Быстрый поиск по файлу

Сейчас на форуме: (+5 невидимых)

Посл.ответ	Сообщение
Zloy Ранг: 46.9 (посетитель) Активность: 0.02↘0 Статус: Участник	Создано: 29 июля 2007 00:15 · Личное сообщение · #1 Есть файл вида : 449A36B6689D841D7D27F31B4B7CC73A=aaron 187EF4436122D1CC2F40DC2B92F0EBA0=ab F740458218F30210F39A389B50287B07=aback 13F27B1072BBF7719D0D267B083FF91C=abacus 0ED4E356DDBE2FBF3D35D4AB1F31DE69=abase 623A150615F470135FF20B735C3F24FB=abash 0CD2269E449DEC70464BD16E373FCFE5=abate AB3358313EFB03210A1BABFB372246F1=abbey Размеров гига 2 нужно быстро произвести по нему поиск,кто может предложить какие алгоритмы буду оч благодарен

[HEX] Ранг: 467.7 (мудрец), 5thx Активность: 0.27↘0 Статус: Участник Иной :)	Создано: 29 июля 2007 00:28 · Поправил: [HEX] · Личное сообщение · #2 Zloy а в БД нормальную один раз перевести никак? Или обязательно в файле искать? Если по файлу искать, то быстро наврятли получиться я думаю все зависеть будет от винта (как быстро он сумеет читать строки). Либо блоками читать в оперативу и искать уже в оперативе. ----- Computer Security Laboratory
Zloy Ранг: 46.9 (посетитель) Активность: 0.02↘0 Статус: Участник	Создано: 29 июля 2007 00:33 · Поправил: Zloy · Личное сообщение · #3 Объясняю вкратце. Имеем структуру вида pass:hash, по 16 байт. итого 32. узнаем количество записей из размера базы. Пусть будет b. левая граница a=0, правая граница b открываем базу, упорядоченную по хэшам. Читаем запись из середины (a+b)/2. Если прочтенный хэш больше(как строка), то выбираем первую половину этого куска. т.е. сдвигаем правую границу на x, а если меньше - то левую на x. Устанавливаем x на (a+b)/2. Повторяем, пока не найдем результат, либо когда поймем, что нет записей. Тут чел вот написал мне,тока я чота непонялмож я тупой но без примера тут мне никак
Wyfinger Ранг: 52.1 (постоянный), 1thx Активность: 0.02↘0 Статус: Участник	Создано: 29 июля 2007 04:38 · Личное сообщение · #4 Поддерживаю предыдущего участника, только достаточно даже не польной сортировки, а еще проще - у Вас поиск и соответственно сортировака по хешам, т.е. один символ это либо цифра от 0 до 9, либо буква от a до f, всего 16 вариантов, Вы можете создать 16 списков и пройтись по исходному файлу, добавляя строки в список с сименем, с которого начинается хеш текущей строки. Периодически списки можно скидывать в файл и очищать, потом опять скидывать в режиме 'дописывания', чтобы не загружать оперативу. Потом все эти файлы склеить в единый. Получается сортировка по первым символам, она на порядок быстрее полной сортировки и использует намного меньше перемещений памяти. Для поиска Вам нужно найти номера строк, с которой начинается новый символ, это можно сделать прохожом по файлу, пропуская 1/16 числа строк, после гаждого шага, если после первого прохода все 16 строк, с которых начинается новые символы, весь алфавит не найден - искать уже между найденными с меньшим пропуском. Эту информацию (о строках с новыми символами в хеше) можно сохранить в отдельный файл - кеш, и начинать поиск с нужного смещения. В итоге поиск будет в 16 раз быстрее исходного, в то же время индексация намного быстрее полной сортировки и, самое главное, не столь критична к памяти. Я этот метод использую регулярно. Одна только проблема, актуальная и для моего метода и для полной сортировки - если в этот файл планируется постоянное добавление новых данных поиск будет весьма затруднительным, разве что скидывать новые данные в отдельный файл, пока его размер не привысит какой-то величины, а когда привысит - производть объединение и реиндексацию. Хотя тучшим вариантом было бы использование БД.
W[4Fh]LF Ранг: 56.3 (постоянный) Активность: 0.03↘0 Статус: Участник	Создано: 29 июля 2007 07:49 · Личное сообщение · #5 Что именно искать в файле надо?
YDS Ранг: 199.9 (ветеран), 4thx Активность: 0.12↘0.02 Статус: Участник	Создано: 29 июля 2007 08:19 · Личное сообщение · #6 Zloy пишет: Тут чел вот написал мне,тока я чота непонял Чел раписал тебе алгоритм поиска по упорядоченной по индексу базе данных. Это будет работать только если записи в файле ранжированы определенным образом. На пальцах: если, например, в файле есть нумерация строк: 1,2,3,4,5..10000 и нужно найти строку, скажем 550, то оптимальным алгоритмом будет такой: ставим указатель на середину файла - строку 500 и сравниваем: у нас больше (550>500), поэтому перемещаем указатель на середину второй половины файла - 750 и снова ссраниваем и т.д. Таким образом число итераций поиска всегда будет минимальным. Если записи в файле не упорчдочены - то чтение блоками через BlockRead и поиск нужного в прочитанном блоке.
NaumLeNet Ранг: 103.3 (ветеран), 8thx Активность: 0.06↘0 Статус: Участник	Создано: 29 июля 2007 10:22 · Поправил: NaumLeNet · Личное сообщение · #7 [delete]
gazlan Ранг: 170.1 (ветеран), 96thx Активность: 0.09↘0.01 Статус: Участник	Создано: 30 июля 2007 07:27 · Личное сообщение · #8 Zloy пишет: какие алгоритмы Любые варианты BM. aeee_29.07.2007_CRACKLAB.rU.tgz - Boyer-Moor searching algorithm.rar
sotona Ранг: 51.0 (постоянный) Активность: 0.03↘0 Статус: Участник	Создано: 30 июля 2007 10:06 · Личное сообщение · #9 Zloy пишет: 449A36B6689D841D7D27F31B4B7CC73A=aaron 187EF4436122D1CC2F40DC2B92F0EBA0=ab F740458218F30210F39A389B50287B07=aback 13F27B1072BBF7719D0D267B083FF91C=abacus 0ED4E356DDBE2FBF3D35D4AB1F31DE69=abase 623A150615F470135FF20B735C3F24FB=abash 0CD2269E449DEC70464BD16E373FCFE5=abate AB3358313EFB03210A1BABFB372246F1=abbey надо ли понимать, что присутствует некая отсортированность по второму столбцу? тогда классический бинарный поиск. поищи в инете binary search.
NaumLeNet Ранг: 103.3 (ветеран), 8thx Активность: 0.06↘0 Статус: Участник	Создано: 30 июля 2007 16:20 · Личное сообщение · #10 напоминает rainbow tables. может ТС стоит смотреть именно в их сторону?

Для печати