Здравствуйте.
Нужно создать базу, в который записывается результат пересчета 5 байт, или проще нужно пересчитать 1099511627775 вариантов и результат каждого варианта записать в базу(обычный бинарный файл). Каждый вариант занимает 11 байт. База получается огромная.
Мне посоветовали посмотреть в сторону радужных таблиц. Прежде чем начать изучать тему может кто нибудь посоветует.
Подойдут ли эти таблицы для моего случая.
Вот примерный вариант базы http://s019.radikal.ru/i640/1401/03/2f215236cac5.png 
1 и 2 это данные по которым будет искаться то что отмечено под 3.
Вернее будет искаться только то что под 1, если находится то с данными под 2 будет производиться некая операция и если все сходится то поиск окончен.
Вообщем нужен совет, можно ли в данном случае применить радужную таблицу?


Это сообщение отредактировал(а) кмс - 13.1.2014, 17:40

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

1099511627775  * 11 = 11 терабайт данных. Зачем вам записывать куда-то столько данных, если их можно рассчитать? Что вообще надо делать? Ну создали вы базу, а затем какие операции надо? Для чего это вообще делается?

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

База нужна для хранения готовых расчетов. Я уже объяснил выше немного принцип.
База состоит из трех значений, два по три байта и одному по 5 байт, по одному из трех байт будет поиск, если они находятся, со вторыми тремя байтами будет производится математический расчет и если расчет совпадает то будет считывать последние 5 байт.
Более подробнее про базу сказать не могу 
Ничего криминального, но распространяться не хочу.
Другие подобные базы имеют размер около 10-15гб, и поиск происходит ну 15-20 минут.
мне намекнули что там тоже эти самые таблицы, правда или нет не знаю.




Это сообщение отредактировал(а) кмс - 13.1.2014, 23:44

+ служебная информация, индексы...


Даже если принять, что создание 1 записи займет 1 миллисекунду, один компьютер будет писать данные 34 года. Если предположить, что увеличение числа компьютеров даст линейный прирост скорости (на самом деле - несколько меньше), то чтобы получить 1 месяц нужно 408 компов (ну, ладно - все они четырехядерные, тогда -  102)    
А теперь, внимание - исходя из Вашего "на порядок дольше" и моего предположения в "1 мс" получается, что поиск значения должен вестись максимум за 0,1 мс??? Имхо, тут никакие индексы, партицирование и т.п. не помогут... хотя партиции - это вариант, но отца русской демократии они не спасут. 

Где у меня ошибка в расчетах?

Ну и плюс ко всему - минимум 11 терабайт... многовато будет.

А не может такого быть, что эти базы содержат (дальше - полет фантазии) к примеру - промежуточные значения вычислений? или конечные, но с каким-нибудь шагом? Программа выбирает нужное ей и производит до-обработку или "интерполяцию значений, максимально близких к требуемому" (которая как раз и занимает основное время из 10-15 минут)
?

Добавлено @ 22:44

Если использовать при расчетах не 1 миллисекунду, а (15-20 минут)*10, то итоговые значения получаются вообще неадекватными. Посему - не думаю, что в аналогах эта задача решалась "в лоб".

Это сообщение отредактировал(а) kami - 14.1.2014, 22:45

kami, 
ошибся в расчетах   

Запилил программку с тремя потоками, каждый поток генерирует одиннадцатибайтовые числа от 10000000000 до 10001000000 в простом цикле. Все, что сгенерировал - кидает в массив. Цикл проходит за доли секунды, даже не могу отловить этот момент.
Затем каждый поток записывает свой массив в файл.
На запись 3-х файлов по 1 млн. одиннадцатибайтовых чисел (в каждый) ушла минута. Сама запись идет долго, но я думаю, что тут можно как-нибудь оптимизировать процесс. Сделать ассемблерные вставки, использовать нестандартные функции или еще что-нибудь.
И да, процессор 6-летней давности не был загружен на всю катушку. И это все на гражданских Дельфях, в простых потоках с "синхронайзом" и записью с помощью writeln   .

Где? Этот пример - не показатель (несмотря на то, что в нем де-факто не используются потоки) , я отталкивался от утверждений

и

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

Это сообщение отредактировал(а) kami - 15.1.2014, 10:55

Потоки позволяют использовать все возможности многоядерных процессоров. Я создал 3 экземпляра данного класса, установив им разные флажки.
Я о том, что ни о каких 34 годах речь не идет) Максимум - полгода)
А вот поиск по 10Тб базе - это да, это вопрос.

Наверно для майнинга такие штуки нужны... Или аккаунты ВК ломать   

Это не относится к делу, но в Вашем коде не используюется многопоточность. Весь код выполняется в основном потоке. Если желаете продолжить дискуссию на эту тему - давайте вернемся в Ваш топик.

А по теме - ТС утверждает, что создание каждой 11-байтной записи очень ресурсоемкая операция. Я привел расчеты. Единственным "узким" местом в моем сообщении было получение 34 лет. Расшифрую:
1099511627775 / 1000(мс) /60(сек)/60(мин)/24(час)/365(дней) = 34,8 лет.

Вы утверждаете, что они не верны. Приведите доказательства.

Это сообщение отредактировал(а) kami - 15.1.2014, 11:29

Вот делал специально программку что бы сравнивать разницу между поиском и перебором.
Может быть там и не совсем точно, так как при поиске не учитываются некоторые нюансы, но и отклонения не столь существенные.
http://www.sendspace.com/file/cny0tv
PS: конечное значение это сколько вариантов перебирать.
Это число делиться на количество потоков и каждый поток работает со своим отрезком.
А так пробовал создавать базу, у меня 300мб (три потока каждый по 100мб) создавались примерно 30-40 минут, точнее не скажу, врубил и пошел телек смотреть, так заглядывал нет нет.
Но и поиск будет не по всей базе. Например можно рассортировать по первому байту искомого, и того получается 255 баз, прога сразу будет искать в нужной базе.


Это сообщение отредактировал(а) кмс - 15.1.2014, 11:53

А где оно ищет, если не секрет? Что-то слишком быстро проходит поиск, без разницы что я задам в поле "конечное значение" 

Ну там в поиске просто сравнение

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

Добавлено через 2 минуты и 11 секунд
Ты введи все 5 байт - 1099511627775  и тогда придется подождать 

Добавлено через 11 минут и 51 секунду
Вот скрин, это поиск по всем вариантам.
http://s005.radikal.ru/i210/1401/65/5093ca998501.png 
Но как говорил выше реальный поиск по все базе конечно будет дольше, но и если учитывать что искать во первых будет не по все базе, во вторых все таки не обязательно что придется искать до конца, наткнутся на искомое может в любое время 


Это сообщение отредактировал(а) кмс - 15.1.2014, 11:56

kami, да ну! В одном потоке? Я привел класс потока:

Код с формой и запуском потоков такой (если интересно):

И он немного долбанутый, особенно таймер не к месту... Ну да пофиг, сделал его за 2 минуты...
Создается 3 объекта того класса.

А по поводу времени

За 1 мс моя прога делает 50 записей. И, я повторюсь, этот процесс можно ускорить,
поэтому

это можно смело делить на 50.
Вся проблема будет только в организации работы всей базы и поиском.


Это сообщение отредактировал(а) boobie - 15.1.2014, 12:11

Весь код Вашего потока заключен в выполнении Synchronize. Если нажать F1, то выяснится, что Synchronize выполняет код в контексте основного потока (или потока-родителя, в зависимости от версии Delphi). Методы переключения контекста (емнип) разнятся так же в зависимости от версии Delphi.
Все три потока при создании выполняют одно действие - пытаются переключиться в контекст основного потока приложения. И уже после переключения выполняется анонимный метод.
Вывод: сколько бы таких потоков ни было создано, выполнение будет идти в контексте одного, что сразу сводит на нет необходимость их создания.
Емнип, такой подход встречался в книгах Фленова (не к ночи будет помянут) и основанных на его книгах примерах.
Совет: выкиньте эти книги и почитайте для начала хотя бы статью на Винграде.

Можно конечно уменьшить базу и без всяких таблиц. Например писать в нее только первые 6 байт, а искомые 5 байт будут адрес / 6
Но все равно база большая получается и не получится ее отсортировать, хотя и над сортировкой тоже в принципе можно подумать.

Это понятно, и если данные будут отсортированы хотя бы по первому значению, это уже значительно упростит поиск вне зависимости от выбора хранилища, особенно если разделить данные по этому признаку (к примеру - разные файлы, или для СУБД - разделы)

Ой, блин, сорри... 
Да, я реально помешан на этом синхронайзе=(
Убрал все обращения к форме, убрал секцию синхронайз...
Теперь 34Кб данных (3000000 одиннадцатибайтовых чисел) генерируются за 2.8 секунды! 34 года надо разделить на 500   

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

Это сообщение отредактировал(а) kami - 15.1.2014, 12:43

Плюс еще разделить на количество компов, хозяева которых просто не дождутся когда придется считать 
В принципе если уменьшить базу до 5 терабайт(способом который я описал выше),  уже можно хотя бы делать онлайн базу, что честно говоря не очень бы хотелось, ну и как поведет себя сервер с поиском если например будут одновременно 100-500 запросов.
Так что все таки придется изучать эти rainbow tables

Добавлено через 4 минуты и 19 секунд

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


Это сообщение отредактировал(а) кмс - 15.1.2014, 12:46

kami, я не спорю, потому как не знаю скорость поиска по такой базе... Вполне возможно, что искать будет дольше, чем генерировать.
Я просто говорил о том, что сама генерация не займет 34 года. Гораздо, гораздо меньше.

Осталось собрать RAID на 11Тб

Это сообщение отредактировал(а) boobie - 15.1.2014, 12:55

Да как поиск может занять больше времени чем генерирование?
Наоборот на много быстрее.

Смотря как его реализовать   

Да даже если вести поиск простым перебором по базе, все равно быстрее.

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

Дело в не организации поиска. Генерация пусть хоть и имеет "стабильное время на одно значение", но оно отнимает слишком много времени на расчеты.

Добавлено @ 13:25
Там же не просто генерируются случайные значение, а именно идут расчеты при двух входных параметров каждый по 5  байт. А так как на выходе мы имеем результат из 3 байт, то получается не очень маленький процент совпадений, по этому приходится считать по 2 раза(один из входных параметров меняем). В итоге получаем что для одной записи в базу нужно вести 2 расчета.

Это сообщение отредактировал(а) кмс - 15.1.2014, 13:27

Какой то у вас полупредметный разговор выходит.

кмс, напиши, сколько времени уходит на одну генерацию. Минимум, максимум, в среднем (чаще всего).

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

Добавлено @ 13:40
Вот перебор 10000 значений.

4 ядра, 4 потока, проц i5

для 100000


Это сообщение отредактировал(а) кмс - 15.1.2014, 13:42

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

UPD. Только учтите, что индексы увеличат объем базы, так что к первоначальным 5Тб (я про "сокращенный вариант базы) добавится еще ... а вот сколько - зависит от СУБД. 

Это сообщение отредактировал(а) kami - 15.1.2014, 14:17

 не проще бесплатную радужную таблицу скачать ?
типа такого http://www.project-rainbowcrack.com/table.htm

Это сообщение отредактировал(а) DYUMON - 18.1.2014, 17:25