Сравнение в php count(array_diff($arr1, $arr2)), не получилось в два массива запихать по 500 000 значений, ошибка памяти
сам недавно пересечениями баловался, были массивы более 10М чисел, даже не сортированные.
1) в php 500к запихнуть легко, просто юзай ini_set memory_limit.
2) конечно же нельзя исопльзовать array_diff , исопльзуй array_diff_key это будет просто на порядок быстрее, тк по ключам там есть индекс. ну и массивы конечно надо перевернуть предварительно array_flip. по времени даже вместе со флипом оно будет на порядок быстрее.
3) в конце концов сделал на GO, точно не помню но по скорости получилось раз в 3-5 наверное быстрее. точно сравнивать сложно тк в php загрузка данных тоже была довольно медленной, да и памяти он расходует гораздо больше. если нужно посчитать пересечение в сортированных списках - нужно сделать цикл пробегаясь по обоим массивам одновременно за один проход.
примерно так:
func intersectCount(ids1, ids2 []uint32) int {
j := 0
cnt := 0
for i := 0; i < len(ids1); i++ {
for ;(j < len(ids2)) && (ids2[j] < ids1[i]); j++ {}
if (j < len(ids2)) && (ids2[j] == ids1[i]) {
cnt++
}
}
return cnt
}
на php конечно так делать бессмысленно, тк array_diff_key на С и будет на порядок быстрее.
ну и в целом по задаче, тут вам уже подсказали что идеальное решение в домашних условиях не найти. ищите просто любое неплохое, насколько приемлимо по задаче. чем меньше ресурсов имеете тем вероятно хуже оно будет.
у меня было 1000 списков чисел, в списках от 1 до 15 млн uint32 чисел. нужно было посчитать пересечением каждое с каждым. в один поток на не очень мощном компе это заняло около 3-4 часов.
очень много времени уходит на чтение с диска, поэтому загружал списки в память по 200 штук и высчитывал пересечение каждое с каждым, потом загружалась следующая партия и тд.
посчитать пересечение 15 млн списков каждое с каждым в лоб за 3 часа выглядит нереально. нужен дешевый способ за один раунд выбрать небольшое количество подходящих и искать уже оптимальное среди них.
