Поиск в содержимом файла

[Хакер]

Как прочитать "буквы" из памяти?

Способов тьма.

1. CopyMemory. Медленнее не придумать, глупее не поступить. За использование — расстрел.
2. GetMem1. Но тоже медленно, хотя куда лучше, чем CM
3. Хитрообёрнутый, но тот же GetMem. Куда быстрее, чем GetMem через Declare.
4. Заставить обычный байтовый массив указывать на твой регион памяти и работать с массивом. Очень быстро, если отключить в настройках оптимизации контроль границ массива, и почти так же, как и предыдущий способ, если не отключать. Но зато красиво. Правда я не провериял релизиацию Viper-а, поэтому просто надеюсь, что там именно то, о чём я говорю. Можешь так же в двух моих последних кирпичах поискать функции SaMap/SaUnmap, вот это точно то, о чём я говорю.
5. Указатели через ByRef-аргумент. Трюк хороший, но из-за необходимости часто сдвигать указатель, не быстрее, чем предыдущие два.
6. Найти какую-нибудь API-функцию, которая получает адрес одной (большой) последовательности байтов и адрес другой (меньшей) последовательности байтов и ищет второую в первой. Или написать такую функцию на Си. Наибыстрейший вариант, при условии, что функция написана хорошо.

Хотя, я бы озаботился вообще о другом. Ты ведь не одну фразы хочешь искать в своём файле, а несколько разных?

[kuhtiov]

Да, прав. И при таком раскладе дел, учитывая что число символов искомого слова будет разное, вылазит задница. Каждый раз совершать поиск с нуля для каждой фразы не есть гуд.

[Хакер]

Вот, поэтому тебе нужна хитрая поисковая функция, которая будет искать параллельно несколько фраз в одной большой последовательности.

И конечно, «параллельно» совершенно не означает многопоточно.

Справишься сам с написанием такой функции?

[kuhtiov]

Если честно, то нет. У меня мозг закипать начал при попытке нарисовать это в голове. Я понимаю, что нужно "всандалить" цикл по поисковым фразам в код чтения файла из памяти. Т.е. определяю максимальное число символов из всех вариантов фраз, в момент чтения беру именно такое кол-во символов и ищу циклом мои фразы. Как-то так. Пока только теория

[alibek]

Сделай класс, у которого задается эталонная (поисковая) фраза и которому передается текущий байт/символ (или последовательность байт/символов).
При совпадении с эталонным значением счетчик совпадений увеличивается на один, иначе обнуляется.
Если счетчик совпадений дошел до длины поисковой фразы, значит найдено.
Создай столько инстансов этих классов, сколько у тебя поисковых фраз.

[Хакер]

Сделай класс, у которого задается эталонная (поисковая) фраза и которому передается текущий байт/символ (или последовательность байт/символов).
При совпадении с эталонным значением счетчик совпадений увеличивается на один, иначе обнуляется.
Если счетчик совпадений дошел до длины поисковой фразы, значит найдено.
Создай столько инстансов этих классов, сколько у тебя поисковых фраз.

Это очень неоптимальный алгоритм. Во-первых, использование объектом делает всё это более медленным. Во-вторых, такая стратегия требует отката назад после каждого неудачного слова (сброса до нуля в одном из объектов). А при этом она ничем не лучше, чем просто применять RtlCompareMemory к каждому адресу для каждого слова.

[alibek]

Алгоритм или реализация?

[Хакер]

Что именно?

[alibek]

Неоптимальный алгоритм или реализация (через классы)?
Потому что никакой принципиальной разницы я не вижу.
Это как обход двухмерного массива по столбцам или по строкам; либо сканирование данных в поисках каждой поисковой строки (цикл по поисковым строкам), либо сканирование блока данных для каждой поисковой строки (цикл по блокам).

[Хакер]

Неоптимальный алгоритм или реализация (через классы)?

Ну реализации пока никакой нет, а алгоритм плох, да. И

Это как обход двухмерного массива по столбцам или по строкам; либо сканирование данных в поисках каждой поисковой строки (цикл по поисковым строкам), либо сканирование блока данных для каждой поисковой строки (цикл по блокам).

Хороший способ — это создание на основе списка слов графа. А потом обход графа с использованием большой последовательности данных как маршрута. Да-да, всё та моя любимая маршрутизация, о которой я так много писал.

Причём с графами есть несколько вариантов разной крутости, но это способ, обеспечивающий максимальное возможное быстродействие.

Есть способ без графа, просто со списком слов. Когда все слова лежат плотно друг-к-другу, это будет быстрее работать, потому что чтение из памяти осуществляется 8-байтными блоками, то есть если нужен один, то вместе с ним будут прочитаны все 7 соседних, и потом, когда данные лежат рядом, максимально эффективно работает процессорный кеш. В случаях, когда нужно миллиард раз поработать с одними и теми же данными, это имеет критическое значение.

Вот если взять твой алгоритм и отказаться от классов в пользу массива массивов символов и массива счётчиков. Счётчик вообще неправильно называется счётчиком, поскольку он не столько считает, сколько определяет текущий эталонный символ из эталонного слова. Не знаю, не забыл ли ты случайно необходимость определять этот символ, но по сути, это критически важно (текущий символ должен быть не просто равен одному из эталонных символов на манер SQL-оператор IN, но и быть на своём месте в эталонном слове). Так вот, отказываемся от счётчика пользу «индексной переменной», и переформулируем условие в «индексная переменная дошла до своего макс. значения».

Вот если к этому всему добавить учёт потенциальных точек входа (entry points), в смысле потенциальных позиций в большой последовательности, где может начинаться слово, то тогда при отказах (failure) можно не откатываться назад до следующего символа (на момент начала сравнения слова), а можно откатываться до крайней-левой точки входа.

В общем, предлагаю тебе реализовать свой поиск, а я реализую свой. А потом сравним слабые и сильные стороны

[Qwertiy]

Вот если к этому всему добавить учёт потенциальных точек входа (entry points), в смысле потенциальных позиций в большой последовательности, где может начинаться слово, то тогда при отказах (failure) можно не откатываться назад до следующего символа (на момент начала сравнения слова), а можно откатываться до крайней-левой точки входа.

А префикс-функция не лучше будет? Или это она так хитро описана?

[Хакер]

А префикс-функция не лучше будет? Или это она так хитро описана?

Нет, это разные вещи. Вряд ли лучше.

Кстати, один из примеров алгоритма с графами, алгоритм Ахо—Корасик. Только сейчас нашёл его название, а то не мог вспомнить, когда писал предыдущий пост.

[Qwertiy]

Вряд ли лучше.

Почему? По-моему, надо в первую очередь минимизировать работу с файлом, а использование префикс-функции позволяет не откатываться назад по строке, поэтому результат получается за один проход по файлу.

Кстати, один из примеров алгоритма с графами, алгоритм Ахо—Корасик.

Не уверен, что в данном случае стоит его использовать.

[Хакер]

Почему? По-моему, надо в первую очередь минимизировать работу с файлом, а использование префикс-функции позволяет не откатываться назад по строке, поэтому результат получается за один проход по файлу.

Нет, не нужно. При первом обращении к страничному фрейму, он попадает в физическую память, в working set, а далее в процессорный кеш разных уровней. Поэтому небольшие откаты не смертельны.

Префикс-функция конечно улучшит картину, но её вычислительная сложность не стоит выигрыша в производительности, по моим предварительным оценкам.

[Qwertiy]

Префикс-функция конечно улучшит картину, но её вычислительная сложность не стоит выигрыша в производительности, по моим предварительным оценкам.

Какая вычислительная сложность? Там же O(len*count) получится для файла (count - число искомых строк) для поиска и O(sum of lens) для подсчёта префикс-функции для искомых строк.

[ger_kar]

Вот обещанный мой чудо - медленный алгоритм в конкретной реализации
В архиве тестовый файл, который я использовал для тестирования работоспособности, в поле формы "шаблон" - текстовая строка, которую я взял из этого файла. Посмотрев обсуждение прихожу к мнению, что можно конечно извращаться с разными чудодейственными алгоритмами, про которые я понял только что это круто и быстро, но это будет полезно только с целью обучения. А на практике, можно ограничится двумя кирпичами и пробежаться по массиву. Очень понравилась идея Алибека с классом, для множественного поиска, что для практического использования будет самое то! ИМХО.

[kuhtiov]

Вот обещанный мой чудо - медленный алгоритм в конкретной реализации
В архиве тестовый файл, который я использовал для тестирования работоспособности, в поле формы "шаблон" - текстовая строка, которую я взял из этого файла. Посмотрев обсуждение прихожу к мнению, что можно конечно извращаться с разными чудодейственными алгоритмами, про которые я понял только что это круто и быстро, но это будет полезно только с целью обучения. А на практике, можно ограничится двумя кирпичами и пробежаться по массиву. Очень понравилась идея Алибека с классом, для множественного поиска, что для практического использования будет самое то! ИМХО.

ч.т.д. Сперва я удивился, когда в файле весом 130 метров, поиск выполнился за 0.078125 и подумал, что это отличный показатель. Но потом понял, что искомое выражение находится в начале файла и решил экспериментировать дальше. Введя искомое выражение которое точно не встретится (Inno Setup1), я проверил код на 2-х файлах. Вот результаты:

13.3 МБ - 23,15234 с.
129 МБ - 231,9844 с.



Вариант, что искомое выражение будет отсутствовать в файле вполне допустимо, так что я считаю что этот способ - зло вселенское в чистом виде!
Но ты молодец что его прислал, держишь слово. У меня до сих пор нет кода

[ger_kar]

Ну вообще в идеале хотелось бы увидеть все реализации идей, которые были предложены в этом посте, но наверное, все реализовать не получиться, но некоторые я думаю можно, к вечеру выложу реализацию идеи, с которой собственно пост и начался, т.е. Модернизирую свой способ, для чтения блоками и посмотрим как это отразится на производительности. Очень бы хотелось потестить вариант с мапом файла в память и простым GetMem, без всяких извращенных алгоритмов. Кстати неплохо было-бы определиться и с тестовым файлом, тот на котором я тестил уж слишком маловат. Какие будут предложения? Но желательно, чтобы ничего не качать. Можно взять большое изображение, а если такового нет, то сделать, путем раздувания разрешения, а потом банально в него вставить в двоичном редакторе, какую нибудь фразу и ее потом искать. Я думаю, что файла весом метров 30 будет вполне достаточно, для сравнения производительности разными методами.

[ger_kar]

Я тут немного подумал и решил, что все-таки сначала попробую сделать вариант с мапом в память, так как фактически, мой предыдущий вариант подходит с минимальными изменениями, по сути меняется только то, что вместо работы с физическим файлом на диске, будет использоваться его мап из памяти, достаточно просто добавить соответствующий кирпич . Но вот засада, указатель на начало я получаю без проблем, но как определить конечную ячейку, либо максимальный размер никак не догоню. Можно конечно сначала определить величину файла на диске в байтах, а потом уже использовать эти данные, но этот способ мне кажется несколько извращенским, хотелось бы напрямую с мапом работать.

[ger_kar]

Вот обещанный вариант с мапом в память, работает конечно быстро, спору нет, и это при том, что сам алгоритм поиска в образе, прост до банальности. Проблему изложенную сообщением выше так и не решил, пришлось добывать длину файла непосредственно из файла , ну и ладно. Обнаружился очень интересный глюк, при тестировании это надо будет учесть. Если запускать тест из среды разработки, то корректный поиск будет только первый раз, при последующих запусках (если в первый раз строка была найдена) строка опять найдется, даже если её в файле отродясь не было, и причем, по тому-же самому адресу . Для того что-бы и во второй раз поиск был корректным среду нужно перезапустить. Ну или как вариант пользоваться скомпилированным файлом. В причинах глюка мне разбираться, что-то не очень охота, да и с моими знаниями наверное это будет затруднительно, здесь нужен, кто нибудь по компетентней, для того, что-бы обнажить истину .

[kuhtiov]

Крут. Время поиска файла весом 129 МБ, снизилось с 23,15234 до 10,41016 с. Спасибо за пример, ща попробую разобраться как ты там из памяти читал

[ger_kar]

В общем тестирование на всем, что под руку попадет показало следующее: Если например взять большой файл, например фильм, весом 800 Мб, то полное сканирование (естественно что ничего не находится) происходит за 20 сек. Кроме этого выявился еще один глюк. Если файл большой > 100 Мб, то IDE падает, скомпилированный вариант работает нормально. И еще на двух файлах примерно одного размера 18 и 22 Мб и при отсутствии в них искомой строки - время поиска составило 2 и 0,4 сек соответственно. Отсюда сделал вывод, что в большем файле (видеоклип) сканирование прошло быстрее из-за отсутствия возвратов, а в меньшем файле (приложение) видимо были частые возвраты из-за совпадений с частью строки, отсюда и большее время поиска. Значит алгоритм поиска нужен посерьезней

[Хакер]

Крут. Время поиска файла весом 129 МБ, снизилось с 23,15234 до 10,41016 с. Спасибо за пример, ща попробую разобраться как ты там из памяти читал

Надеюсь тесты делались на скомпилированном файле, а не на работающем проекте?

[ger_kar]

Надеюсь тесты делались на скомпилированном файле, а не на работающем проекте?

Ради интереса провел такое сравнение: Поиск в файле Directx_Jun2010_redist.exe - 95,6 Мб
Скомпилированный проект время - 1,45 , Запуск из IDE - 5,25

[Хакер]

Что толку сравнивать сингл-поиск. Предлагаю сравнивать мультипоисковые алгоритмы.

ПС. Вообще, я бы посоветовал автору выбрать другой способ определения типа компилятора. Или как минимум конкретезировать критерий: например подтвердить или опровергнуть какую-нибудь гипотезу, вроде гипотезы о том, что нужная строчка лежит не абы-где, а в какой-либо конкретной секции PE-файла. И соответственно, загружать файл уже через MapAndLoad и искать строчку конкретно в нужной секции, а не везде.

[ger_kar]

Что толку сравнивать сингл-поиск. Предлагаю сравнивать мультипоисковые алгоритмы.

Ну скажем, толк в том (для меня по крайней мере) сравнить первый вариант выборки (побайтно) со вторым, так сказать сравнить скорость выборки . Ну, а теперь, можно в алгоритмах поиска попрактиковаться, для того, что-бы сравнить этот аспект.

ПС. А действительно, что-то в пылу дискуссии и совсем забылось, что нужно, не цедить весь файл на предмет поисковой строки, а определить тип инсталлятора. А это существенно снижает объемы поиска, при их соответствующей детализации. Но касается только определения инсталлятора. Но все таки хотелось бы и первоначальный вариант продолжить. Т.е. перейти к мультипоиску.

[Хакер]

Ну скажем, толк в том (для меня по крайней мере) сравнить первый вариант выборки (побайтно) со вторым, так сказать сравнить скорость выборки . Ну, а теперь, можно в алгоритмах поиска попрактиковаться, для того, что-бы сравнить этот аспект.

Твой вариант с маппингом косячен из-за того, что режимы не соответствуют ситуации.

[ger_kar]

Твой вариант с маппингом косячен из-за того, что режимы не соответствуют ситуации.

Вообще я несколько раз перечитывал предложение и его можно понимать по разному, то-ли мой пример целиком плох из-за того, что в реальной ситуации описанной в теме предполагается мультипоиск, то-ли я сам маппинг неправильно сделал? Так там вроде как и ошибаться негде.
Ну да ладно, тут в голову пришли следующие мысли: Что если при поиске сравнивать не 2 байтовых значения а например две переменных с типом Long, т.е. четыре байта подряд, таким образом будет сравниваться сразу четыре первых символа, а для случаев, когда длина шаблона меньше 4 байт, то к сравниваемым переменным сначала применить битовую маску к соответствующим байтам справа. Таким образом если совпадет сразу 4 байта, то дальше очень высока вероятность, что и все слово совпадет. Таким образом количество откатов будет существенно меньше, а при мультипоиске очень положительно сказаться на скорости. Тем более, что процессору так даже удобнее будет. Или я не прав?

[Хакер]

Так там вроде как и ошибаться негде.

Режимы неправильные. Что с маппингом, что с файлом.

Или я не прав?

Не прав. Сравнение блоками по 4 байта ничего не даст. Если этот 4-байтовый блок не совпал, то следующий 4 байтовый блок будет взят на 1 байт вперёд, а не на 4 вперёд. Таким образом, получается работа с невыровненными 4-байтовыми блоками, что ещё более медленно.

И вообще подобной цели есть специальная инструкция процессора.

[ger_kar]

Вообще странно конечно, процессор 32-х разрядный, значит по логике ему, что один байт зачерпнуть из памяти, что 4 за раз, без разницы, ну сдвинулся указатель на 1 ячейку а не на 4, какая разница процу одну зачерпнуть или опять 4. Или он считывает сразу большими блоками, а потом уже берет из кэша, что очень быстро, а предлагаемом мною варианте, каждый раз будет черпать из памяти?

И вообще подобной цели есть специальная инструкция процессора.

Это намек сделать ассемблерную вставку?
А в чем неправильный режим с маппингом? Нужно брать блоками, а не целиком как сделал я? Я теряюсь в догадках.