Алгоритм поиска паттерна в неупорядоченной последовательности?

Question

[Дмитрий Гавриленко]

Приветствую всех.
Задача такова: есть не отсортированный (естественно) массив байтов размерностью 2млд и более.
Есть определенный паттерн размером в 10 байтов. Надо найти все позиции паттерна в массиве.
Линейный поиск не самая лучшая реализация. Подскажите, что работает быстрее.
Спасибо!

Comments

[Александр]

Вы хотите на неотсортированном массиве выполнить поиск быстрее чем за O(n)? Боюсь, это в принципе невозможно.

[Дмитрий Гавриленко]

Александр: я не гуру алгоритмов, но такие предположения тоже имеется. Точно известно, что паттерн есть в самом начале. Его точно нельзя как-то ускорить, если не брать в счет асинхронные операции?

[Александр]

Дмитрий Гавриленко: Дмитрий, я сам не гуру. Но если массив не упорядочен, то придётся проверить каждый его элемент - по другому никак. А это и есть сложность O(n), и быстрее линейного поиска ничего не получится.
Для некоторых частных случаев можно применить хитрости и добиться экономии в несколько раз. Например, если в искомом паттерне по нескольку раз повторяются одинаковые символы. Но для общего случая - только линейный поиск.

[Дмитрий Гавриленко]

Александр: прочите комментарий к ответу x67

Answer 1

[x67]

Ну в общем-то, как заметил Александр, вы хотите чуда, но алгоритм можно оптимизировать, если есть какая-либо закономерность, которая позволяет предсказать, в каких областях может быть искомый паттерн.
Также если местоположение начала паттерна не может быть произвольным (то есть паттерн может начинаться в 1, 11, 21 байте, но не может начинаться в 37 к примеру), то время поиска можно сократить менее, чем в 10 раз, сначала поискав все первые байты, а потом проверив эти места уже полностью.
Также можно поискать закономерность в этом паттерне.
Но в целом, если это будет регулярной задачей, прикрутите что-нибудь для первоначальной обработки массива.

Comments

[Дмитрий Гавриленко]

Исходные данные каждый раз разные. Найти в нем какую-то закономерность невозможно.
Из всего этого могу только указать на то, что сам паттерн не меняется, и содержит 5 идущих подряд 0. То бишь: x x x 0 0 0 0 0 x x
Можно это как то использовать?

[x67]

Конечно! Теперь ты перебираешь не каждый из 2 млрд. байт, а каждый 5 байт(1, 6, 11,16 и тд). Ищешь нули тем самым линейным поиском, когда находишь, проверяешь на соответствие паттерну, только надо учитывать смещение паттерна относительно найденного нуля. Поиск будет тем эффективнее, чем меньше случайных нулей будет в массиве.

Answer 2

[Александр]

С учётом вашего комментария к ответу x67:
В этом случае можно попробовать проверять только каждый пятый байт. Если там ноль - от него шагаем по одному символу влево до тех пор пока не наткнёмся на не ноль. После чего отходим ещё на пару символов влево и уже с этого символа проверяем вхождение паттерна.
Теоретически можно получить экономию почти в пять раз.
Но это будет хорошо работать только если в массиве мало нулей, не являющихся частью паттерна. Если же в массиве много посторонних нулей - то может получится даже хуже, чем при линейном поиске.
И всё-таки рекомендую попробовать реализовать этот вариант и замерить время работы по сравнению с линейным поиском.

Answer 3

[Дмитрий Гавриленко]

Спасибо Александр и x67 Реализовал вашу идею. Вот небольшой отчет производительности на массиве данных размером чуть меньше 1 000 000 запущенный 1000 раз. Время указываю суммарное, за все 1000 запусков.
Линейный поиск - 9000-9300 мс
Реализация Александр - 4100-3900 мс
Доработка (с предварительной проверкой на хотя бы один 0 вокруг buffer[i]) - 3100-2900 мс

Comments

[x67]

Приятно видеть, когда небольшая оптимизация помогает в 2-3 раза сократить время поиска)

[Дмитрий Гавриленко]

x67: все гениальное - просто)