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

Тема в разделе "WASM.A&O", создана пользователем Serg50, 1 мар 2010.

  1. Black_mirror

    Black_mirror Active Member

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

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    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 битовые строки.
    Еще возможна всякая оптимизация с подсчётом сразу нескольких сумм, с упорядочиванием загрузки строк ключей, и прочие зависимые от кеша штуки.
     
  3. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    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 выдало на моем не самом быстром компе
    а, да, сортировать ключи тут не надо
     
  4. Black_mirror

    Black_mirror Active Member

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

    Serg50 New Member

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

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

    qqwe New Member

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

    Serg50 New Member

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

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

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    Serg50
    фигня. фигня. даже если удастся из 3х недель сделать 3 дня - это _очень_ выгодная вещь для дела. это либо переведет некоторые вещи из разряда возможных только теритически в разряд практических, либо поможет сэкономить на дорогом оборудовании и затратам на его обслуживание.
    а то что вы говорите - я не я и коза не моя - обычное дело. так все говорят в подобных случаях. мол хобби - искать дубликаты среди мильярдов чисел. жутко интересно.

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

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

    d2k9 Алексей

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

    Serg50 New Member

    Публикаций:
    0
    Регистрация:
    17 фев 2010
    Сообщения:
    48
    Проблема в количестве :)

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

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    Serg50
    ладно, мне тоже лениво. тем более, что после драки.. (вы не менеджер, не?)

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

    d2k9 Алексей

    Публикаций:
    0
    Регистрация:
    14 сен 2008
    Сообщения:
    325
    Serg50
    И что, сложно многопоточность реализовать с привязкой для каждого ядра процессора или при SMP на каждый проц? Какое кол-во элементов?
     
  13. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    d2k9
    на предыдущей странице написано
    многопоточность тут не столько, тк задача не вычислительная, а на быстое ворочанье объемами памяти. те память тут станет узким местом. те если эта задача таки не просто хобби-"чтобы дурь в голову не лезла", то можно было бы и небольшой кластер организовать на более дешевых компах. но в случае хобби - это скучные глупости. а вот ускорить алгос в 2 раза, да - и интересно, и несложно.
     
  14. d2k9

    d2k9 Алексей

    Публикаций:
    0
    Регистрация:
    14 сен 2008
    Сообщения:
    325
    Большой объём памяти говорите? И что тогда мешает взять 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.
    Надо учиться указатели использовать вместе с упакованными типами данных ;)
    Сей сэмпл на дельфи легко можно переделать на Си. Хотя у ТС видно проблема со сравнением массивов. Будет время напишу.
     
  15. Serg50

    Serg50 New Member

    Публикаций:
    0
    Регистрация:
    17 фев 2010
    Сообщения:
    48
    :) Специально в словарь залез - ответ нет. А как вы понимаете "менеджер"? А программирование это действительно хобби, когда устаю от химии с ее малой предсказуемостью.
    Алгоритм вообще? Тот которым пользуюсь я? Тот который привели вы?

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

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

    Serg50 New Member

    Публикаций:
    0
    Регистрация:
    17 фев 2010
    Сообщения:
    48
    Идея любопытная, но к сожалению сравнение на себя это частная задача, чаще приходится делать что то вроде 200000*5000000, а в этом случае массив Tan буде слишком большим :). Массив key-ID, я как то не рассматривал, наверное потому что его еще нужно сделать.

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

    d2k9 Алексей

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

    d2k9 Алексей

    Публикаций:
    0
    Регистрация:
    14 сен 2008
    Сообщения:
    325
    З.Ы. http://88.208.217.213/mas_count.rar
     
  19. Black_mirror

    Black_mirror Active Member

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

    Serg50 New Member

    Публикаций:
    0
    Регистрация:
    17 фев 2010
    Сообщения:
    48
    :)
    The exception unknown software exception (0x0eedfade) occured in the application at location 0x7c59bcb1