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

[Хакер]

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

В чём выигрышь? Количество операций сравнения, что в случае байта, что в случае дворда — одинаковы.

[ger_kar]

В чём выигрышь? Количество операций сравнения, что в случае байта, что в случае дворда — одинаковы.

Ну пока идет основной цикл, то выигрыша нет, но по логике и проигрыша тоже, но, если сравнивать например по 1 байту, то при совпадении первого символа начинается вложенный цикл, в котором сравнивается второй символ и так далее. И здесь начинаются лишние накладные расходы - организация вложенного цикла происходит очень часто, всякий раз при совпадении первого символа, далее чуть поменьше это выход из вложенного цикла, при несовпадении второго символа и откат назад, далее еще реже откаты при несовпадении третьего и т.д. В реальности цифры такие:
Поиск в файле Directx_Jun2010_redist.exe весом 95 Мб.
Совпадение с 1 символом - 385622
Совпадение с 1 и 2 - 1570
Совпадение с 1, 2 и 3 - 6
Совпадение с первыми 4 - 2
Таким образом если сравнивать сразу 4 байта, то применительно к моему алгоритму и данным условиям поиска удалось бы избежать
Затрат на организац внутреннего цикла, GetMem1 и операций сравнения - 385622 раз
Затрат на операции сравнения, интерацию счетчика цикла и опять же GetMem1 - еще 1570 раз.
Остальное не стоит внимания. А если поиск будет не одиночным, а мульти, и скажем будет искаться 5 строк сразу, то я думаю выигрыш будет очевиден. Вот таким и был ход моих мыслей.
Кстати хотелось и про мапп узнать, то что неправильно, я понял, а как правильно не догнал

[Хакер]

Ну пока идет основной цикл, то выигрыша нет, но по логике и проигрыша тоже,

Я предполагаю, что проигрышь есть из-за того, что для формирования 32-битных значений из невыровенных ячеек понадобятся доп. сдвиговые операции в процессоре.

Но надо понимать, что основное время тратится на основной цикл.

К тому же, оперирование не байтами не позволяет строить список точек входа.

Кстати хотелось и про мапп узнать, то что неправильно, я понял, а как правильно не догнал

Везде рид-онли и секвентал-скан на файл. Грубо говоря.

[ger_kar]

Везде рид-онли и секвентал-скан на файл. Грубо говоря.

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

[Qwertiy]

Поиск в файле.7z

(7.27 Кб) Скачиваний: 111

Надеюсь, багов не насажал

[Хакер]

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

read-only позволяет выгружать страницы из working-set-а без проверки Dirty-флага в PTE каждой отдельной страницы.
sequental scan позволяет cache manager-у эффективнее организовать работу с файлом-образом.

[ger_kar]

Посмотрел пример Qwertiy, пример мне понравился и хотя там мап даже близко не используется, скорость довольно приемлемая, но самое главное мне понравилось, что все решено встроенными возможностями VB и особенно сам алгоритм поиска.
Решил, сделать таки вариант со сравнением 4 байтов за раз, просто ради любопытства. Тесты все покажут

[Qwertiy]

А кто-нибудь ещё поиск нескольких строк написать собирается?

Кстати, есть подозрение, что я зря открываю файл For Binary. Это действительно нужно или можно лучше/правильнее?

[ger_kar]

А кто-нибудь ещё поиск нескольких строк написать собирается?

Я собираюсь
Насчет For Binary не в курсе, но наверное большой разницы не будет.

[iGrok]

Кстати, есть подозрение, что я зря открываю файл For Binary. Это действительно нужно или можно лучше/правильнее?

Это действительно нужно.

[kuhtiov]

ger_kar, можешь разжевать вариант с мапом? Если в цикл

Код: Выделить всё

For i = 1 To intLenStroka - 1

вставить поиск по нескольким ключевым словам (чтобы каждый раз не искать с начала), я так думаю это может снизить производительность поиска в целом, но с другой стороны если искомое выражение находится в начале или середине файла, то таким образом обработка файла выполнится быстрее, чем начинать поиск в отдельности, для каждого ключевого слова, верно? Или возможен еще более быстрый поиск?

[Хакер]

Или возможен еще более быстрый поиск?

Как бы уже 2 страницы исписано как раз ровно тем, что более быстрый поиск возможен.

[ger_kar]

Вечером выложу вариант с маппом и мультипоиском

[ger_kar]

А вот и обещанный "супер" мультипоиск от меня .
Заценяйте.

ЗЫ: Не просто ищет, а считает, сколь раз чего нашел.

Перезалито! Теперь нормально обрабатывает строки любой длины. Спасибо Qwertiy, за найденный баг

[kuhtiov]

Маньяк. Отличный исходник. При нескольких условиях время поиска в файле размером свыше 150 Мб, 7 сек.
С вашего позволения заюзаю?

[Хакер]

Отличный исходник.

Исходник — эталонный пример кривого отстойного кода.

[kuhtiov]

Отличный исходник.

Исходник — эталонный пример кривого отстойного кода.

А в чем кривизна?

[Хакер]

А в чем кривизна?

Звучит банально, но в коде. Начиная отступами и заканчивая тем, что мап выделили в отдельную процедуру, а анмап никуда не выделили. То есть проецирование сделали абстрактно от проецирующей подсистемы, а анмап без какого-либо посредника, без абстракции, без обёртки в процедуру. Ну и вообще, как можно нормальным считать то, что процедура поиска выполнена не как отдельная процедура, а как обработчик события «Клик» кнопки с именем (о боже) «Command1». А как можно стерпеть I и II, когда уже невероятное число лет математики используют для этой цели i, j, k, а в последние 60 лет и программисты тоже?

А вот это: Mid$(strSearch(I), II, 1) = Chr$(bytCode) — просто кошмар.

[kuhtiov]

На сколько я понял, тебе в основном не нравится код с точки зрения оформления? Я думаю что для кода накиданного на скорую руку, вполне достойно

[Хакер]

На сколько я понял, тебе в основном не нравится код с точки зрения оформления?

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

Настаиваю на том, что нужно выработать единые условия и правила для тестирования и сравнения между собой алгоритмов и реализаций.

[ger_kar]

Вау! Сколько критики в адрес моего "Супер" поиска... Это хорошо! Значит поиск получился внатуре "Супер"

Звучит банально, но в коде. Начиная отступами и заканчивая тем, что мап выделили в отдельную процедуру, а анмап никуда не выделили.

А что с отступами? Еще раз все просмотрел вроде все нормально, мой глаз косяков не приметил, ежели есть косяк, то конкретно где? А насчет анмап, какой смысл затевать отдельную процедуру для одной строчки кода.

Ну и вообще, как можно нормальным считать то, что процедура поиска выполнена не как отдельная процедура, а как обработчик события «Клик» кнопки с именем (о боже) «Command1»

Кроме поиска, обработка события кнопки Command1, больше ничем не занимается, ну и какой смысл разделать это логически целое, по разным процедурам. Тем более целью было просто показать, как мне видится алгоритм мультипоиска. А чем плохо название Command1? В интерфейсе с двумя кнопками, запутаться в принципе не возможно.

А как можно стерпеть I и II, когда уже невероятное число лет математики используют для этой цели i, j, k, а в последние 60 лет и программисты тоже

А чем плохо использовать I, II, III, которые у меня например ассоциируются с римскими цифрами 1, 2, 3 и соответствующим уровнем вложенности. Здесь ИМХО всего лишь вопрос предпочтений. Например насчет наименований есть как сторонники венгерской нотации, так и противники оной. А сам спор лежит чисто в субъективной плоскости восприятий и предпочтений отдельно взятого индивидуума.

А вот это: Mid$(strSearch(I), II, 1) = Chr$(bytCode) — просто кошмар.

А в чем кошмар-то? Мне очень интересно, потому, как я ничего кошмарного в такой записи не нахожу.

Вот здесь тоже набросанный на скорую руку, но в нём всё идеально с оформлением. Но и с архитектурой тоже, что важнее.

Скорая рука, у всех скорая по разному

В общем, это в принципе не являющийся хорошим код, ещё и в довесок плохо оформленный.

Пес с ним с кодом, а сам принцип поиска тоже отстой? Ищет вроде быстро.

Настаиваю на том, что нужно выработать единые условия и правила для тестирования и сравнения между собой алгоритмов и реализаций.

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

[Хакер]

А что с отступами?

Их нет вообще. Разумеется, речь идёт о вертикальных оступах.

Кроме поиска, обработка события кнопки Command1, больше ничем не занимается, ну и какой смысл разделать это логически целое, по разным процедурам.

Какойсмысолпесатьспрабеламииващщепридержывацакакойтаграмматнастиитакведьмопнятночойаимейуввиду?

А в чем кошмар-то? Мне очень интересно, потому, как я ничего кошмарного в такой записи не нахожу.

Вместо того, чтобы сравнить два байта, дважды вызывается SysAllocString чтобы выделить место под каждую их двух сравниваемых строчек из строковой кучи OLE, дважды вызывается SysFreeString для освобождения памяти под эти строчки. Выделяются куски размером 4+2+2 байтов, а само сравнение этих строчек вопреки принципу лени первым действием всякий раз сравнивает 4 первые байта BSTR-строки, которые заведомо во всех случаях содержат одинаковое значение. Сама же функция Chr — это тысячи строк кода, это конвертация текущая локаль → юникод, это обращение к системным таблицам преобразования символов.

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

Пес с ним с кодом, а сам принцип поиска тоже отстой? Ищет вроде быстро.

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

[Хакер]

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

Глупее даже при определённом старании не придумаешь. Вообще-то характерный для программиста ответ: это написать утилиту, которая генерирует тестовый файл размером 1,8 Гб.

[ger_kar]

Какойсмысолпесатьспрабеламииващщепридержывацакакойтаграмматнастиитакведьмопнятночойаимейуввиду?

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

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

Не знаю, код написан настолько плох, что я так и не смог его прочитать полностью и понять.

Жесть...

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

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

Глупее даже при определённом старании не придумаешь. Вообще-то характерный для программиста ответ: это написать утилиту, которая генерирует тестовый файл размером 1,8 Гб.

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

[Qwertiy]

Глупее даже при определённом старании не придумаешь. Вообще-то характерный для программиста ответ: это написать утилиту, которая генерирует тестовый файл размером 1,8 Гб.

Во-первых, почему собственно текстовый? В целью же exe является, а он бинарный. А во-вторых, почему на одном и том же файле все должны сравнивать? Каждый вполне может сравнивать на своём файле.

А в чем кривизна?

1. Работает неверно со строками короче 4 символов! Не находит просто их. Сам-то тестировал?
Теперь то, что касается форматирования:
2. Видеть на VB несколько операторов на одной строке - как-то совсем непривычно. Хотя, на Си++ пишу иногда связанные логически действия через запятую.
3. Пустые строки действительно не помешают, хотя это и не очень принципиально.
4. Про вынесение закрытия в процедуру - согласен.
5. Про имена контролов - тоже.
6. К переменным цикла отношусь нормально.
7. Поиск в процедуре нажатия на кнопку - тоже нормально. Обычно начинаю растаскивать, когда набирается много кода, но пишу так, чтобы вытаскивание не создало проблем.

Работает действительно быстро: на файле размером 819 427 328 байт - за 73 сек, мой код (если убрать DoEvents) - за 129. Хотя, проверять надо будет, когда исправишь ошибки.

Настаиваю на том, что нужно выработать единые условия и правила для тестирования и сравнения между собой алгоритмов и реализаций.

Для начала, надо определиться с наличием DoEvents в коде. В моём коде он есть, у ger_kar'а нет. Мне кажется, неправильно, что программа "висит" во время поиска.
И вообще, предлагаю вынести весь код, необходимый для поиска в отдельный модуль, и вызывать из него функцию, получающую в качестве аргументов массив искомых строк и имя файла и возвращающую результаты поиска.

[Хакер]

Исправлю , но что-то мне подсказывает, что на времени поиска это практически никак не отразится, т.е. оно конечно отразиться, но на неуловимую величину. Поэтому, я переделаю, а практика покажет...

Во-первых, там вроде есть ещё такие же косяки, так что может и не отразится.

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

Это зависит от входных данных. Если искать слово «диметилалкилбензиламмонийхлоридный» в двухгигабайтном файле, в котором будет очень много раз встречаться слово «диметилалкилбензиламмонийхлоридная», то будет и очень заметно.

Ну этим уже Ось рулит

Ось этим вовсе не рулит. Ось предоставляет изумительные возможности этим рулить, но 99 процентов программистов ими не пользуется. Им редко приходится на скорость работать с огромными объёмами, так что они дразнятся тем, что их время стоит слишком дорого, чтобы они занимались такого рода оптимизацией. Но вот здесь как раз тот случай, когда этим нужно заниматься.

вряд ли это можно исправить простыми средствами

Можно.

да и опять будет ли в этом, какой-либо практический толк в ощутимых количествах.

Это всё очень зависит от машины, на которой всё это будет работать. Если цель: выиграть соревнования на одной тестовой машине, то это одно дело. И совсем другое — написать код, который будет лучше работать вообще, и по-максимуму использовать потенциал собственной эффективности.

Если это архидревняя машина с одноядерным процессором и без DMA, то это ничем не поможет. Но если DMA есть и хотя бы присутствует HT, и время подгрузки страницы сопоставимо со временем обхода страницы, то скорость поиска увеличивается вдвое.

[ger_kar]

Во-первых, почему собственно текстовый?

Вообще Хакер написал тестовый, т.е. для теста.

1. Работает неверно со строками короче 4 символов! Не находит просто их. Сам-то тестировал?

Странно, у меня все находит, я конечно еще раз проверю, изменив условия поиска, а вообще

Во-первых, почему собственно текстовый? В целью же exe является, а он бинарный. А во-вторых, почему на одном и том же файле все должны сравнивать? Каждый вполне может сравнивать на своём файле.

Лучше, как говорит Хакер, по тому, как моем файле и моими условиями поиска строки короче 4 символов находились. Нужны одинаковые условия тестирования.

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

А в добавок к ним еще и комментарии

4. Про вынесение закрытия в процедуру - согласен.5. Про имена контролов - тоже.

Вынесу, хотя по моему мнению, это, что в лоб, что полбу. С именами контролов я обычно так и делаю, если в них можно запутаться, здесь в двух кнопках заблудиться в принципе не возможно.

Для начала, надо определиться с наличием DoEvents в коде.

Ну можно вставить это не проблема, я уже даже знаю куда

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

Фактически это будет уже как кирпич. Можно конечно это сделать, для универсальности применения. Когда я создавал свое творение, я просто хотел протестировать определенные алгоритмы поиска и не более.

[Хакер]

Во-первых, почему собственно текстовый? В целью же exe является, а он бинарный.

Ты ошибся, я написал не «текстовый», а «тестовый».

А во-вторых, почему на одном и том же файле все должны сравнивать? Каждый вполне может сравнивать на своём файле.

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

Для начала, надо определиться с наличием DoEvents в коде. В моём коде он есть, у ger_kar'а нет. Мне кажется, неправильно, что программа "висит" во время поиска.

Я же уже где-то писал, что DoEvents делает кучу лишнего, в частности, там есть Sleep, который вызывает задержку минимум на 20 мс, даже несмотря на то, что указан 0, потому что это в любом случае переключение потока.

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

Я предлагаю сделать вообще так:

От вас требуется EXE-файл. Взаимодействие организовано следующим образом. Есть два файла: input.txt и output.txt.
Формат первого:


Код: Выделить всё

имя-большого-файла-в-котором-нужно-искать<CR><LF>
строка-для-поиска-1<CR><LF>
строка-для-поиска-2<CR><LF>
...
строка-для-поиска-n<EOF>



формат выходного файла: для каждого найденного вхождения отдельная строчка в двумя числами, разделёнными пробелами, первое число — позиция вхождения в файле начиная с нуля, второе число — номер поисковой фразы из списка начиная с нуля.

С моей (или не с моей, а просто со стороны) стороны — приложение, которое само генерирует тестовые файлы, тестовые фразы, само вызывает ваши exe-шники, передаёт им входные данные, проверяет правильность поиска, и самое главное, делает замер времени.

Каждый сможет прогнать тесты и сделать сравнение любых алгоритмов на своей собственной машине.

[ger_kar]

Клево! Я согласен. Т.е. как я понял, экзешник будет вообще без интерфейса, а input.txt и output.txt ему будут передаваться в командной строке.

[Хакер]

Зачем командная строка, пусть ищет в текущей рабочей папке файлы с такими именами.