kolosovas

Сравнение в 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 часа выглядит нереально. нужен дешевый способ за один раунд выбрать небольшое количество подходящих и искать уже оптимальное среди них.

В вашем случае, даже если числа float, где то нужно хранить 15 000 000 * 500 000 * 4 = 30 000 000 000 000 это 30 терабайт. Это просто линейный блоб, файл в формате 4 байта на число. И это без индексов (они появятся когда вам понадобятся поисковые запросы по выборкам). Не вздумайте брать универсальные базы данных, у вас узкая специализация и практически любое другое готовое решение будет требовать от вас плату либо местом либо процессорным временем.

Никуда от этих чисел вам не деться!.

3 минуты на последовательность умноженные на 15 миллионов штук - это приговор, 31тысчу cpu дней, это вам кластер из тысячи процессоров надо на месяц загружать, и хорошо если можно использовать gpu (это может позволить одной машине делать не десяток вычислений а сотни за раз), тогда обойдетесь десятком инстансев амазона и за пару тройку недель посчитаете.

Поверьте, стоимость места в данном случае настолько мизерная что даже смешно ;)

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

Отличный пример, вам нужно посчитать матрицу якобиана для нейронной сети, изменяя значения весов по одному +e и -e. Т.е. нужно вычислить матрицу N*N чисел где N - количество весов в нейронной сетию Если решать задачу в лоб, это значит нужно O(N^3) вычислений - это дико много. Но, так как для каждого числа из матрицы в нейронной сети меняется только один вес, то почти в половине случаев вычисления веса будут использовать одни и те же числа (особенно если вес изменился в сети близко к ее концу) а значит если хранить промежуточные значения вычислений, можно их опускать. На практике хранить ВСЕ на постоянной основе не по требуется, достаточно используя знания в каком порядке идут вычисления (не важно в каком она будет считаться, пусть например с конца) можно рекурсивно считать нейронную сеть, храня эти промежуточные значения в стеке. Трудоемкость конечно все равно останется большой где то порядка O(N^2*log(N)*...) но за ускорение будет небошая плата в N*log(N) памяти

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