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

У меня часто встречается задача сжирающая непомерное количество времени. Один расчет, завершившийся сегодня, длился 3.5 недели! К сути:

Есть 2 массива данных, состоящие из идентификатора(строка) и приписанных ей "ключей" - числа 1-3FFFFFh. Формат хранения можно организовать любой. На выходе нужно иметь таблицу вида ID1 ID2 Tan, где Tan - коэффициент Танимото, считающийся по формуле Tan = c/(a+b-c), я еще добавляю *100, получая проценты(это не принципиально). Здесь a и b - количество "ключей" для ID1 и ID2, соотвественно, а c - количество одинаковых "ключей". Если интересно могу подробнее написать для чего это делается

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

Код (Text):

1.    
2.     mov       ebx, 4
3.     mov       eax, [esi]
4.     xor        ecx, ecx
5.     mov       edx, [edi]
6.     jmp       @F
7. align   16
8. @@:
9.     cmp       eax, edx
10.     mov       eax, 0
11.     mov       edx, eax
12.     cmovbe  eax, ebx
13.     cmovae  edx, ebx
14.     add       esi, eax
15.     add       edi, edx
16.     add       ecx, eax
17.     mov      eax, [esi]
18.     add       ecx, edx
19.     sub       ecx, 4
20.     mov      edx, [edi]
21.     or         eax, eax
22.     jz         @F
23.     or         edx, edx
24.     jnz       @B
25. @@:
26.     shr       ecx, 2

Здесь на входе ESI и EDI указывают на массивы ключей(завершенные 0), на выходе ECX - искомое число.

Что здесь можно сделать еще для оптимизации по времени?

 

Забыл добавить - ключи отсортированы по возрастанию.

 

Как понял я, существует один массив идентификаторов и один массив ключей. Но

поставило меня в тупик. Получается 2 массива ключей?

 

Не совсем так. Два массива идентификаторов, где каждый идентификатор ссылается на собственный массив "ключей". Соотвественно приведенный фрагмент относится к моменту сравнения, и ESI, EDI указывают уже на массивы ключей для 2 идентификаторов.

 

лучше оформить вывод Tan в двумерную таблицу ID1/ID2

 

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

 

Задачи где это используется разные, но наибольшего внимания заслуживает со след. параметрами:
ID1: 50 000 - 700 000
ID2: 500 000 - 1 500 000
"ключей" на каждое ID: 1-600, среднее 70-100

Как видете двухмерная матрица будет очень большой Да и как правило она не нужна, так как результать это набор ID1 где Tan больше, или меньше(в зависимости от цели) чем заданное число.

 

Serg50

А в момент генерации ключей нельзя сразу сравнивать и подсчитывать? Не накапливать два массива?

 

Serg50
Можно связять каждый ID с разреженным битовых хешем. Чтобы хеш был разреженным, его длину нужно выбрать в несколько раз большей, чем среднее количество ключей. Из каждого ключа мы получаем индекс бита в нашем хеше и устанавливаем его в 1, а остальные биты остаются равными 0. Если два хеша проксорить, то количество единичных бит даст нижнюю оценку числа элементов в симметричной разности множеств, и если она больше (a+b)*(1-Tan)/(1+Tan), значит c/(a+b-c)<Tan, а если нет, то придётся сравнивать сами множества.
Можно построить немного другой хеш, в котором число совпадающих бит для двух ID будет пропорционально числу общих элементов, но это в среднем. Сравнение с Tan жесткое или вариант "найти почти все" тоже годится?

 

Массивы уже отсортированы? Это прекрасно: тогда сортировка слиянием+подсчёт парных элементов (они будут идти друг за другом).

 

CyberManiac
Слияние 10^11-10^12 массивов по 100 элементов в каждом? А оптимизация где?

 

CyberManiac

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

 

Serg50

плохо понял проблему, но я бы решал ее с помощью разреженного вектора размерностью в максимальный номер ID. 4 метра - это не так много.

void getABC(int* ID1, int* ID2, int* a, int* b int* c){
char* v = malloc( 0x3fffff );
memset(v, 0, 0x3fffff);
for(*a = 0; *ID1 != 0; ID1++, *a++){
v[*ID1] = 1;
}
for(*b = 0, *c = 0; *ID2 != 0; ID2++, *b++){
// если в самих ключах одного ID2 нету повторов или их не надо учитывать.
// тут можно и просто
// *с += v[*ID2];

// если же есть, то
if(v[*ID2])
*c++;
v[*ID2]++;
}
}

выделение памяти лучше вынести

хотя, может я и не понял задания

 

Black_mirror

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

l_inc

Да в том цодесе вообще без бутылки не разберёшься. Понятно, что интересен не весь супур-пупер массив, а только его кусочек из пары элементов на каждый момент времени. Хотя можно и целиком слить и на винт положить, если с парными ключами предполагается делать ещё что-то потом. Но более всего мне непонятно, как с 1.5 млн элементов в одном массиве и 700 тыс в другом можно обсчитывать пересечение этих массивов три недели. Даже если решать эту задачу дубовым SQL-запросом к какому-нить позорному MySQL, оно и то быстрее отработает.

 

CyberManiac

На винт — это ужасно. Согласно задаче даже приведенный алгоритм с линейной сложностью и минимумом непредсказанных условных переходов даёт огромные задержки. Складывая массивы по 500 элементов на винт рассчёты затя-а-а-анутся...

Есть полмиллиона массивов ID1 и полмиллиона массивов ID2. Нужно попарно сравнить все массивы (ID1 с ID2). Длина каждого — в районе пары сотен элементов. По крайней мере я так понял задачу.

 

оценка сверху даёт 700,000 * 1,500,000 * 600 ~ 6*10^14 ~ 500 Тбайт.
или где-то закралась ошибка?

 

t00x
Это оценка чего? По смыслу почти подходит под трёхмерную двоичную таблицу, содержащую признаки присутствия конкретного ключа в обоих массивах ID. Если да, то о такой таблице нигде речь не идёт.
Если же предполагалось посчитать объём обрабатываемых данных, то оценка сверху выглядит так:
(700.000 + 1.500.000) * 600 ~ 1,3 ГБ.

 

P.S. Хотя надо бы домножить ещё на 4, что есть размер одного ключа с учётом выравнивания размера числа "3FFFFF" до ближайшей большей степени двойки.

 

l_inc

зачем нужно хранить сами ключи, если только их не очень мало?

если нужно просто отмечать существует ли ключ N или нет, можно использовать способ

char* keys;

устанавливаем ключ
keys[N >> 3] |= 1 << (N & 7);

сбрасываем ключ
keys[N >> 3] &= ~(1 << (N & 7));

при этом используется блок памяти в (0x400000 >> 3) = 0x80'000 байт, что почти целиком влазит в кэш.

 

qqwe

А я не говорил хранении. Я говорил об объёме обрабатываемых входных данных. Хранятся ли эти данные где-то заранее или высчитываются динамически в процессе, известно вроде пока только автору.

Лично мне ничего не нужно.