Поиск общих сигнатур

Twister
Мы можем разбить второй файл на блоки не более размера дерева, тогда стоимость сортировки такого блока будет сравнима со стоимостью поиска каждого элемента блока в дереве. Правда для сортировки требуется не только читать память, но еще и записывать, поэтому константа наверно будет больше. Хотя узлы дерева тоже нужно иногда обновлять. Вообще я не думаю что в первом сообщении под "невероятным количеством времени" понималось дерево или сортировка, мне кажется там было что-то совсем ужасное.

 

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

По поводу сортировки: она нужна нам лишь единожды для построения первоначального дерева. Далее при вставке узлов ничего сортировать уже не нужно, нужно лишь вставлять в правильные места. Так что издержки на запись в память в этом случае будут минимальны.

Попутный вопрос к ТС: размер сигнатуры кратен чему-нибудь или совсем произволен?

 

зачем сортировать то? мы просто делаем N деревьев с ветками длиной не более 12, где N - количество различных байт, присутствующих в файле наименьшего размера... корнями будут байты начала последовательностей... и ничего сортировать не надо, обращаемся к корню равному текущему байту, переходим к его веткам, и так спускаемся... если прошли по всей ветке (от 4 до 12 байт по условию), то ветку оставляем... после каждого пройденного файла, те ветки, которые не оказались "помеченными на оставление", удаляем из дерева... на практике, я думаю, что после 3-4 файла проигрыша по памяти уже не будет, но останется выигрыш по скорости...

 

Rel

Мы немного разные варианты обсуждаем.

Я предлагаю реализовать одно дерево, каждый узел которого будет являться лишь характеристикой для поиска сигнатуры. Сами же сигнатуры будут содержаться на самом нижнем уровне, эдакий двусвязный список (может и не один).
Таким образом мы добъемся минимума проходов по дереву, минимум сравнений.
Соответственно, один раз построив такое дерево нам останется лишь добавлять/удалять в него узлы и/или сигнатуры.

Вы же предлагаете строить "N деревьев с ветками длиной не более 12, где N - количество различных байт, присутствующих в файле наименьшего размера". Сама идея довольно-таки неплоха, но, имхо, мы потеряем кучу времени на строительстве дерева для каждого файла.

 

Сортировка накладно получится - проще хеш считать.

 

чет я не совсем понял...

так мы строим деревья для наименьшего файла, потом наоборот убираем ветки, которые не нашлись в последующих... те ветки, которые остались и будут сигнатурами...

 

А я "чет" и не знаю, как понятней объяснить... Может просто устал.

Чтобы понять ту организацию данных, которую я имею ввиду, рекомендую для начала прочитать все три статьи Joe Celco об одном из способов создания деревьев в SQL. После этого, переложив полученную теорию на наш конкретный случай, должно стать ясно, как увязать дерево и двусвязный список для получения наивысшей скорости поиска.

 

Решение, от которого даже я, нубас со стажем, пришел в ужос, было примерно таким:

Код (Text):

1. PBYTE pfile1, pfile2;
2. PBYTE pos1, pos2;
3.  
4. pos1 = pfile1;
5. pos2 = pfile2;
6.  
7. for (x=0; x<file1_size; x++)
8. {
9.   for(y=0; y<file2_size; y++)
10.   {
11.      if (memcmp(pos1, pos2, 12) == 0)
12.      {
13.         add_signature(pos1, 12);
14.      }
15.   }
16. }

Далее файл с сигнатурами сохранялся. И далее шло сравнения подобного файла с файлом_3.
И т.д.

 

точнее вот так...

Код (Text):

1. PBYTE pfile1, pfile2;
2. PBYTE pos1, pos2;
3.  
4.  
5. for (x=0; x<file1_size; x++)
6. {
7.   pos1 = pfile1 + x;
8.   for(y=0; y<file2_size; y++)
9.   {
10.     pos2 = pfile2 + y;
11.      if (memcmp(pos1, pos2, 12) == 0)
12.      {
13.         add_signature(pos1, 12);
14.      }
15.   }
16. }

 

Как минимум подобное решение работает с сигнатурами 12 байт, а не от 5 до 12.

 

окей... посмотрю на следующей неделе... и раз зашел разговор о SQL, подскажи какие-нить материалы по внутреннему устройству баз данных (конкретно об организации хранилища в файле, разделении доступов и тд)...

 

dyn
Выделяешь из файлов все тройки байт, потом четверки, 5-ки и тд Заносишь в структуру value, file
Потом сортируешь. И за один проход выкидываешь лишнее.

 

Twister
Не знаю как вы будете делать дерево, но вот вариант с двоичным поиском вместо дерева:

Код (Text):

1. #include <time.h>
2. #include <stdio.h>
3. #include <stdlib.h>
4. #include <string.h>
5.  
6. const MaxA=0x800000;
7. const MaxB=0x800000;
8. const mask=0xFFFFFF;
9.  
10. int*a;
11. int*b;
12.  
13. void T(char*s)
14. {
15.   static clock_t t;
16.   clock_t n=clock();
17.   if(s)
18.     printf("%s %.3f\n",s,(n-t)/(double)CLOCKS_PER_SEC);
19.   t=n;
20. }
21.  
22. void fill(int *p,int n,int s,int k,int d)
23. {
24.     int i;
25.     for(i=0;i<n;i++)
26.     {
27.     *p++=s&mask;
28.     s=s*k+d;
29.     }
30. }
31.  
32. int read(int*p,int n)
33. {
34.     int r=0;
35.     while(n>0)
36.     {
37.     r+=*p;
38.     p+=4096/sizeof(*p);
39.     n-=4096/sizeof(*p);
40.     }
41.     return r;
42. }
43.  
44. void sort(int *p,int *n)
45. {
46.     int *s=p,*e=n;
47.     int k=*s++;
48.     int *i,t;
49.     goto qin;
50.     while(s<e)
51.     {
52.     *e^=*s^=*e^=*s;
53. qin:
54.     while(*e>k)
55.         e--;
56.     while(s<=n&&*s<=k)
57.         s++;
58.     }
59.     s--;
60.     *p^=*s^=*p^=*s;
61.     e++;
62. /*
63.     for(i=p;i<=n;i++){
64.     if(i==e) printf(" E");
65.     printf("%3d",*i);
66.     if(i==s) printf(" S");
67.     }
68.     printf("\n");
69. */
70.     if(p<s)
71.     sort(p,s);
72.     if(e<n)
73.     sort(e,n);
74. }
75.  
76. find(int *p,int n,int v)
77. {
78.     int l=0,r=n-1,a;
79.     while(l<r)
80.     {
81.     a=(l+r+1)>>1;
82.     if(p[a]<=v)
83.         l=a;
84.     else
85.         r=a-1;
86.     }
87.     return p[l]==v;
88. }
89.  
90. int main()
91. {
92.     int i,s;
93.     T(0);
94.     a=malloc(MaxA*sizeof(*a));
95.     b=malloc(MaxB*sizeof(*b));
96.     printf("%d\n",read(a,MaxA)+read(b,MaxB));
97.     T("alloc");
98.     fill(a,MaxA,123456,134775813,1);
99.     fill(b,MaxB,654321,134775813,1);
100.     T("fill");
101.     sort(a,a+MaxA-1);
102.     T("sort A");
103.     for(i=0;i<MaxB;i++)
104.     s+=find(a,MaxA,b[i]);
105.     T("find");
106.     sort(b,b+MaxB-1);
107.     T("sort B");
108.     printf("%d\n",s);
109. }

время у меня получилось такое:
alloc 0.050
fill 0.050
sort A 1.630
find 18.480
sort B 1.640
может у меня просто поиск криво сделан, или массивы плохо заполнены, в общем экспериментируйте.

 

Twister
Сегодня решил поэкспериментировать с хеш-таблицей. Увеличил размер массивов в 16 раз(до 512Мб каждый), а поиск при помощи хеш-таблицы эмулировал таким кодом:

Код (Text):

1.     for(k=0;k<10;k++)
2.     {
3.     fill(b,MaxB,clock(),134775813,1);
4.     T(0);
5.     for(i=0;i<MaxB;i++)
6.         s+=a[b[i]&(MaxA-1)];
7.     T("find");
8.     }

Время получилось такое:
find 19.810
find 27.100
find 22.260
find 17.750
find 15.760
find 15.720
find 18.120
find 15.470
find 15.640
find 22.690
А вот время сортировки массива B получилось около 31 секунды.
Конечно заполнение массива B тут далеко от реального, в нём скорее всего нету повторяющихся значений, которые могут испортить быстрой сортировке жизнь, с другой стороны есть ведь и другие алгортмы сортировки, да и хеш-функция сильно упрощена. Так что говорить о полной победе хеш-таблицы над сортировкой применительно к данной задаче еще рано.

 

Готовыми статьями не интересовался. Но можно заглянуть в сорцы того же огнептица, к примеру.

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

 

Товарищ dyn, как успехи в изготовлении сей тулзы?