Нахождение количества общих элементов 2 массивов

Serg50
Можете назвать отношение средней длины списка ключей к количеству действительно используемых? А еще лучше статистику средней встречаемости ключа по всем молекулам файла. Просто переход к таблице ключ=>список молекул может сделать суммирование более эффективным если средняя длина списка будет существенно менее общего числа записей в файле.

 

Serg50
Ваш алгоритм решает задачу за время N*M*k, но можно его улучшить до n*M*k.
N - число эталонных записей
M - число тестируемых записей
k - среднее число ключей на одну запись
n - среднее число эталонных записей на один ключ

Код (Text):

1. #include <time.h>
2. #include <stdio.h>
3. #include <stdlib.h>
4. #include <string.h>
5.  
6. void T(char*s)
7. {
8.   static clock_t t;
9.   clock_t n=clock();
10.   if(s)
11.     printf("%s %.3f\n",s,(n-t)/(double)CLOCKS_PER_SEC);
12.   t=n;
13. }
14.  
15. #define maxid 1000000 //количество id
16. #define maxkey 1000000 //максимальное количество ключей
17. #define avgkey 100 //среднее количество ключей связанное с одним id
18.  
19. int* keys[maxid];//списки ключей связанных с заданным id
20. int* ids[maxkey];//списки id связанных с данным ключом
21. int nkeys[maxid];//длины списков ключей
22. int nids[maxkey];//длины списков id
23. int tans[maxid];//массив для подсчёта числа общих элементов
24.  
25. int main()
26. {
27.   int id,key,total,*buf,*kl,k,i,id2,*il;
28.  
29.   T(0);
30. //виртуальная генерация для подсчёта необходимого количества памяти
31.   for(key=0;key<maxkey;key++)
32.     nids[key]=0;
33.  
34.   srand(987654321);
35.   for(id=0,total=0;id<maxid;id++)
36.   {
37.     for(key=rand()%maxkey/avgkey,nkeys[id]=0;key<maxkey;)
38.     {
39.     nids[key]++;
40.     nkeys[id]++;
41.     total++;
42.     key+=rand()%(2*maxkey)/avgkey+1;
43.     }
44.   }
45. //создание массива id=>список ключей  
46.   buf=malloc(total*sizeof(*buf));
47.  
48.   srand(987654321);
49.   for(id=0;id<maxid;id++)
50.   {
51.     keys[id]=buf;
52.     for(key=rand()%maxkey/avgkey;key<maxkey;)
53.     {
54.     *buf++=key;
55.     key+=rand()%(2*maxkey)/avgkey+1;
56.     }
57.   }
58. //создание массива key=>список id
59.   buf=malloc(total*sizeof(*buf));
60.   for(key=0;key<maxkey;key++)
61.   {
62.     ids[key]=buf;
63.     buf+=nids[key];
64.   }
65.  
66.   for(id=0;id<maxid;id++)
67.   {
68.     kl=keys[id];
69.     for(k=0;k<nkeys[id];k++)
70.     {
71.       key=kl[k];
72.       *ids[key]++=id;
73.     }
74.   }
75.  
76.   for(key=0;key<maxkey;key++)
77.     ids[key]-=nids[key];
78.  
79.   T("gen ");
80. //перебор тестовых id2
81.   for(id2=0;id2<maxid;id2++)
82.   {
83. //обнуление массива похожести на эталоны
84.     memset(tans,0,maxid*sizeof(*tans));
85. //перебор списка ключей связанных с тестовым id2
86.     kl=keys[id2];
87.     for(k=0;k<nkeys[id2];k++)
88.     {
89.       key=*kl++;
90. //перебор списка id связанных с данным ключoм и увеличение счётчика общих элементов в массиве tans
91.       il=ids[key];
92.       for(i=0;i<nids[key];i++)
93.     tans[il[i]]++;
94.     }
95. //преобразование числа общих элементов в коэффициенты Танимото
96. //    for(id=0;id<maxid;id++)
97. //      tans[id]/(nkeys[id]+nkeys[id2]-tans[id]);
98.     printf("\r%d",id2+1);//чтобы знать что программа работает
99.   }
100.   printf("\n");
101.  
102.   T("calc ");
103.  
104.   return 0;
105. }

На сравнение массива в миллион элементов с самим собой при среднем числе ключей 100 из миллиона возможных у программы ушло 1878 секунд, то есть чуть больше 31 минуты. То есть для массива в 5000000 ожидаемое время работы должно быть в 25 раз больше или около 13 часов. Правда если реальное число различных ключей будет 20000, то эта программа станет работать в 50 раз медленнее и тоже будет 3 с половиной недели считать. Но есть резервы для улучшения:
В частности, можно производить суммирование не более чем по 255 строк в байтовый массив, а потом добавлять его к массиву tans.
Еще, списки id которые длинее чем N/32 можно заменять на битовые массивы, читать их по 1 байту, расширять его биты в байты загружая соответствующие константы в mmx регистры из таблицы на 256 элементов, и суммировать сразу по 8 байт. Еще можно читать и суммировать таким образом сразу по 3-4 битовые строки.
Еще возможна всякая оптимизация с подсчётом сразу нескольких сумм, с упорядочиванием загрузки строк ключей, и прочие зависимые от кеша штуки.

 

Serg50

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

Код (Text):

1. #include <time.h>
2. #include <stdio.h>
3.  
4. #define _CRT_RAND_S
5. #include <stdlib.h>
6.  
7.  
8.  
9. #define TESTS_N 100
10.  
11. #define maxid 0x400000 //количество id
12.  
13. char map[maxid / 8];
14. unsigned int id1[maxid];
15. unsigned int id2[maxid];
16.  
17.  
18. void getABC(unsigned int* ID1, unsigned int* ID2, int* a, int* b, int* c){
19.   int id;
20.   memset(map, 0, maxid / 8);
21.   for(*a = 0; *ID1 != 0; ID1++, *a++){
22.     id = *ID1;
23.     map[id >> 3] |= 1 << (id & 7);
24.   }
25.   for(*b = 0, *c = 0; *ID2 != 0; ID2++, *b++){
26.     id = *ID2;
27.     *c += (map[id >> 3] >> (id & 7)) & 1;
28.   }
29. }
30.  
31.  
32. int main()
33. {
34.   unsigned int maxkey, tmp;
35.   int i, j, a, b, c;
36.   clock_t t0, t, t_all, t_max;
37.  
38.   t_max = t_all = 0;
39.  
40.   for(j = 0; j < TESTS_N; j++){
41.     printf("- %d\n", j);
42.  
43.     rand_s(&maxkey);
44.     maxkey %= maxid;
45.  
46.     for(i = 0; i < maxkey; i++){
47.       rand_s(&tmp);
48.       tmp %= maxid - 1;
49.       id1[i] = tmp + 1;
50.     }
51.     id1[i] = 0;
52.  
53.     rand_s(&maxkey);
54.     maxkey %= maxid;
55.  
56.     for(i = 0; i < maxkey; i++){
57.       rand_s(&tmp);
58.       tmp %= maxid - 1;
59.       id2[i] = tmp + 1;
60.     }
61.     id2[i] = 0;
62.  
63.  
64.     t0 = clock();
65.     getABC(id1, id2, &a, &b, &c);
66.     t = clock() - t0;
67.     t_all += t;
68.     if(t > t_max)
69.       t_max = t;
70.   }
71.  
72.   printf("max time = %.4fs, avg time = %.4fs\n",
73.               ((double)t_max)/(double)CLOCKS_PER_SEC,
74.               ((double)t_all/(double)TESTS_N)/(double)CLOCKS_PER_SEC
75.         );
76.  
77.   return 0;
78. }

скомпиленный с -O2 , при 100 (TESTS_N. можете сделать больше себе. мне не охота было ждать) подсчетах a, b и c со случайными наборами ключей в списках id1 и id2 выдало на моем не самом быстром компе

а, да, сортировать ключи тут не надо

 

Попробовал разбить самый внутренний цикл на две части, чтобы обновление массива tans происходило блоками не вылезающими за пределы кеша. Но при моих параметрах ускорение было всего в два раза. При сужении диапазона различных ключей выигрыш от такого разбиения может быть более существенным, а может суммирование битовых строк окажется лучшим вариантом. Вообще мой алгоритм должен работать за время пропорциональное суммарному размеру всех возможных пересечений списков признаков, а не объединений как было в алгоритме предложенном автором. То есть этот алгоритм очень хорошо работает в случае если множества существенно друг на друга не похожи. Правда из-за произвольного доступа к памяти скорость вычислений падает в сотню, а может и в тысячу раз. Если индексы слишком сильно разбросаны, то для увеличения ячейки tans на единицу нам приходится читать целую строку кеша, которая вряд ли будет использована повторно и потом её придётся записывать обратно.
Но это всё пока абстрактные рассуждения, для более конкретных нужно знать:
количество эталонных образцов
количество тестируемых образцов
фактическое число различных ключей
среднее число ключей в эталонных образцах
среднее число ключей в тестируемых образцах

 

Спасибо за обсуждение! Предложенные алгоритмы посмотрю сегодня по дороге домой...

Если не абстрактно, то такого рода сравнение используется для нескольких целей, и наиболее времяемкое из них сравнение виртуальной библиотеки(предполагаемых к синтезу соединений) со уже имеющимися реальными продуктами(а зачастую еще и с имеющимися в продаже) - цель сделать непохожие на уже имеющиеся соединения. Для этого отбираются соединения с Tan менее чем заданное с эталонным. При этой задаче:

количество эталонных образцов- 5000000-8000000(если еще и продажные)
количество тестируемых образцов - 50000 - 1500000(зависит от библиотеки)
фактическое число различных ключей
Ни разу не считал... Вообще то говоря чем больше тем лучше - иначе дизайн библиотеки был не очень. Ведь количество ключей в какой-то мере отражает разнообразие задуманных соединений
среднее число ключей в эталонных образцах
среднее число ключей в тестируемых образцах
Тоже ни разу не определял... Могу лишь посмотреть максимально количество. Так тек. склад разбит на 4 куска, где макс. количеста включей на запись - 419, 425, 256 и 295. Но это максимальное.

 

Serg50
судя по описанию и числам - задача полностью и целиком коммерческая. и на правильном алгосе ктото тоимеет неплохой профит. может быть парень из калифорнии, но явно не я. чувствую себя лохом и желание помогать левым людям какбы само собой испаряется. хотя алгос можно ускорить еще раза в 1.5-2. но это уже будете делать вы сами. должны ж вы хоть какуюто работу делать сами?

 

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

Насчет "должны ж вы хоть какуюто работу делать сами?" - я в первую очередь отвечаю за то как синтезировать эти продукты и за это получаю деньги. Я знаю как их сделать. А то, что я занялся дизайном библиотек(это жаргон , это уже скорее хобби. Так что не надо мне приписывать мотивы котрых не было.

 

Serg50

фигня. фигня. даже если удастся из 3х недель сделать 3 дня - это _очень_ выгодная вещь для дела. это либо переведет некоторые вещи из разряда возможных только теритически в разряд практических, либо поможет сэкономить на дорогом оборудовании и затратам на его обслуживание.
а то что вы говорите - я не я и коза не моя - обычное дело. так все говорят в подобных случаях. мол хобби - искать дубликаты среди мильярдов чисел. жутко интересно.

задача букварная.

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

 

Если бы ТС внятно сформулировал ТЗ я бы тоже по приколу поразмышлял над ним, т.к. нахождение количества общих элементов 2 массивов является примитивном действием уровня 9-11 класс средней школы... Интересно, в чём там проблемы?
К примеру, есть mas1: array of integer; mas2: array of integer? И среди них надо найти одинаковые числа, а затем вывести их? Если я правильно понял задачу, профит готов в уме

 

Проблема в количестве

qqwe
Ну если вы так уверены в моих корыстных намерениях воздержитесь от обсуждения. Ибо доказать, что я не верблюд, тем более в рамках форума мне сложно. Да и лень

 

Serg50

ладно, мне тоже лениво. тем более, что после драки.. (вы не менеджер, не?)

впрочем, если вам эта тема интересна - скажите, как несложно ускорить алгоритм в 1.5-2 раза? только немного изменив алгоритм? (может и больше, чем в 2 раза. я не проверял)

 

Serg50
И что, сложно многопоточность реализовать с привязкой для каждого ядра процессора или при SMP на каждый проц? Какое кол-во элементов?

 

d2k9

на предыдущей странице написано

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

 

Большой объём памяти говорите? И что тогда мешает взять Core i9 с 128Гб RAM? Только я не вижу для чего столько оной - у меня это заняло 2.35Гб, на 2.1Ггц Core 2 Duo на ноутбуке заполнение 2х массивов рандомными значениями в 2х тредах произошло за 1 сек.

Код (Text):

1. type
2.   PKey = ^TKey;
3.   TKey = packed array [1 .. 200] of Integer;
4.   PMyArr = ^TMyArr;
5.   TMyArr = packed array [1 .. 1500000] of TKey;
6.  
7. var
8.   mas1: PMyArr;
9.   mas2: PMyArr;
10.  
11. begin
12.   GetMem(mas1, SizeOf(TMyArr));
13.   GetMem(mas2, SizeOf(TMyArr));
14.   TMasFill.Create(False, mas1);
15.   TMasFill.Create(False, mas2);
16. ...
17.  
18. end.

Надо учиться указатели использовать вместе с упакованными типами данных
Сей сэмпл на дельфи легко можно переделать на Си. Хотя у ТС видно проблема со сравнением массивов. Будет время напишу.

 

Специально в словарь залез - ответ нет. А как вы понимаете "менеджер"? А программирование это действительно хобби, когда устаю от химии с ее малой предсказуемостью.

Алгоритм вообще? Тот которым пользуюсь я? Тот который привели вы?

Кстати я посмотрел тот который привели вы. Да я использовал практически такой же, но не стал заморачиваться с упаковкой бит, и у меня был map[maxid] где использовался только 0 бит. Но этот алгоритм - это сравнение всего 2 элементов из массивов ID1 и ID2. Соотвественно получается, что мы будем иметь для типовой. и не самой большой задачи 200000*5000000*0.046s = 1470 лет Это конечно утрированно, но показывает, что при такой постановке задачи, важна оптимизация кода, а не только алгоритма.

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

 

Идея любопытная, но к сожалению сравнение на себя это частная задача, чаще приходится делать что то вроде 200000*5000000, а в этом случае массив Tan буде слишком большим . Массив key-ID, я как то не рассматривал, наверное потому что его еще нужно сделать.

Я посчитал среднее количество ключей в некотром куске, и их оказалось ~3500 на 250000 ID. Причем в первом же 50000 куске 3000 из них присутстворвали. То есть количество реально используемых ключей значительно меньше возможного. И во всем большом вряд ли оно будет больше 5000. То есть есть возможность перед сравнением их заменить на другие сузив их пространство. Надо подумать, что это может дать. Спасибо за наводку - мне и голову не приходило проверить сколько из них реально используется

 

Serg50
Держите Профит http://88.208.217.213/mas_count.rar, с вас пиво
Протестите сколько времени займёт сравнение массивов: у меня 3Гб памяти не хватило для хранения хэшей. Ну ещё можно будет многопоточность добавить для сравнения хэшей, сейчас она только для заполнения массивов и вычисления хэшей в процессе. Потом сырцы выложу.
Алгоритм: 2 массива, в каждом 1 .. 1500000 элементов, каждый элемент содержит в себе 200 подэлементов, также имеется 2 массива для хэшей (1 .. 1500000 элементов). При старте массивы заполняются рандомными значениями и сразу же от этого берётся хэш, который добавляется в массив хэшей. Затем запускается тред, в котором идёт сравнения 2х массивов хэшей, здесь надо сделать разделение массивов дабы был не один тред, а несколько. Пробуй те короче

 

З.Ы. http://88.208.217.213/mas_count.rar

 

Serg50
Вообще-то у меня строки массива tan генерятся по одной, и там где она сформированна можно выполнять любую их обработу. К тому же у меня можно сравнивать и различные массивы, правда один из них должен храниться ввиде id->keys, а другой key->ids. Массив keys->id можно кстати заменить на битовый, потом преобразовывать биты в отдельные байты и суммировать их используя MMX или SSE. Даже если там будет один единичный бит на сотню нулей, это будет в 10-30 раз быстрее вашего безобразия из первого сообщения. А в теории алгоритм может быть быстрее вашего в "число уникальных ключей"/"среднее число ключей в строке". Но случайный доступ к памяти его раз в 100 тормозит, хотя версия с разбиением циклов может быть не совсем плоха для ваших данных.

 

The exception unknown software exception (0x0eedfade) occured in the application at location 0x7c59bcb1