Как организовать обработку больших объемов данных?

Question

[kolosovas]

Существует поле целых чисел от 0 до 15 000 000.
По этому полю раз в три дня рассчитываются последовательности из 500 000 значений(алгоритмы расчета последовательностей меняются, можно считать случайными). Таких последовательностей 15 000 000, каждая последовательность отсортирована по возрастанию. Далее необходимо выбрать N последовательностей с максимальным охватом поля. Соответственно уложить расчеты в 3 часа и занять минимум вычислительных ресурсов.

Пример:
$sequence1 = array(n1=>1, n2=>5, n3=>100.....n500000 => 14900999) //1-я последовательность
$sequence2 = array(n1=>4, n2=>5, n3=>99.....n500000 => 14900999) //2-я последовательность
Последовательностей $sequence1, $sequence2......$sequence15000000 // 15 000 000 последовательностей по 500 000 значений
Считаем суммы уникальных значений поля для N последовательностей.
Выбираем последовательность с максимальной суммой.

Вопросы по задаче:
|. Подскажите, как лучше организовать систему хранения, или может быть решение не предусматривающее хранение всех данных?
||. Какие инструменты выбрать для расчетов?
|||. Подскажите быстрые алгоритмы сравнения больших объемов данных, ведь надо сравнивать 500 000 с 500 000 записей
|V. Разрешима ли данная задача в домашних условиях?

Мои мысли:
|. Расчеты одной последовательности идут долго порядка 3-х минут, поэтому предполагаю хранить последовательности
Идеи которые отлетели
sql- индексированная таблица для быстрых сравнений (одна таблица >10mb, 15 000 000 таблиц это 150ТБ, такой объем никто не даст)
txt - файл через запятую ( один файл >4мб, весь расчет уложится в 60ТБ, что тоже много)
zip- один файл >1mb, весь расчет уложится в 15ТБ, ближе к теме, но все равно много.
Может есть другие идеи хранения данных?

||. Взял php, sql, так как с ними знаком, возможно использование других инструментов

|||.Пробовал сравнение индексных таблиц join-м, скорость приемлемая, но надо иметь 15 000 000 индексных таблиц, что много по памяти
Сравнение в php count(array_diff($arr1, $arr2)), не получилось в два массива запихать по 500 000 значений, ошибка памяти, пробовал REDIS, он помогает, но пока запихаешь туда два массива времени уйдет много
Бегать перебором по массивам в цикле и проверять есть ли уже значение, вариант в лоб, дольше всего.

|V. Возможно ли используя 16гб оперативки, Core i7, 2TB HDD, уложиться в 3 часа расчетов? И вообще реально ли произвести подобного рода расчеты в разумное время?

Comments

[V Sh.]

значения в последовательностях могут повторяться?

[sim3x]

В каком виде и откуда приходят данные?
И какова конечная цель данной процедуры?

[kolosovas]

V Sh., Значения в одной последовательности уникальны и располагаются по возрастанию значений

[kolosovas]

sim3x, Данные каждой последовательности рассчитываются по формуле, которая меняется, можно считать функция RAND(0, 15000000)
Конечная цель получить список последовательностей с максимальным охватом, количество последовательностей задает гость, но в пределах N[3..1000]

[V Sh.]

kolosovas, тогда не совсем понятно, что подразумевается под максимальным охватом поля. Если значения в разрезе одной последовательности уникальны и взяты из исходного поля, то у всех последовательностей будет одинаковый охват поля по количеству (500к). Если же понимать под макс. охватом диапазон, то он будет просто равен разнице между последним и первым элементом последовательности (т.к. последовательности уже упорядочены по возрастанию). Собственно, вопрос: что такое максимальный охват поля чисел?

[Adamos]

V Sh., он считает охват не для одной последовательности. Нужно найти комбинацию из N последовательностей, дающих наибольший охват в сумме.
Хотя, признаться, не понимаю, почему нельзя просто формировать последовательности по одной, но длиной N * пол-лимона, ведь одинаковые данные в них предположительно уменьшают охват.

[V Sh.]

Adamos, а, ну теперь задача хотя бы обретает смысл... Такую задачу перебором явно не решить. Насколько я знаю, в таких задачах ищется не точный ответ, а максимально близкий.

[Adamos]

V Sh., ну да, честный оптимум в общем случае - только полным перебором. Но конкретные случаи могут позволять оптимизации, инварианты и ранние отсечки. С уменьшением времени перебора на порядки. Естественно, по расплывчатому описанию мы тут ничего не насоветуем...

[Zhainar]

насколько я понял, есть
15*10^6 элементов, элемент - это массив int[500000]
нужно найти максимальную сумму последовательных N элементов?

[Adamos]

Zhainar, откуда вы взяли "последовательных"? В том-то и затык, что нужно найти N элементов из 15 миллионов, которые вместе дадут некий максимальный результат.
Причем, судя по всему, предварительный отбор элемента, который даст лучший результат, чем другие, невозможен.

[kolosovas]

Adamos, Правильно я понял идею брать N последовательностей и объединять в одну на этапе расчета?
Если честно не могу сообразить как на этапе заполнения сформировать все возможные варианты 10-ток,
ведь надо сравнивать каждую последовательность с каждой, а таких последовательностей по N получается (Ц из N по K, где N[3..1000], а K=15 000 000 )
] N=10 => количество комбинаций 15 000 000!/ (15 000 000-10)!*10! Мне кажется многовато и где-то опять надо хранить.

[Adamos]

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

[kolosovas]

Adamos, Я скорей всего запутал словами "Последовательность значений".
Значения располагаются по возрастанию, но не являются непрерывно последовательными.
Пример:
1,5,6,68,97,150,......

[Zhainar]

Adamos, тогда это простая задача, надо найти суммы каждого элемента, отсортировать и взять наибольшие N элементов.

[Zhainar]

Условно в базе

select sum(item) as seq_sum from sequences group by sequence_id order by seq_sum desc limit N

[Adamos]

kolosovas, главный вопрос, имхо, таков: можете ли вы, проанализировав одну последовательность, что-то сказать о ее перспективности для перебора? Лучше она других, хуже или это выяснится только в комбинации с N - 1 других последовательностей?

Zhainar, очевидно, это не та простая задача, которую вы так решаете. Кстати, учитывая объемы данных, вы решаете ее неверно. Отбирать N оптимальных элементов можно еще в процессе обсчета, не храня все миллионы результатов и ничего не сортируя.

[Zhainar]

Adamos, в любом случае вам нужно все их пересчитать

[Adamos]

Zhainar, мне - нет. ТС - нужно, это само собой. Просто, судя по его описанию, ему приходится пересчитывать не 15 миллионов, а N комбинаций из 15 миллионов. А это немножко более охрененное количество.

[Сергей Соколов]

Правильно я понимаю «выбрать N последовательностей с максимальным охватом поля»?
Выбрать из M такие N последовательностей, которые относительно друг друга имеют минимум одинаковых/повторяющихся значений? Например из

1: 1 3 5 6
2: 1 4 5 6
3: 1 2 7 9

выбрать 1 и 3 (или 2 и 3), но не 1 и 2.

[Adamos]

Сергей Соколов, предлагаю не сбивать ТС с толку разными вопросами, а озадачить одним: описать по-человечески, что он на самом деле считает. А то мы тут ему догадками AI изобретем ;)

[kolosovas]

Перспективность одной последовательности можно попробовать оценить, если разбить диапазон 15 000 000 допустим по 1000, и смотреть какие диапазоны охватывает последовательность( в какие диапазоны попадают значения последовательности), допустим все скучковалось в последних, тогда с большей долей вероятности данной последовательности подойдет, та в которой диапазоны в начале списка.
Можно тогда свести задачу к сравнению не 500 000 значений последовательности, а к сравнению 500 диапазонов. Которые можно хранить кстати.

[kolosovas]

Сергей Соколов,
Да, все верно
1: 1 3 5 6 таких значений 500 000
2: 1 4 5 6 таких значений 500 000
3: 1 2 7 9 таких значений 500 000
4:
.
.
15 000 000: 10 20 67 89 таких значений 500 000

Выбрать N[3..1000] последовательность с минимальным повтором

[kolosovas]

kolosovas, Ошибся, диапазонов будет 15 000, а не 500

[Adamos]

kolosovas, если вам нужен минимальный повтор между последовательностями, то он в оптимуме нулевой. Стоит рассмотреть алгоритм их формирования и удлинить в N раз, а потом разбить. Тогда ничего хранить и комбинировать не потребуется вообще, вся математика будет решаться с каждой из последовательностей индивидуально.

[kolosovas]

Adamos, придется объединять N последовательностей из 15 000 000, а это (Ц из N по K, где N[3..1000], а K=15 000 000 )
] N=10 => количество комбинаций по N последовательностей = 15 000 000!/ (15 000 000-10)!*10!
Очень много комбинаций последовательностей. Или я не так понял вашу идею?

[Adamos]

kolosovas, нет, нужно искать возможность сразу формировать последовательности длины N * 500 000, обсчитывать их по мере формирования, откладывая самую лучшую, а по окончании подбора просто разбить ее на N последовательностей по 500 000.

[Сергей Соколов]

Обязательно ли генерировать последовательности по одной целиком от 1 до 500000-го числа, или можно по кругу всех 150000 цепочек: сначала каждой из них по 1-му числу, потом каждой по 2-му и т.д. до каждому по 500000-му?

[rPman]

kolosovas, если числа целые а последовательность гарантированно возрастающая, то можно хранить не сами числа в последовательности а разницу между соседними
1,5,6,68,97,150,...... -> 1,4,1,62,29,53
то можно хранить в числах меньшей разрядности но главное, сумма этих дельт будет там выше, где значения примерно менее сгруппированы, т.е. равномернее распределены по всему пространству чисел. При этом не важно, где в основном кучкуются значения, у вас будет дельта использоваться.

Answer 1

[Adamos]

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

Comments

[Сергей Соколов]

ТС пишет «Расчеты одной последовательности идут долго порядка 3-х минут», поэтому сложно обойтись без сохранения.

[АртемЪ]

Сергей Соколов, Тут все просто - узнаем сколько занимает времени и ресурсов хранение, сравниваем с этими тремя минутами, и решаем что выгоднее.

Answer 2

[xmoonlight]

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

Answer 3

[rPman]

В вашем случае, даже если числа 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) памяти

Comments

[kolosovas]

Спасибо, я подумаю в этом направлении

Почти наверняка алгоритмы у вас однотипные и еще более вероятно, возможно переиспользование данных из соседних последовательностей где-то из середины алгоритма.

Answer 4

[Сергей Соколов]

Несколько не связанных идей:

1. хранить каждую «последовательность» (набор) из 500000 (не важно, сколько) чисел как картинку с 1-битным цветом, 3873*3873px, чтобы покрыть диапазон 0..15e6. Будет 15 млн. таких картинок. Черный пиксель - число, белый - нет числа. Картинки можно накладывать и смотреть, насколько потемнело ) Но в цифре это делать неэффективно, вот если бы аналогом..
   
2. хранить последовательность как бинарную строку, где включённые биты означают выбранное число. 15e6 бит примерно 1875e3 байт =~1.9Mb на набор. 1875e3 * 15e6 = 28125e9 байт =~28Тб
   
3. хранить как бинарный файл по 3 байта (24 бита) на число. 0–15 млн прекрасно уместятся: 2²⁴ = 16 777 216. См. php функции pack() / unpack(). Один набор 500000 * 3 = 1.5Мб, 15млн наборов 22.5Тб
   
4. Не хранить всё. Полное покрытие диапазона 0..15 млн. идеально подобранными диапазонами по 500 тыс. потребует всего 30 таких диапазонов.
   
5. Гипотеза. Если все выборки действительно случайны, можно брать любые N, они окажутся хуже «настоящего» максимума лишь незначительно.
   
6. «Расчеты одной последовательности идут долго порядка 3-х минут» 180 секунд * 15e6 = 27e8 секунд, это почти 86 лет. А вы за несколько дней собирались как-то?
   
   

Comments

[kolosovas]

1) интересная мысль с учетом того что можно на один пиксель повесить огромное количество значений, если хранить rgb, вопрос как считывать значения, сохранить не беда, но вот при считывании цвета будут правильно ли определяться, проверю, мысль интересная
5,6) Выборки не случайны, задаются по формуле, по поводу 3 минут ошибся, последовательности считаются цугами(блоками), 3 минуты один блок. Формула вычисления последовательности дает смещение, сейчас изучаю, возможно получится по другому задавать последовательности

Answer 5

[Юрий]

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

Comments

[kolosovas]

Я пришел к выводу что можно разбить на блоки весь диапазон и смотреть сколько попало значений в диапазон, допустим по 10 000 диапазоны, тогда если в него попало 100 значений, то данный диапазон не рассматриваю, так как при пересечении с другой последовательностью вероятность что в диапазоне 10 000 значений пересекутся 100 очень мала.
GO обязательно гляну на предмет данной задачи, спасибо за подсказку