Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 115
Ох*еть, простите.
А тут что ох*енного, простите? То, что автор открыл для себя бинарный поиск? Даже школьники знают, что его сложность O(log n).
Я действительно не знал. Мне должно быть стыдно? Уже пол дня изучаю этот метод.
Да, если Вы не знали про двоичный поиск, то Вам должно быть стыдно.
Если бы меня кто то учил… Он мне просто не было нужен. По крайней мере я так думал.
Вас не учили логарифмам? Ну тогда вот вам еще одно откровение: поиск по массиву, размер которого равен количеству атомов во вселенной, потребует не более 266 операций сравнения. Даже на PHP.
По произвольному массиву? Что-то не верится.
По отсортированному массиву.
По неотсортированному — 2^266 операций на обычном компьютере, или 2^133 на квантовом.
По неотсортированному — 2^266 операций на обычном компьютере, или 2^133 на квантовом.
Время сортировки еще учтите и тогда будет все нормально ;)
Время сортировки такого объема — около пары часов, не больше.
Есть даже специальные соревнования по такой дисциплине, как сортировка больших объёмов данных.
Есть даже специальные соревнования по такой дисциплине, как сортировка больших объёмов данных.
Ого!
Найдите компьютер, способный хотя бы хранить 2^266 бит информации — и весь мир у Ваших ног.
Найдите компьютер, способный хотя бы хранить 2^266 бит информации — и весь мир у Ваших ног.
Да что вы накинулись? У меня специальность кинотехник, TimTowdy, давайте не будем, а? Если я не знал про бинарный поиск, не значит, что я не знаю ничего. Просто не сталкивался с этим.
А кто вообще говорил о 2^266 битах?
В статье — 70 гигабайт данных.
В статье — 70 гигабайт данных.
О 2^266 битах говорится здесь.
Метод половинного деления?
То, что сам бинарный поиск существует, действительно знает любой прошаренный школьник.
Для себя я открыл бинарный поиск в больших файлах, без необходимости загрузки содержимого в память.
Для себя я открыл бинарный поиск в больших файлах, без необходимости загрузки содержимого в память.
Называемый вами «бинарный поиск» имеет другое название, более точно его определяющее — дихотомический поиск.
Алгоритм такого поиска я писал на C# в консоли будучи студентом.
Алгоритм такого поиска я писал на C# в консоли будучи студентом.
Интересно на сколько будут отличаться результаты, если все это дело переписать на Си
скорость Сишных программ в 5 раз быстрее ПХПешных
но если переделывать, то надо использовать не только другой язык, но и немного другие методы:
про сортировку для подготовки данных я написал ниже.
данные ключей необходимо разбить на индекс и подиндекс.
подиндекс держать постоянно загруженным в памяти,
по нему вычислять номер индекного файла, а по индексному файлу,
определить смещение в файле данных.
для связи с WEB сервером используем протоколscgi
поиск будет занимать доли секунд. сам делал похожие штучки.
но если переделывать, то надо использовать не только другой язык, но и немного другие методы:
про сортировку для подготовки данных я написал ниже.
данные ключей необходимо разбить на индекс и подиндекс.
подиндекс держать постоянно загруженным в памяти,
по нему вычислять номер индекного файла, а по индексному файлу,
определить смещение в файле данных.
для связи с WEB сервером используем протоколscgi
поиск будет занимать доли секунд. сам делал похожие штучки.
Согласно приведенной автором табличке, C обгоняет PHP чуть больше чем в 2000 раз.
это во многом зависит как от используемого алгоритма, так и от используемого железа.
во первых в РНР очень много хорошо оптимизированных Сишных функций
во вторых, исходя из текста статьи компетенция автора — сомнительна как в алгоритмах,
так и в выборе инструментария.
программы с частыми операциями i/o на С не на много обгоняют РНР;
если на Си использовать технику паралельных вычислений, то можно добиться и большей производительности.
во первых в РНР очень много хорошо оптимизированных Сишных функций
во вторых, исходя из текста статьи компетенция автора — сомнительна как в алгоритмах,
так и в выборе инструментария.
программы с частыми операциями i/o на С не на много обгоняют РНР;
если на Си использовать технику паралельных вычислений, то можно добиться и большей производительности.
5 раз — это откуда цифра? Всё зависит от того, что вы хотите делать. У меня в одной программе, которая обращалась к большой двумерной табличке в цикле (а в PHP все массивы работают как хэш-таблицы) после грамотной оптимизации получился 200-кратный прирост скорости работы.
Позволю себе упомянуть свою статью: пишем PHP extension. Там просто есть некоторые цифры.
делал замеры для определенного круга задач
в среднем от 5 до 20 раз
я взял наихудший вариант
в среднем от 5 до 20 раз
я взял наихудший вариант
несомненно в вычислительных задачах — РНР проигрывает
ежу понятно.
ежу понятно.
По ходу прочтения у меня возник вопрос, а зачем вы все в 1 отсортированный файл пихаете?
Получается чтобы добавить 1 хеш придется все перестроить / пересортировать.
Раз вы получили фиксированную длину хеша, то можно разграничит диапазоны для каждого файла, сделав его на этапе создания по 2 ГБ. После сортировать можно в параллель. При бинарном поиске вы так же будете знать в каком файле (файлах) искать.
Но в тоже время Mysql неплохо справляется секционированием больших таблиц.
Получается чтобы добавить 1 хеш придется все перестроить / пересортировать.
Раз вы получили фиксированную длину хеша, то можно разграничит диапазоны для каждого файла, сделав его на этапе создания по 2 ГБ. После сортировать можно в параллель. При бинарном поиске вы так же будете знать в каком файле (файлах) искать.
Но в тоже время Mysql неплохо справляется секционированием больших таблиц.
Да, добавление одного хеша в моем случае требует полной перегенерации. Это большой минус, хотя для статичных данных это может быть в тему.
В первую очередь, мне было интересно узнать, как будет происходить поиск в большом файле. Наверное, из-за этого и получилась так, как получилось :)
В первую очередь, мне было интересно узнать, как будет происходить поиск в большом файле. Наверное, из-за этого и получилась так, как получилось :)
Можно было использовать 0 байт (лишь показуха) под все записи, расположив хеши в именах файлов в папке и используя поиск Windows Explorer)))
Переходите на x64
>> php -r 'echo PHP_INT_MAX;'
9223372036854775807
>> php -r 'echo PHP_INT_MAX;'
9223372036854775807
Радужные таблицы требуют нагрузки на процессор, соответственно не быстрый поиск.
А вы пробовали их применять?
Имхо, посчитать цепочку из 100 хешей будет быстрее, чем сходить за одним хэшом в память, а уж тем более на диск (у вас же не 75гб памяти?)
Имхо, посчитать цепочку из 100 хешей будет быстрее, чем сходить за одним хэшом в память, а уж тем более на диск (у вас же не 75гб памяти?)
p.s.: к тому же, входную цепочку можно заставить считать браузер. Да и выходную восстанавливать тоже.
Я к ним присматривался, но, если честно, не до конца понял, как они работают :)
Читая про них, я мне пришла идея убрать избыточные данные, сохраняя только часть хеша, а все пароли в отдельном файле.
Читая про них, я мне пришла идея убрать избыточные данные, сохраняя только часть хеша, а все пароли в отдельном файле.
Попробуйте перечитать и вынести хотя-бы обратное восстановление на клиента. Это очень сильно снизит объём вашей БД. А по скорости будет примерно так же.
Если ещё вынести генерацию и входной цепочки, то мне кажется, что будет даже быстрее.
Если ещё вынести генерацию и входной цепочки, то мне кажется, что будет даже быстрее.
Перескажу вам вкратце оригинальную статью Охслина.
0) H — наша хеш-функция. Например, мд5.
1) Множество паролей, для которых строится таблица, можно пронумеровать. функция R берёт хеш (как одно число) по модулю количество_паролей и использует результат как индекс в этом множестве паролей. (Радужность таблицы, на самом деле, подразумевает, что для таблицы с номером k к хешу мы ещё добавим k)
2) Возьмем произвольный хеш. Построим чейн: применим к хешу по очереди функции R и H, к результату применим их ещё раз, и так всего N раз. Получим какой-то хеш в самом конце. N называется длиной чейна. Первый и последний хеши сохраним в таблицу. Сделаем так M раз.
3) Отсортируем таблицу по второй колонке (где последние хеши), чтобы было удобнее дальше работать.
4) Время взломать хеш. Строим вышеописанным способом чейн, начиная с данного хеша. Для каждого из промежуточных хешей делаем следующее. Мы ищем его во второй колонке. Если найден, восстанавливаем чейн по хешу из первой колонки. Если нам повезло, то исходный текст для исходного хеша попадётся в ходе вычисления чейна. Если не вполне понятно, рекомендую нарисовать себе картинку: чейн для исходного хеша и чейн из таблицы, сдвинутые друг относительно друга (некий элемент первого совпадает с последним второго).
0) H — наша хеш-функция. Например, мд5.
1) Множество паролей, для которых строится таблица, можно пронумеровать. функция R берёт хеш (как одно число) по модулю количество_паролей и использует результат как индекс в этом множестве паролей. (Радужность таблицы, на самом деле, подразумевает, что для таблицы с номером k к хешу мы ещё добавим k)
2) Возьмем произвольный хеш. Построим чейн: применим к хешу по очереди функции R и H, к результату применим их ещё раз, и так всего N раз. Получим какой-то хеш в самом конце. N называется длиной чейна. Первый и последний хеши сохраним в таблицу. Сделаем так M раз.
3) Отсортируем таблицу по второй колонке (где последние хеши), чтобы было удобнее дальше работать.
4) Время взломать хеш. Строим вышеописанным способом чейн, начиная с данного хеша. Для каждого из промежуточных хешей делаем следующее. Мы ищем его во второй колонке. Если найден, восстанавливаем чейн по хешу из первой колонки. Если нам повезло, то исходный текст для исходного хеша попадётся в ходе вычисления чейна. Если не вполне понятно, рекомендую нарисовать себе картинку: чейн для исходного хеша и чейн из таблицы, сдвинутые друг относительно друга (некий элемент первого совпадает с последним второго).
Поиск там ровно такой же, просто радужная таблица меньше, чем полная таблица перебора всех паролей. Генерить её дольше, но искать в итоге по меньшему объёму данных.
«prepair» резануло глаз.
C помощью javascript?! Забавно будет подсовывать всем клиентам небольшой кусок данных и javascript. Эдакое клиент-серверное распределение :D
статья похожа на сгенерированную сеошниками для поисковых машин, читать и понять что к чему сложновато.
А если вам надо быстро что-то найти в 75Gb посмотрите с сторону Map/Reduce, Hadoop, ваша задача туда хорошо ложиться
А если вам надо быстро что-то найти в 75Gb посмотрите с сторону Map/Reduce, Hadoop, ваша задача туда хорошо ложиться
Мисье знает толк в толковых извращениях.
Теперь осталось попробовать сотворить тоже самое на своём сервере, или сервере друга :D.
Автору зачёт, ещё по твоим мануалам учился настраивать pvpgn :)
Теперь осталось попробовать сотворить тоже самое на своём сервере, или сервере друга :D.
Автору зачёт, ещё по твоим мануалам учился настраивать pvpgn :)
А причем тут PHP? В статье C# встречается чаще чем PHP…
И вообще какой вывод должны сделать читатели прочитавшие статью? Что у вас все получилось?
Как то бесполезно…
И вообще какой вывод должны сделать читатели прочитавшие статью? Что у вас все получилось?
Как то бесполезно…
и исходников с алгоритмом нету )
pastebin.com/S1jWxQGt
pastebin.com/rTty0cRx
Но без файлов таблиц не думаю, что это представляет большой интерес.
pastebin.com/rTty0cRx
Но без файлов таблиц не думаю, что это представляет большой интерес.
На C# сделана вся подготовка бинарных файлов. А PHP потому, что поиск реализован на нем. Могу выложить и исходник на PHP, но ведь подробнее об этом написано в разделе «поиск».
Я думаю, что отсюда могут пригодиться некоторые идеи. То, как сделан сам поиск, или перенос нагрузки на клиента.
Я думаю, что отсюда могут пригодиться некоторые идеи. То, как сделан сам поиск, или перенос нагрузки на клиента.
немного не понял.
это статья о том как крут бинарный поиск?
ну да, он крут, и...?
это статья о том как крут бинарный поиск?
ну да, он крут, и...?
> это статья о том как крут бинарный поиск?
Автор выяснил, что бинарный поиск крут на больших количествах данных, даже если они предствалены в виде обычных планарных файлах.
Автор так же выяснил, что для реализации бинарного поиска на больших объемах данных достаточно стандартных дервних файловых функций fopen(), fseek(), fread().
Так же он выяснил, что при применении правильного алгоритма для решения задачи, неважно на каком языке реализован алгоритм — хоть на PHP, хоть на C, разница в скорости небольшая — C оказался быстрее всего в два раза.
Это бесценный опыт на самом деле, и он поможет автору в дальнейшем правильно смотреть на новые технологии незамыленным взглядом.
Автор выяснил, что бинарный поиск крут на больших количествах данных, даже если они предствалены в виде обычных планарных файлах.
Автор так же выяснил, что для реализации бинарного поиска на больших объемах данных достаточно стандартных дервних файловых функций fopen(), fseek(), fread().
Так же он выяснил, что при применении правильного алгоритма для решения задачи, неважно на каком языке реализован алгоритм — хоть на PHP, хоть на C, разница в скорости небольшая — C оказался быстрее всего в два раза.
Это бесценный опыт на самом деле, и он поможет автору в дальнейшем правильно смотреть на новые технологии незамыленным взглядом.
сортирует файл за один проход
Т.е. сортировка O(n)? ))… Прорыв в теории алгоритмов ?? ))
Т.е. сортировка O(n)? ))… Прорыв в теории алгоритмов ?? ))
у меня было тестовое задание — отсортировать 109 строк по 8 цифр( 87Гб)
решалось банально просто: файл бился на 1024 кусков (где-то по 1 млн строк),
каждый из них сортировался, далее происходило слияние парами.
Эти части вполне реально распаралелить.
Сортировка заняла около 7-15х мин.
практически можно подобрать соотношение: кол-во кусков/размер.
В зависимости от процессора и памяти может 8192 или 16384 куска обработать быстрее, чем 1024
программа использовала метод qsort и была реализована на С++
может научимся БД использовать как хранилище данных, а не забивать микроскопом гвозди
Объемы раз в 10 превышающие ваши хеши.
решалось банально просто: файл бился на 1024 кусков (где-то по 1 млн строк),
каждый из них сортировался, далее происходило слияние парами.
Эти части вполне реально распаралелить.
Сортировка заняла около 7-15х мин.
практически можно подобрать соотношение: кол-во кусков/размер.
В зависимости от процессора и памяти может 8192 или 16384 куска обработать быстрее, чем 1024
программа использовала метод qsort и была реализована на С++
может научимся БД использовать как хранилище данных, а не забивать микроскопом гвозди
Объемы раз в 10 превышающие ваши хеши.
Реализации на разных языках доступны для загрузки harpywar.pvpgn.pl/?do=hashежу понятно,
Очевидно, что на Си быстрее всего.
так как в других языках используют либо бинд этой функции, либо ее реализуют своими средствами
Хм. BST же (двоичное дерево поиска).
Вы не пробовали арифметический поиск? Поскольку хеши довольно случайны, то он должен дать значительное уменьшение операций чтения с диска.
Табличка у Вас, конечно, хорошая.
График у Вас совершенно замечательный:) Только должен он выгляеть так.
Табличка у Вас, конечно, хорошая.
График у Вас совершенно замечательный:) Только должен он выгляеть так.
Имхо, уже некуда уменьшать количество операций чтения с диска. Подскажите, где почитать про арифметический поиск? Поиск в гугле дает только ссылку на Ваш комментарий)
Хм, не думал, что это столь редкое название:)
Упс, коммент рано отправился.
Правильное его название — интерполяционный поиск
Правильное его название — интерполяционный поиск
Ага, особенно хорошо он работает на данных вроде списка степеней двойки.
Спойлер: O(N) в этом (худшем) случае.
Спойлер: O(N) в этом (худшем) случае.
Если у Вас хеши паролей — это степени двойки, то Вы пользуетесь либо очень странными паролями, либо очень странной хеш-функцией.
Для «хорошей» криптографической хеш0функции на «нормальных» входных данных результат распределен более-менее равномерно. Что дает нам O(log log N) запросов.
Как Вы думаете, стоит ли попробовать сделать топик, в котором будут сравниваться разные способы решения этой задачи?
Для «хорошей» криптографической хеш0функции на «нормальных» входных данных результат распределен более-менее равномерно. Что дает нам O(log log N) запросов.
Как Вы думаете, стоит ли попробовать сделать топик, в котором будут сравниваться разные способы решения этой задачи?
С CDB не сравнивали ваше решение?
У меня есть предположение, что CDB уже устаревшая технология, которая мало где используется, тем более для больших объемов данных.
Напишите, если это не так.
Напишите, если это не так.
Это не так. Чтобы технология устарела, ей что-то на замену прийти должно. Вы знаете что-то более быстрое?
Увы, не доводилось использовать CDB, поэтому не могу сравнивать и говорить про скорость.
Есть у Вас есть ссылки на сравнительные тесты с другими БД, и информация о том, где её лучше использовать — это будет интересно посмотреть.
Есть у Вас есть ссылки на сравнительные тесты с другими БД, и информация о том, где её лучше использовать — это будет интересно посмотреть.
Да она простая очень, вот почитайте: cr.yp.to/cdb.html
Там же есть стоимость операций, посмотрите, станет всё понятно.
Там же есть стоимость операций, посмотрите, станет всё понятно.
А вы уверены что SQLite такой быстрый?)
Alexey Pechnikov. подсказывает, что SQLite поиск по хэшу выполняется со скоростью порядка десятков тысяч операций в секунду на БД размером в 100 Гб на десктопе уровня коре квадро.
Цитирую письмо:
Цитирую письмо:
Надо было так:
CREATE VIRTUAL TABLE t USING fts4(hash TEXT, password TEXT);
Искать как:
select * from t where hash math '...';
Смысл в том, что fts4 использует индексное мультидерево и нет деградации скорости вставки на больших таблицах, при сохранении высокой скорости поиска. Впрочем, даже при обычном индексе на поле хэша вы должны были получить быстрый поиск и медленную вставку, но никак не медленный поиск. Попробуйте взять мою сборку эскулайт
sqlite.mobigroup.ru/home
Тест поиска (на нетбуке) можете посмотреть здесь
geomapx.blogspot.com/2010/01/sqlite-fts3.html
Вот здесь есть тест с генерацией БД, для изучения скорости вставки
book.mobigroup.ru/dir?ci=c9fc797c01deb246&name=web_project_DBMS/distributed_schema
См. файлы perftest_log_* с результатами теста на разных носителях.
≈4½ года спустя я наткнулся на этот комментарий и оставляю к нему исправление: в письме Печникова весьма вероятна опечатка, так как в пособии по употреблению FTS3 и FTS4 кодовым словом служит не «math», а «match».
Интересно, а много нашлось таких, кто решили проверить свои пароли, а для получения хэшей воспользовались этим же сайтом, который вполне мог добавить в словарь (базу) их пароли?
закончил читать после сообщения о том, что в тотал коммандере нельзя разбить файл с точностью до байта.
Хa! Уже в который раз на Хабре сталкиваюсь с упертыми людьми (в комментариях), которые в подобных случаях предлагают бинарный поиск. Видимо, в вузах дальше него ничего не изучают. Бинарный поиск отнюдь не хорош, так как требует постоянных вызовов fseek() и дерганий головкой HDD. А при реализации в памяти — требует громоздкую уродливую структуру с кучей указателей (кто любит указатели?). По моему, это какая-то устаревшая структура данных из 60-х.
В данным случае (поиск по огромному количеству хешей) надо использвоать хеш-таблицу. Эта замечательная технология, например, применяется в не менее замечательном PHP. Она позволяет рещить задачу, используя только 2 вызова fseek64() и чтение порядка 8 Кб данных. Естественно, с этим примитивным бинарным поиском такого никогда не достичь.
Реализуется она примерно так:
1) определяем нужный нам объем индексного файла. У нас был 190 Гб файл с паролями+хешами, значит там примерно 5 млрд. паролей. Пусть на 1 entry в индексе приходится в среднем 300 паролей (они займут как раз что-то оклоло 4-8 Кб — пара секторов на диске) — значит нам нужен индекс на 16 млн значений (16M * 300 = 5 млрд).
2) придумываем хеш-функцию hash(), которая из 32-символьного хеша делает 24-битное значение. В данном случае эта функция простая: просто берем первые 24 бита хеша (первые 6 символов):
hash(«1234006f7865...») -> 0x123400
3) В индексный файл (index) пишем подряд 6-байтные оффсеты в файле с паролями для каждого хеша:
offset_000000 (смещение, по которому хранится блок, а в нем все пароли, с хешами начинающимися на 000000)
offset_000001 (то же для хешей с 000001)
…
offset_ffffff
Размер индексного файла получается 16 Mb * 6 = 96 Mbytes
4) Разбиваем пароли на блоки, в каждом блоке пароли, хеши которых начинаются с одних и тех же 6 символов.
5) Ну и в файл с паролями (data) пишем эти блоки (длина блока + magic number + содержимое): либо разделенные символом \0 пароли, либо структуры(длина пароля + пароль), либо пароли с хешами (чтобы не вычислять эти 300 хешей).
Для поиска достаточно сделать следущее:
Берем первые 6 символов хеша, преобразуем их в unsigned long:
hashOfHash = getFirst24bit(hash)
Делаем fseek() в индексном файле на hashOfHash * 6 (размер поля offset_*). Читаем оттуда 6 байт — это смещение блока в основном файле (data), где хранятся пароли, хеши которых начинаются с этих цифр. Читаем блок (он должен быть порядка 4-8 Кб, так что можно сразу читать 8 Кб, и если блок длиннее, читать вторым запросом остальное).
Ну а прочитав блок, уже можно по нему подбирать пароли, или, если мы храним и хеши этих паролей, то просто сравнитьи выбрать нужный.
Автор, не хотите попробовать реализовать?
И да, кстати насчет сортировок и разбиений файлов: если бы вы использвоали linux, то обнаружили бы что там есть и средства для сортировки больших файлов, и для разбиения. Все это давно написано и оттестировано, и всяко лучше самодельного велосипеда.
В данным случае (поиск по огромному количеству хешей) надо использвоать хеш-таблицу. Эта замечательная технология, например, применяется в не менее замечательном PHP. Она позволяет рещить задачу, используя только 2 вызова fseek64() и чтение порядка 8 Кб данных. Естественно, с этим примитивным бинарным поиском такого никогда не достичь.
Реализуется она примерно так:
1) определяем нужный нам объем индексного файла. У нас был 190 Гб файл с паролями+хешами, значит там примерно 5 млрд. паролей. Пусть на 1 entry в индексе приходится в среднем 300 паролей (они займут как раз что-то оклоло 4-8 Кб — пара секторов на диске) — значит нам нужен индекс на 16 млн значений (16M * 300 = 5 млрд).
2) придумываем хеш-функцию hash(), которая из 32-символьного хеша делает 24-битное значение. В данном случае эта функция простая: просто берем первые 24 бита хеша (первые 6 символов):
hash(«1234006f7865...») -> 0x123400
3) В индексный файл (index) пишем подряд 6-байтные оффсеты в файле с паролями для каждого хеша:
offset_000000 (смещение, по которому хранится блок, а в нем все пароли, с хешами начинающимися на 000000)
offset_000001 (то же для хешей с 000001)
…
offset_ffffff
Размер индексного файла получается 16 Mb * 6 = 96 Mbytes
4) Разбиваем пароли на блоки, в каждом блоке пароли, хеши которых начинаются с одних и тех же 6 символов.
5) Ну и в файл с паролями (data) пишем эти блоки (длина блока + magic number + содержимое): либо разделенные символом \0 пароли, либо структуры(длина пароля + пароль), либо пароли с хешами (чтобы не вычислять эти 300 хешей).
Для поиска достаточно сделать следущее:
Берем первые 6 символов хеша, преобразуем их в unsigned long:
hashOfHash = getFirst24bit(hash)
Делаем fseek() в индексном файле на hashOfHash * 6 (размер поля offset_*). Читаем оттуда 6 байт — это смещение блока в основном файле (data), где хранятся пароли, хеши которых начинаются с этих цифр. Читаем блок (он должен быть порядка 4-8 Кб, так что можно сразу читать 8 Кб, и если блок длиннее, читать вторым запросом остальное).
Ну а прочитав блок, уже можно по нему подбирать пароли, или, если мы храним и хеши этих паролей, то просто сравнитьи выбрать нужный.
Автор, не хотите попробовать реализовать?
И да, кстати насчет сортировок и разбиений файлов: если бы вы использвоали linux, то обнаружили бы что там есть и средства для сортировки больших файлов, и для разбиения. Все это давно написано и оттестировано, и всяко лучше самодельного велосипеда.
[sarcasm]Ха! Уже в который раз на Хабре сталкиваюсь с людьми, уверенными, что хеши — панацея от всего и вся[/sarcasm]
Cчитав порядка 8кб данных с помощью бинпоиска можно найти один из 2^(8кбайт / 32 байт) = 2^256 ключей размером 32 байта каждый.
Уродливым он выглядит только будучи написанным криво. Посмотрите, например, реализацию в вики — она проста и прекрасна.
Нет, хеши сильны. Очень сильны. На практике, если против нас не работает Мерлин, они во многих случаев действительно лучше чем что бы то ни было другого.
В данном случае вполне может оказаться очень хорошо работающим интерполяционный поиск. А может и не оказаться. Надо смотреть и проверять.
Кроме того, не забываем про специально придуманные для работы с внешней памятью B-деревья.
Если будет время и будет не лень — попробую аккуратно написать все варианты:)
PS. А SSD не решают проблему дерганья головки?
Cчитав порядка 8кб данных с помощью бинпоиска можно найти один из 2^(8кбайт / 32 байт) = 2^256 ключей размером 32 байта каждый.
Уродливым он выглядит только будучи написанным криво. Посмотрите, например, реализацию в вики — она проста и прекрасна.
Нет, хеши сильны. Очень сильны. На практике, если против нас не работает Мерлин, они во многих случаев действительно лучше чем что бы то ни было другого.
В данном случае вполне может оказаться очень хорошо работающим интерполяционный поиск. А может и не оказаться. Надо смотреть и проверять.
Кроме того, не забываем про специально придуманные для работы с внешней памятью B-деревья.
Если будет время и будет не лень — попробую аккуратно написать все варианты:)
PS. А SSD не решают проблему дерганья головки?
> Cчитав порядка 8кб данных с помощью бинпоиска можно найти один из 2^(8кбайт / 32 байт) = 2^256 ключей размером 32 байта каждый.
Ага, только это будет 24 операции seek и 24 чтения из разбросанных по всему диску местам, против 1 seek и 1 чтения из индекса в моем случае. SSD уменьшает время поиска, но алгоритм все равно остается неэффективным из-за ненужных лишних чтений. Хеш-таблица в данном случае — оптимальное решение.
В данном случае хеш-таблица требует в разы (в 24 раза?) меньше операций поиска и чтения. Хеш-табица, правда, отличие от дерева, не позволяет делать сравнения по диапазону (>/
Ага, только это будет 24 операции seek и 24 чтения из разбросанных по всему диску местам, против 1 seek и 1 чтения из индекса в моем случае. SSD уменьшает время поиска, но алгоритм все равно остается неэффективным из-за ненужных лишних чтений. Хеш-таблица в данном случае — оптимальное решение.
В данном случае хеш-таблица требует в разы (в 24 раза?) меньше операций поиска и чтения. Хеш-табица, правда, отличие от дерева, не позволяет делать сравнения по диапазону (>/
И еще хеш-таблица (в предложенном Вами варианте) обладает очень медленным временем добавления. Если мы хотим уметь добавлять данные — то дерево — единственный выход.
Ну насчет добавления данных (в определенных пределах) — можно извратиться, например при добавлении пароля в блок, дописывать этот обновленный блок в конец data-файла, менять 1 оффсет этого блока в индексе, а старый кусок блока помечать где-нибудь как свободную память. Индексный файл расти не должен, расти будет только data-файл. Ведь и с деревьями не все так просто, их надо балансировать, а каждая операция перестановки вершин требует обновления в 2 участках файла, которые, скорее всего будут в разных секторах диска, а таких операций надо иногда делать отнюдь не одну.
Но все же хеш таблицы в той же MySQL не используют (для диска) — видимо, есть какая-то причина. Или просто реализовать было лень?
Но все же хеш таблицы в той же MySQL не используют (для диска) — видимо, есть какая-то причина. Или просто реализовать было лень?
Думаю лет через 5-10 твердотельные накопители будут преобладать над дисковыми.
И бинарный поиск не будет таким уж накладным на уровне обращения к дисковой памяти.
И бинарный поиск не будет таким уж накладным на уровне обращения к дисковой памяти.
> Я написал на C# простенькую утилиту, читающую исходный файл по байтам и складывающую их последовательно в отдельные файлы заданного размера.
На что только не идут люди, чтобы не пользоваться юниксовыми утилитами… MSYS принесет столько чудных открытий!
На что только не идут люди, чтобы не пользоваться юниксовыми утилитами… MSYS принесет столько чудных открытий!
На PHP есть проецирование файлов в память?
Проецирование файлов в память это ведь не средство языка, а механизм операционной системы. У PHP другие задачи, по сравнению с другими языками.
Ну да, неверно выразился. Я имел ввиду возможна ли эта операция средствами стандартной библиотеки? Проецирование файлов в память никогда лишним не будет. Даже в .NET наконец-то сделали))
В арсенале Windows, как ни странно, такой утилиты нету. В тоталкомандере нельзя разбить по байтам, а мне нужна была точность.
Я написал на C# простенькую утилиту, читающую исходный файл по байтам и складывающую их последовательно в отдельные файлы заданного размера.
OMG, только не велосипед!
качаем Win32 порт coreutils в котором есть
split: split a file into pieces
впрочем, там полно и других не менее полезных консольных утилит, заимствованных из GNU
Проще написать утилиту на C, которая будет заниматься темже самым, прописать ей нужные права и запускать с параметрами из php.
Вам проще на С. Я бы мог написать под ASP.NET или Mono. Не суть.
Этот комментарий полностью отражает то, что я хотел показать в топике.
Этот комментарий полностью отражает то, что я хотел показать в топике.
не пробовали реализовать на Google Go?
А чтобы перебор не помог нало использовать bcrypt и солить его SHA-512 в несколько итераций, чтобы генерирование нужного хеша занимало, ну, например полсекунды.
Пароли надо ШИФРОВАТЬ а не хешировать, хэширование рассчитано на быстрое вычисление хэша, а нам как раз этого и не надо.
Пароли надо ШИФРОВАТЬ а не хешировать, хэширование рассчитано на быстрое вычисление хэша, а нам как раз этого и не надо.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Мгновенный поиск в 75 гигабайтах