| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Delphi: Для новичков > Радужная таблица |
| Автор: кмс 13.1.2014, 17:40 |
| Здравствуйте. Нужно создать базу, в который записывается результат пересчета 5 байт, или проще нужно пересчитать 1099511627775 вариантов и результат каждого варианта записать в базу(обычный бинарный файл). Каждый вариант занимает 11 байт. База получается огромная. Мне посоветовали посмотреть в сторону радужных таблиц. Прежде чем начать изучать тему может кто нибудь посоветует. Подойдут ли эти таблицы для моего случая. Вот примерный вариант базы http://s019.radikal.ru/i640/1401/03/2f215236cac5.png 1 и 2 это данные по которым будет искаться то что отмечено под 3. Вернее будет искаться только то что под 1, если находится то с данными под 2 будет производиться некая операция и если все сходится то поиск окончен. Вообщем нужен совет, можно ли в данном случае применить радужную таблицу? |
| Автор: кмс 13.1.2014, 20:42 |
| Если есть специалисты по этой теме, готов оплатить потраченное время на создание такой таблицы. Вернее не на создание, там уйму времени уйдет, а на написание проги для ее создания. |
| Автор: Illusion Dolphin 13.1.2014, 22:50 |
| 1099511627775 * 11 = 11 терабайт данных. Зачем вам записывать куда-то столько данных, если их можно рассчитать? Что вообще надо делать? Ну создали вы базу, а затем какие операции надо? Для чего это вообще делается? |
| Автор: kami 14.1.2014, 22:35 | ||||
+ служебная информация, индексы...
Даже если принять, что создание 1 записи займет 1 миллисекунду, один компьютер будет писать данные 34 года. Если предположить, что увеличение числа компьютеров даст линейный прирост скорости (на самом деле - несколько меньше), то чтобы получить 1 месяц нужно 408 компов (ну, ладно - все они четырехядерные, тогда - 102) А теперь, внимание - исходя из Вашего "на порядок дольше" и моего предположения в "1 мс" получается, что поиск значения должен вестись максимум за 0,1 мс??? Имхо, тут никакие индексы, партицирование и т.п. не помогут... хотя партиции - это вариант, но отца русской демократии они не спасут. Где у меня ошибка в расчетах? Ну и плюс ко всему - минимум 11 терабайт... многовато будет.
А не может такого быть, что эти базы содержат (дальше - полет фантазии) к примеру - промежуточные значения вычислений? или конечные, но с каким-нибудь шагом? Программа выбирает нужное ей и производит до-обработку или "интерполяцию значений, максимально близких к требуемому" (которая как раз и занимает основное время из 10-15 минут) ? Добавлено @ 22:44 Если использовать при расчетах не 1 миллисекунду, а (15-20 минут)*10, то итоговые значения получаются вообще неадекватными. Посему - не думаю, что в аналогах эта задача решалась "в лоб". |
| Автор: boobie 15.1.2014, 09:37 | ||
| kami, ошибся в расчетах Запилил программку с тремя потоками, каждый поток генерирует одиннадцатибайтовые числа от 10000000000 до 10001000000 в простом цикле. Все, что сгенерировал - кидает в массив. Цикл проходит за доли секунды, даже не могу отловить этот момент. Затем каждый поток записывает свой массив в файл. На запись 3-х файлов по 1 млн. одиннадцатибайтовых чисел (в каждый) ушла минута. Сама запись идет долго, но я думаю, что тут можно как-нибудь оптимизировать процесс. Сделать ассемблерные вставки, использовать нестандартные функции или еще что-нибудь. И да, процессор 6-летней давности не был загружен на всю катушку. И это все на гражданских Дельфях, в простых потоках с "синхронайзом" и записью с помощью writeln
|
| Автор: kami 15.1.2014, 10:53 | ||||
Где? Этот пример - не показатель (несмотря на то, что в нем де-факто не используются потоки) , я отталкивался от утверждений и
В примере же сами вычисления, с учетом всяческих ухищрений в современных процессорах (за исключением строки
|
| Автор: boobie 15.1.2014, 11:14 |
| Потоки позволяют использовать все возможности многоядерных процессоров. Я создал 3 экземпляра данного класса, установив им разные флажки. Я о том, что ни о каких 34 годах речь не идет) Максимум - полгода) А вот поиск по 10Тб базе - это да, это вопрос. Наверно для майнинга такие штуки нужны... Или аккаунты ВК ломать |
| Автор: kami 15.1.2014, 11:27 | ||
Это не относится к делу, но в Вашем коде не используюется многопоточность. Весь код выполняется в основном потоке. Если желаете продолжить дискуссию на эту тему - давайте вернемся http://forum.vingrad.ru/forum/topic-375281.html А по теме - ТС утверждает, что создание каждой 11-байтной записи очень ресурсоемкая операция. Я привел расчеты. Единственным "узким" местом в моем сообщении было получение 34 лет. Расшифрую: 1099511627775 / 1000(мс) /60(сек)/60(мин)/24(час)/365(дней) = 34,8 лет. Вы утверждаете, что они не верны. Приведите доказательства. |
| Автор: кмс 15.1.2014, 11:38 |
| Вот делал специально программку что бы сравнивать разницу между поиском и перебором. Может быть там и не совсем точно, так как при поиске не учитываются некоторые нюансы, но и отклонения не столь существенные. http://www.sendspace.com/file/cny0tv PS: конечное значение это сколько вариантов перебирать. Это число делиться на количество потоков и каждый поток работает со своим отрезком. А так пробовал создавать базу, у меня 300мб (три потока каждый по 100мб) создавались примерно 30-40 минут, точнее не скажу, врубил и пошел телек смотреть, так заглядывал нет нет. Но и поиск будет не по всей базе. Например можно рассортировать по первому байту искомого, и того получается 255 баз, прога сразу будет искать в нужной базе. |
| Автор: kami 15.1.2014, 11:45 |
А где оно ищет, если не секрет? Что-то слишком быстро проходит поиск, без разницы что я задам в поле "конечное значение" |
| Автор: кмс 15.1.2014, 11:55 | ||
Ну там в поиске просто сравнение
не учитывается загрузка базы и лазанье по ней, но и при переборе тоже это все не учитывается, прогу делал просто сравнить примерно разницу между поиском и перебором. Добавлено через 2 минуты и 11 секунд Ты введи все 5 байт - 1099511627775 Добавлено через 11 минут и 51 секунду Вот скрин, это поиск по всем вариантам. http://s005.radikal.ru/i210/1401/65/5093ca998501.png Но как говорил выше реальный поиск по все базе конечно будет дольше, но и если учитывать что искать во первых будет не по все базе, во вторых все таки не обязательно что придется искать до конца, наткнутся на искомое может в любое время |
| Автор: boobie 15.1.2014, 12:10 | ||||||||
kami, да ну! В одном потоке? Я привел класс потока:
Код с формой и запуском потоков такой (если интересно):
И он немного долбанутый, особенно таймер не к месту... Ну да пофиг, сделал его за 2 минуты... Создается 3 объекта того класса. А по поводу времени
За 1 мс моя прога делает 50 записей. И, я повторюсь, этот процесс можно ускорить, поэтому
это можно смело делить на 50. Вся проблема будет только в организации работы всей базы и поиском. |
| Автор: kami 15.1.2014, 12:24 |
Весь код Вашего потока заключен в выполнении Synchronize. Если нажать F1, то выяснится, что Synchronize выполняет код в контексте основного потока (или потока-родителя, в зависимости от версии Delphi). Методы переключения контекста (емнип) разнятся так же в зависимости от версии Delphi. Все три потока при создании выполняют одно действие - пытаются переключиться в контекст основного потока приложения. И уже после переключения выполняется анонимный метод. Вывод: сколько бы таких потоков ни было создано, выполнение будет идти в контексте одного, что сразу сводит на нет необходимость их создания. Емнип, такой подход встречался в книгах Фленова (не к ночи будет помянут) и основанных на его книгах примерах. Совет: выкиньте эти книги и почитайте для начала хотя бы статью на Винграде. |
| Автор: кмс 15.1.2014, 12:29 |
| Можно конечно уменьшить базу и без всяких таблиц. Например писать в нее только первые 6 байт, а искомые 5 байт будут адрес / 6 Но все равно база большая получается и не получится ее отсортировать, хотя и над сортировкой тоже в принципе можно подумать. |
| Автор: kami 15.1.2014, 12:35 |
Это понятно, и если данные будут отсортированы хотя бы по первому значению, это уже значительно упростит поиск вне зависимости от выбора хранилища, особенно если разделить данные по этому признаку (к примеру - разные файлы, или для СУБД - разделы) |
| Автор: boobie 15.1.2014, 12:37 |
| Ой, блин, сорри... Да, я реально помешан на этом синхронайзе=( Убрал все обращения к форме, убрал секцию синхронайз... Теперь 34Кб данных (3000000 одиннадцатибайтовых чисел) генерируются за 2.8 секунды! 34 года надо разделить на 500 |
| Автор: kami 15.1.2014, 12:42 | ||
Вы так и не опровергли мои расчеты Если исходить из Ваших скоростей "генерации" 11-байтных значений, то в создании базы нет смысла - проще использовать "онлайн"-расчет. |
| Автор: кмс 15.1.2014, 12:44 | ||||
Плюс еще разделить на количество компов, хозяева которых просто не дождутся когда придется считать В принципе если уменьшить базу до 5 терабайт(способом который я описал выше), уже можно хотя бы делать онлайн базу, что честно говоря не очень бы хотелось, ну и как поведет себя сервер с поиском если например будут одновременно 100-500 запросов. Так что все таки придется изучать эти rainbow tables Добавлено через 4 минуты и 19 секунд
Не совсем понял про что вы, но создание базы пусть хоть и займет много времени, но создавать она будет только один раз. Потом только поиск по ней, а это уже в разы быстрее. |
| Автор: boobie 15.1.2014, 12:54 | ||
| kami, я не спорю, потому как не знаю скорость поиска по такой базе... Вполне возможно, что искать будет дольше, чем генерировать. Я просто говорил о том, что сама генерация не займет 34 года. Гораздо, гораздо меньше.
Осталось собрать RAID на 11Тб |
| Автор: кмс 15.1.2014, 12:56 |
| Да как поиск может занять больше времени чем генерирование? Наоборот на много быстрее. |
| Автор: boobie 15.1.2014, 13:12 | ||
Смотря как его реализовать |
| Автор: кмс 15.1.2014, 13:14 | ||
Да даже если вести поиск простым перебором по базе, все равно быстрее. |
| Автор: kami 15.1.2014, 13:15 |
Легко. Время поиска зависит от объема данных (тут вступает в силу организация хранения данных и сами алгоритмы поиска, но тем не менее - зависит). А вот генерация чаще всего имеет стабильное время на одно значение (ок, в Вашем (кмс) коде это не так). |
| Автор: кмс 15.1.2014, 13:21 | ||
Дело в не организации поиска. Генерация пусть хоть и имеет "стабильное время на одно значение", но оно отнимает слишком много времени на расчеты. Добавлено @ 13:25 Там же не просто генерируются случайные значение, а именно идут расчеты при двух входных параметров каждый по 5 байт. А так как на выходе мы имеем результат из 3 байт, то получается не очень маленький процент совпадений, по этому приходится считать по 2 раза(один из входных параметров меняем). В итоге получаем что для одной записи в базу нужно вести 2 расчета. |
| Автор: Агрох 15.1.2014, 13:34 |
| Какой то у вас полупредметный разговор выходит. кмс, напиши, сколько времени уходит на одну генерацию. Минимум, максимум, в среднем (чаще всего). |
| Автор: кмс 15.1.2014, 13:38 | ||||
| Агрох, я чуть выше выложил прогу, там можно примерно посмотреть сколько ведется расчет. Там нету сохранения в файл, просто чистый расчет. Добавлено @ 13:40 Вот перебор 10000 значений.
4 ядра, 4 потока, проц i5 для 100000
|
| Автор: kami 15.1.2014, 14:14 |
| кмс, хорошо, раз Вы считаете, что поиск будет быстрее - "да будет так". Ввиду того, что я не работал с "радужными таблицами" и не могу оценить целесообразность их использования, мой вариант решения задачи "в лоб" - сделать таблицу с разделением (partitions) по первому значению и индексами по полям, по которым будет производиться выборка. http://dev.mysql.com/doc/refman/5.5/en/partitioning.html. UPD. Только учтите, что индексы увеличат объем базы, так что к первоначальным 5Тб (я про "сокращенный вариант базы) добавится еще ... а вот сколько - зависит от СУБД. |
| Автор: DYUMON 18.1.2014, 17:23 |
| не проще бесплатную радужную таблицу скачать ? типа такого http://www.project-rainbowcrack.com/table.htm |