Есть два списка массивов: первый — 10 млн. массивов, второй 100 массивов. Все массивы одинаковой длины и отсортированы. Задача:
Для каждого массива из первого списка собрать статистику совпадений с каждым массивом из второго списка.
Т.е. берем первый массив из 1го списка, сравниваем его с каждым массивом из 2го, а результаты (количество совпавших элементов) заносим в словарь. В словаре ключ — результат, а значение — сколько раз этот результат встретился. Такой словарь надо построить для каждого массива из 1го списка
Пример:
Список 1: {1,2,3}
Список 2: {1,2,3}; {1,2,5}; {1,3,4}; {4,5,6}
Сравниваем массив из 1го списка с каждым из 2го:
{1,2,3} и {1,2,3} — 3 совпавших элемента.
{1,2,3} и {1,2,5} — 2 совпавших элемента.
{1,2,3} и {1,3,4} — 2 совпавших элемента.
{1,2,3} и {4,5,6} — 0 совпавших элементов.
Результат:
{0,1}; //0 совпадений — 1 раз
{1,0}; //1 совпадение — 0 раз
{2,2}; //2 совпадения — 2 раза
{3,1}} //3 совпадения — 1 раз
Пишу на c#, в итоге быстрее решения в лоб ничего не нашел. Пытался представить второй список в виде дерева, но работает медленнее(возможно потому что дерево было построено на словарях).
Когда надо было просто проверить есть ли такой массив в списке, то дерево помогало очень сильно, но тут надо именно посчитать количество совпадений.
судя по примеру у вас не массивы, а множества, что можно представить в виде битовых массивов (для 1-50 хватит 64бит)
т.о. элементы массива — это 1 в соответствующей позиции ({1,2,5} ==> 0b0001 0110) количество совпавших элементов, это количество единиц после операции &.
(расчёт количества единиц для ускорения взять из таблиц )
Пример не осилил, но как правило для сравнения таких данных преобразую массивы в строки — со строковыми примитивами работа быстрее.
Например, поиск подстроки "_2_" в строках «1_2_3», «1_2_5», и т.д — очень быстрая операция. Если размерность массивов одинакова, то можно объединить массивы в текст, зная позицию подстроки, можно при желании определить к какому массиву такая строка относилась. Подумайте в этом направлении, я честно пытался раскурить вашу задачу, но у нас крайне разные способы мышления :)
Попробуйте предпосчитать 50 массивов с номерами массивов из 100, которые содержат индекс. Тогда расчет статистики по 1 массиву из 10 млн. займет примерно (100*10/50)*10=200 операций вместо 30*100=3000 при сравнении массивов «в лоб».
Не совсем понял, что вы имеете ввиду под «предпосчитать» и как вы рассчитали количество операций. Если не затруднит — напишите подробнее.
Я правильно понимаю, что вы предлагаете проиндексировать второй список? Какой вариант индексации вы бы предложили? Я с индексацией не работал, так что знания в этой области не очень хорошие.
Если бы ваш «Список 2» был кратчайшим, результат предпосчета был бы таким:
{ /* Список 2: {1,2,3}; {1,2,5}; {1,3,4}; {4,5,6} */
{1,2,3,...}, /* '1' есть в 1, 2 и 3-м массивах */
{1,2,0,...},
{1,3,0,...},
{3,4,0,...},
{2,4,0,...},
{4,0,...},
{0,...},
...
{0,...} /* 50-й массив */
}
Тогда расчет для каждого массива из длинного списка был бы таким:
int[][] pred;
...
for (int i = 0; i < 10; i++) {
for (int si = 0; ; si++) {
int from_short_list = pred[from_long_list[i] - 1][si];
if (!from_short_list) break;
<ячейка для from_long_list, from_short_list> ++;
}
}
Проблема в том, что сбор такой статистики происходит не один раз, а > 1000. И если одна итерация сбора всей статистики для двух списков происходит примерно за 5 секунд, то 1000 итераций соответственно за 1.5 часа.
Благо, эти итерации независимы и их можно раскидать по клиентам аналогично MapReduce и это сделано, только вот клиентов не так много, так что все равно медленно. Поэтому борьба идет за то чтобы уменьшить эти 5 секунд на одну итерацию.
надо найти однозначное преобразование что бы массив превратить в число и сравнивать уже числа
про множества — коммент выше
если есть повторяющиеся элементы то можно их отсортировать и преобразовать в число используя элементы как разряды в позиционной системе исчисления по основанию, которое есть максимум элементов или больше.
Если отсортировать массивы и «сжать» примитивным образом, чтобы избежать многократных проходов по одним и тем же эл-там: [1,1,1,1 0,0, 2, 2, 2, 2, 3] -> [(0,2), (1,4),(2,2), (3,1)]
после этого устанавливаем указатели на начало эталонного массива из первой группы и проверяемого из второй и проверяем кол-во совпадений, учитывая второе число.
// arr1, arr2 = проверяемые отсортированные сжатые массивы,
// arr[нечётный_индекс] = эл-т массива,
// arr[чётный_индекс] = кол-во вхождений этого значения
int i, j;
int matches = 0;
for(i = 0, j = 0; i < arr1.size() && j < arr2.size(); )
{
if(arr1[i] == arr2[j])
{
matches+= min(arr1[i+1], arr2[j+1];
i+=2; j+=2;
}
else if(arr1[i] < arr2[j]) { i+=2; }
else { arr2[j] < arr1[i] ) { j+= 2; }
}
Сложность проверки двух сжатых отсортированных массивов O(m+n), m и n их длины.
Некоторые массивы скорее всего будут вообще совпадать. В этом случае лучше перед сравнением вообще посчитать хэш их элементов и перед запуском сравнения сначала сравнить длины и хэши массивов. Если хэши совпадают, то можно пропустить проверку и добавлять длину несжатого массива.
Еще если значений в массиве всего 50, то 50 эл-тов спокойно можно разместить в 64-битных переменных (uint64_t в C++, наверняка в С# тоже есть). Если важно посчитать кол-во одинаковых значений в двух массивах, а не количество вхождений значения, то просто берём побитовую операцию AND и считаем установленные биты: pastebin.com/3rV0CEnQ
Как я понял у вас два списка — один ОЧЕНЬ большой, второй маленький (всего 100). Отсортируйте сам массив из 100 массивов, чтобы каждый следующий кортеж был больше предыдущего кортежа.
( кортеж {x1,x2,x3, ..} больше {y1,y2,y3, ...} если x1>y1 или x1=y1, но x2>y2, или x1=y1,x2=y2, но x3>y3 ...)
Берите первый элемент(т.е. массив) из массива массивов из 10 млн.массивов. Сравните ПОСЛЕДНИЙ элемент выбранного элемента и сравните с ПЕРВЫМИ элеменами отсортированного массива массивов (из 100). Затем возьмите второй с конца и сравните со вторыми элементами кортежей. И так далее для всех элементов выбранного первого массива из 10 млн. Затем возьмите второй элемент-массив (из 10 млн) и так далее.
Правило, на котором экономите следующее:
Если какой-либо элемент (m-i) для n-го массива из 10млн. меньше элемента i в кортеже j, значит можно уже не рассматривать кортеж j и все кортежи, большие кортежа j для сравнения n-го массива.
На этом будет экономия.
