Складывание нескольких (дискретных) операций в одну (непрерывную) операцию

Для простого примера предположим, что мы проверяем, является ли char c буквенно-цифровым:

if (48 <= c && c <= 57 ||
 65 <= c && c <= 90 ||
 97 <= c && c <= 122)
{
 // ...
}

6 операций, чтобы подтвердить, что это так.

Но нет ли такой непрерывной функции f (c), что f (c) > 0 для буквенно-цифровых байтовых значений, 0 для остальных? Я думаю, что есть хотя бы один: многочлен степени 12, который "подходит" по 12 очкам, сплетенный вверх и вниз по оси x; но, возможно, существует и функция меньших степеней, или даже не многочлены. Такая формула "упростит" операции для:

if (f(c) > 0)
{
 // ...
}

Есть ли для этого термин искусства? (слово "складывание" приходит на ум, но оно не дает каких-либо релевантных результатов поиска, только концепция складчатости Хаскелла.) Кажется, что пока мы можем сопоставить кодомену набора операций с кодоманом достаточно тонкой гранулярности, мы можем получить такую ​​ "складку". Таким образом, мой вопрос: может "складывать" время сэкономить?. Или существует какой-то принцип сохранения, который заставляет стоимость вычисления "складки" соответствовать (или даже превышать) стоимости вычисления оригинальные, "сырые" операции.

3 ответа

Полином пересекает ось x 6 раз, т.е. имеет 6 вещественных корней, поэтому достаточно многочлена степени-6.

f(c) = -(c-48)*(c-57)*(c-65)*(c-90)*(c-97)*(c-122)

Это, конечно, будет тратить время, делая 5 умножений намного медленнее, чем 5 логических операций. Кроме того, && и || замыкаются так часто, что вам не нужно делать все.


В вашем конкретном случае оптимальная форма:

unsigned u = c;
if (u-48<10 || (u|32)-97<26)

Согласитесь, это не решает проблему так, как вы искали, но те же самые концепции (то есть (1) превращение двух сравнений в диапазон с одним вычитанием и сравнением без знака и (2) использование поразрядного или объединение нескольких которые имеют одинаковые длины и для которых совпадения совпадают) часто могут быть обобщены в других ситуациях.


Есть ли причина, по которой функция isalnum() недостаточна для ваших нужд? Не забудьте #include.

licensed under cc by-sa 3.0 with attribution.