Расмотрим [0-9] Фактически это диапазон чисел от 30h до 39h (ASCII коды цифр) В двоичной системе: _________________________ Символ: 0 30h 0011 0000 1 31h 0011 0001 2 32h 0011 0010 3 33h 0011 0011 4 34h 0011 0100 5 35h 0011 0101 6 36h 0011 0110 7 37h 0011 0111 8 38h 0011 1000 9 39h 0011 1001 _________________________ Как видим, старшие 4 бита совпадают у всех чисел диапазона - достаточно проверить их и в случае НЕСОВПАДЕНИЯ утверждать о том, что число не попадает в диапазон. Однако совпадение не позволяет утверждать о попадании в диапазон - потребуется дополнительная проверка. В чем преимущество такого подхода? Если мы ищем числа в строке, состоящей в большинстве своём из текста, то большинство символов будет отбрасываться при первом же сравнении. Проверка выглядит так : ________________________ and 1111 0000 xor 0011 0000 jz совпадение, необходима дополнительная проверка. иначе продолжение цикла ________________________ Это быстрее чем поверка сравнением крайних значений диапазона. Но главное преимущество в том, что таким образом можно проверять попадание в множество чисел, не являющееся диапазоном и число проверок в большинстве случаев будет меньше числа чисел. (Я думаю над тем, как приспособить сюда 32р операции, что бы проверять за раз 4 символа.) Рассмотрим такой пример: [{}()[]<>], то есть нам нужно совпадение с любой скобкой. Вот так это выглядит: _________________________ { 7bh 0111 1011 } 7dh 0111 1101 ( 28h 0010 1000 ) 29h 0010 1001 [ 5bh 0101 1011 ] 5dh 0101 1101 < 3ch 0011 1100 > 3eh 0011 1110 _________________________ Как видим, совпадают у этих чисел только два бита: 0xxx 1xxx Проверка может выглядеть так: ______________ and 1000 1000 xor 0000 1000 jz совпадение, необходима дополнительная проверка. иначе продолжение цикла ______________ Но дело в том, что под эту маску попадает 64 числа из 256 возможных, мы же ищем один из 8. То есть ложных срабатываний может быть неприемлимо много. Можно разделить это множество на два: _________________________ { 7dh 0111 1011 } 7dh 0111 1101 [ 5bh 0101 1011 ] 5dh 0101 1101 < 3ch 0011 1100 > 3eh 0011 1110 _________________________ и _________________________ ( 28h 0010 1000 ) 29h 0010 1001 _________________________ В первом множестве совпадают 3 бита 0xx1 1xxx . Проверка выглядит так: ___________________ and 1001 1000 xor 0001 1000 jz совпадение, необходима дополнительная проверка. иначе следующая проверка ___________________ что сужает диапазон попадаемых чисел с 64 до 32, а это уже более приемлимо. Второе множество отличается от первого тем, что имеет маску 0010 100x И ЗАНИМАЕТ ВСЕ ВОЗМОЖНЫЕ ЗНАЧЕНИЯ, то есть попадание под маску говорит об однозначном попадании в диапазон. Таким образом мы можем проверять совпадение с одним из 8 символов всего двумя проверками: ___________________ and 1001 1000 xor 0001 1000 jz совпадение, необходима дополнительная проверка. and 1111 1110 xor 0010 1000 jz совпадение(однозначное) ___________________ То есть мы имеем 32 варианта которые могут показать совпадение с одним из 6 чисел, и два числа, которые определяются с первого раза. Моя цель написать функцию, которая получив на входе множество чисел, на выходе давала бы маски и оптимальную последовательность действий. Однако для принятия решения далеко не всегда этой информации достаточно: вероятности встречи символа '{' в тексте романа 'Война и мир' и исходиках M$ Win немного отличаются, а это может влиять на выбор маски. Это так называемые частотные деревья, и наша функция должна уметь с ними работать. Обычно мы заранее знаем со строками какого вида придется работать программе - html, исходники программ, английский или русский текст, а значит мы можем указать вероятности появления того или иного символа. К этой же задаче мы можем свести поиск одной из нескольких альтернатив. Простейший пример : (Jane | Sam | Jack | Mary ) Если размышлять так, как учит "Mastering Regular Expressions", то читать это следует как "один из вариантов: Jane или Sam или Jack или Mary", а каждый вариант читается наподобие следующего: "J, за которым следует a, за которой следует n, за которым следует e". По этой логике нам следует искать совпадение с одной из букв [J S M], и в случае совпадения проверять на совпадение со следующим символом и т.д. На самом деле решить задачу можно гораздо проще: надо искать символ 'a', который имеется в каждом слове. При совпадении с символом проверять на совпадение с одним из слов. Кроме того, если не совпало, поиск начинать не со следующего символа а через один. Почему? Во всех словах символ 'a' встречается на второй позиции, таким образом, если совпадения не было, то предположив, что со следующей буквы начинается одно из нужных нам слов, приходим к выводу, что символ 'a' встретится не раньше чем через одну позицию. В случае, если слова, содержащие искомый символ, достаточно длинные и содержат только один такой символ, это может привести к некоторому выигрышу в быстродействии(чем ближе символ к концу слова, тем больше выигрыш). Таким образом, нам нужна функция, которая из множества вариантов составляет множество символов, которые надо искать, при этом учитывает длину каждого варианта, позицию символа в каждом варианте и частотное дерево строки, в которой осуществляется поиск(если таковое имеется) Другой возможный вариант ускорения поиска: Вычисляем длину минимально возможной строки, которая может дать совпадение с regex-ом, (обозначим длину l), составляем множество символов, которые не входят в regex, выбираем из них тот, у которого вероятность встретить его на отрезке длиной l один раз максимальна. Разбиваем строку, в которой производится поиск, разделителем служит этот символ. В итоге получим множество строк, и если символ подобран правильно (если вообще возможно подобрать такой символ), то значительная часть этих строк будет иметь длину меньшую, чем может иметь строка, совпадающая с regex, что позволяет отбросить эти строки не проводя сравнения. Выбираем символ такой, что бы вероятность встретить его один раз была максимальна, но это не значит что мы берем символ, наиболее часто встречающийся - такой символ может встречатся слишком часто и разбивать строку на слишком маленькие части, что приведет к замедлению как на этапе разбивки, так и на этапе отброса заведомо коротких строк. Кроме того, разбивка может проводится не по одному символу, а по нескольким, комбинируя набор которых можно максимально приблизить вероятность встречи одного из них к требуемой. Строки, длина которых больше l-1, проверяются не до конца. Если длина такой строки l+n, то просмотрев n+1 байт можно прекратить поиск, поскольку остается l-1 байт, а это меньше минимально возможной совпадающей строки. Такой сценарий применим, когда необходимо найти все совпадения, т.е. просмотреть всю строку. Вряд ли это будет лучшим решением, если необходимо найти первое совпадение. Однако есть еще один метод быстрого поиска совпадения с одним из символов диапазона. К сожалению он неприменим, если поиск ведется в одной короткой строке так как время, затрачиваемое на инициализацию может оказаться больше времени поиска по маске. Суть метода такова: инициализируется 256 байтное поле, в котором каждый байт соответствует одному из 256 возможных вариантов. Те байты, которые соответствуют символам, входящим в диапазон, обнуляются, остальные заполняются любым ненулевым значением. Процедура поиска следующая: cld ;флаг напрвления, просмотр по возрастанию адресов xor eax, eax @start: lodsb test byte ptr [ebp+eax], ffh loopnz @start иначе совпадение, в eax совпавший байт, esi смотрит на байт следующий после совпавшего. ebp смотрит на 256 байтную структуру. Наиболее универсальный метод, подходит для самых запутанных множеств. Однако потеря времени на инициализации структуры. Это существенно при интерпретации кода, однако при исполнении скомпилированного кода этой потери нет, так как уже инициализированная структура может включатся в код программы. Но это увеличивает её размер на 256 байт для каждого множества, используемого в regex, а каждое выражение может порождать десятки таких множеств, что выглядит не так уж и безобидно. Кроме того, этот метод применим только к 8-разрядным числам, на 16 разрядах потребуется 64кбайта (даже если работать с битами - это 8кбайт), о 32р можно забыть 16разрядов - работа с unicode и подобными кодировками, 32р - индексы баз данных, timestaps, crc и прочие хэши, etc.