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

Существует поле целых чисел от 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 часа расчетов? И вообще реально ли произвести подобного рода расчеты в разумное время?
  • Вопрос задан
  • 878 просмотров
Пригласить эксперта
Ответы на вопрос 5
Adamos
@Adamos
Вообще в комбинаторных задачах хранение - самое узкое место, и в первую очередь стоит думать не о том, как его оптимизировать, а как его избежать. То есть свести алгоритм к поточной обработке данных, как только они поступили, и сразу выбрасывать те, что не актуальны для дальнейшей работы.
Ответ написан
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
При анализе очередной последовательности нужно предусматривать критерии останова и перехода к следующей последовательности. Максимальные достижения (критерии) - хранить в промежуточном стеке. Т.е., как только текущий набор хуже критерия - сразу делаем выход из перебора значений текущего набора (break).
Изначально - берём сразу все наборы и параллельно перебираем их значения. Затем - отсеиваем наборы по мере ухудшения набранных критериев.
Ответ написан
Комментировать
@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) памяти
Ответ написан
sergiks
@sergiks Куратор тега PHP
♬♬
Несколько не связанных идей:
  1. хранить каждую «последовательность» (набор) из 500000 (не важно, сколько) чисел как картинку с 1-битным цветом, 3873*3873px, чтобы покрыть диапазон 0..15e6. Будет 15 млн. таких картинок. Черный пиксель - число, белый - нет числа. Картинки можно накладывать и смотреть, насколько потемнело ) Но в цифре это делать неэффективно, вот если бы аналогом..
  2. хранить последовательность как бинарную строку, где включённые биты означают выбранное число. 15e6 бит примерно 1875e3 байт =~1.9Mb на набор. 1875e3 * 15e6 = 28125e9 байт =~28Тб
  3. хранить как бинарный файл по 3 байта (24 бита) на число. 0–15 млн прекрасно уместятся: 224 = 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 лет. А вы за несколько дней собирались как-то?

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы