Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > 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 терабайт данных. Зачем вам записывать куда-то столько данных, если их можно рассчитать? Что вообще надо делать? Ну создали вы базу, а затем какие операции надо? Для чего это вообще делается?

Автор: кмс 13.1.2014, 23:43
Цитата(Illusion Dolphin @  13.1.2014,  22:50 Найти цитируемый пост)
1099511627775  * 11 = 11 терабайт данных. Зачем вам записывать куда-то столько данных, если их можно рассчитать?

Потому что рассчитать намного дольше чем потом в базе искать, на порядок дольше.
Создавать базу придется, по предварительным расчетам около месяца и то если будет достаточно компов.
Цитата(Illusion Dolphin @  13.1.2014,  22:50 Найти цитируемый пост)
 Что вообще надо делать? Ну создали вы базу, а затем какие операции надо? Для чего это вообще делается?

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



Автор: kami 14.1.2014, 22:35
Цитата(Illusion Dolphin @  13.1.2014,  22:50 Найти цитируемый пост)
11 терабайт данных. 

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

Цитата(кмс @  13.1.2014,  23:43 Найти цитируемый пост)
Потому что рассчитать намного дольше чем потом в базе искать, на порядок дольше.

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

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

Ну и плюс ко всему - минимум 11 терабайт... многовато будет.
Цитата(кмс @  13.1.2014,  23:43 Найти цитируемый пост)
Другие подобные базы имеют размер около 10-15гб, и поиск происходит ну 15-20 минут.

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

Добавлено @ 22:44
Цитата(кмс @  13.1.2014,  23:43 Найти цитируемый пост)
поиск происходит ну 15-20 минут.

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

Автор: boobie 15.1.2014, 09:37
kami, 
ошибся в расчетах  smile 

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

unit Unit2;

interface

uses
  Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
  Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls;

type
  mypot = class(TThread)
  private
    { Private declarations }
  protected
    schet:integer;
    massiv1:array[1..1010000]of integer;
    massiv2:array[1..1010000]of integer;
    massiv3:array[1..1010000]of integer;
    procedure Execute; override;
  public
    flag:integer;

  end;

implementation

{ 
  Important: Methods and properties of objects in visual components can only be
  used in a method called using Synchronize, for example,

      Synchronize(UpdateCaption);  

  and UpdateCaption could look like,

    procedure mypot.UpdateCaption;
    begin
      Form1.Caption := 'Updated in a thread';
    end; 
    
    or 
    
    Synchronize( 
      procedure 
      begin
        Form1.Caption := 'Updated in thread via an anonymous method' 
      end
      )
    );
    
  where an anonymous method is passed.
  
  Similarly, the developer can call the Queue method with similar parameters as 
  above, instead passing another TThread class as the first parameter, putting
  the calling thread in a queue with the other thread.
    
}

uses Unit1;

{ mypot }

procedure mypot.Execute;
var f1,f2,f3:textfile;

begin
schet:=1;
//while terminated=false do
begin
  Synchronize(
      procedure
      var i:integer;
      begin
        if flag=1 then
        begin
          for i:=10000000000 to 10001000000 do
          begin
            massiv1[schet]:=i;
            inc(schet);
            form1.Label8.caption:=inttostr(schet);
          end;
          form1.label1.Caption:=form1.label7.caption;
          assignfile(f1,'t1.txt');
          rewrite(f1);
          for I := 1 to 1000000 do
          writeln(f1,massiv1[i]);
          closefile(f1);
          form1.label4.Caption:=form1.label7.caption;
        end;

        if flag=2 then
        begin
          for i:=20000000000 to 20001000000 do
          begin
            massiv2[schet]:=i;
            inc(schet);
          end;
          form1.label2.Caption:=form1.label7.caption;
          assignfile(f2,'t2.txt');
          rewrite(f2);
          for I := 1 to 1000000 do
          writeln(f2,massiv2[i]);
          closefile(f2);
          form1.label5.Caption:=form1.label7.caption;
        end;


        if flag=3 then
        begin
          for i:=30000000000 to 30001000000 do
          begin
            massiv3[schet]:=i;
            inc(schet);
          end;
          form1.label3.Caption:=form1.label7.caption;
          assignfile(f3,'t3.txt');
          rewrite(f3);
          for I := 1 to 1000000 do
          writeln(f3,massiv3[i]);
          closefile(f3);
          form1.label6.Caption:=form1.label7.caption;
        end;
      end
      );
end;
end;

end.

Автор: kami 15.1.2014, 10:53
Цитата(boobie @  15.1.2014,  09:37 Найти цитируемый пост)
ошибся в расчетах 

Где? Этот пример - не показатель (несмотря на то, что в нем де-факто не используются потоки) , я отталкивался от утверждений
Цитата(кмс @  13.1.2014,  23:43 Найти цитируемый пост)
рассчитать намного дольше чем потом в базе искать

и
Цитата(кмс @  13.1.2014,  23:43 Найти цитируемый пост)
Другие подобные базы имеют размер около 10-15гб, и поиск происходит ну 15-20 минут.

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

form1.Label8.caption:=inttostr(schet);
) не занимают вообще ничего.

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

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

Автор: kami 15.1.2014, 11:27
Цитата(boobie @  15.1.2014,  11:14 Найти цитируемый пост)
Потоки позволяют использовать все возможности многоядерных процессоров. 

Это не относится к делу, но в Вашем коде не используюется многопоточность. Весь код выполняется в основном потоке. Если желаете продолжить дискуссию на эту тему - давайте вернемся 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:38 Найти цитируемый пост)
при поиске не учитываются некоторые нюансы,

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

Автор: кмс 15.1.2014, 11:55
Ну там в поиске просто сравнение
Код

  while ks < ke do
  begin
    if (b = 22) and (b1 = 23) then
      krr := 0;
    inc(ks);
  end;

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

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

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

Автор: boobie 15.1.2014, 12:10
kami, да ну! В одном потоке? Я привел класс потока:
Код

mypot = class(TThread)

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

unit Unit1;

interface

uses
  Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
  Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls, Vcl.ExtCtrls, unit2;

type
  TForm1 = class(TForm)
    Button1: TButton;
    Label1: TLabel;
    Label2: TLabel;
    Label3: TLabel;
    Label4: TLabel;
    Label5: TLabel;
    Label6: TLabel;
    Label7: TLabel;
    Timer1: TTimer;
    Button2: TButton;
    Label8: TLabel;
    procedure FormCreate(Sender: TObject);
    procedure Timer1Timer(Sender: TObject);
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
    pot: array[1..3] of mypot;
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
begin

timer1.Enabled:=true;
pot[1].start;
pot[2].start;
pot[3].start;
end;

procedure TForm1.Button2Click(Sender: TObject);
begin
pot[1].Terminate;
pot[2].Terminate;
pot[3].Terminate;
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
pot[1]:=mypot.Create(true);
pot[2]:=mypot.Create(true);
pot[3]:=mypot.Create(true);

pot[1].Priority:=tpnormal;
pot[2].Priority:=tpnormal;
pot[3].Priority:=tpnormal;

pot[1].flag:=1;
pot[2].flag:=2;
pot[3].flag:=3;
end;

procedure TForm1.Timer1Timer(Sender: TObject);
begin
label7.Caption:=floattostr(strtofloat(label7.Caption)+0.1);
end;

end.

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

А по поводу времени
Цитата

Даже если принять, что создание 1 записи займет 1 миллисекунду

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

1099511627775 / 1000(мс) /60(сек)/60(мин)/24(час)/365(дней) = 34,8 лет.

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

Автор: kami 15.1.2014, 12:24
Цитата(boobie @  15.1.2014,  12:10 Найти цитируемый пост)
Я привел класс потока:

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

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

Автор: kami 15.1.2014, 12:35
Цитата(кмс @  15.1.2014,  11:55 Найти цитируемый пост)
не обязательно что придется искать до конца,

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

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

Автор: kami 15.1.2014, 12:42
Цитата(boobie @  15.1.2014,  12:37 Найти цитируемый пост)
Теперь 34Кб данных (3000000 одиннадцатибайтовых чисел) генерируются за 2.8 секунды! 34 года надо разделить на 500

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

Автор: кмс 15.1.2014, 12:44
Цитата
34 года надо разделить на 500

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

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

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

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

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

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

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

Автор: boobie 15.1.2014, 13:12
Цитата(кмс @ 15.1.2014,  12:56)
Да как поиск может занять больше времени чем генерирование?
Наоборот на много быстрее.

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

Автор: кмс 15.1.2014, 13:14
Цитата
Смотря как его реализовать  user posted image 

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

Автор: kami 15.1.2014, 13:15
Цитата(кмс @  15.1.2014,  12:56 Найти цитируемый пост)
Да как поиск может занять больше времени чем генерирование?

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

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

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

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

Автор: Агрох 15.1.2014, 13:34
Какой то у вас полупредметный разговор выходит.

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

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

Добавлено @ 13:40
Вот перебор 10000 значений.
Цитата
Начало в 16:39:11
Поток завершен в 16:39:12
Поток завершен в 16:39:12
Поток завершен в 16:39:12
Поток завершен в 16:39:12

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

для 100000
Цитата
Начало в 16:41:47
Поток завершен в 16:41:51
Поток завершен в 16:41:51
Поток завершен в 16:41:51
Поток завершен в 16:41:51

Автор: kami 15.1.2014, 14:14
кмс,  хорошо, раз Вы считаете, что поиск будет быстрее - "да будет так".
Ввиду того, что я не работал с "радужными таблицами" и не могу оценить целесообразность их использования, мой вариант решения задачи "в лоб" - сделать таблицу с разделением (partitions) по первому значению и индексами по полям, по которым будет производиться выборка. http://dev.mysql.com/doc/refman/5.5/en/partitioning.html.

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

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)