Вот предварительное решение, основанное на описании проблемы в комментарии ОП к моему другому ответу:
Миллион записей, каждая из которых имеет 3k имен-> числовых пар.Учитывая подмножество миллионов записей и подмножество имен, вы хотите среднее значение для каждого имени для всех записей в подмножестве.Таким образом, каждое возможное подмножество (каждого возможного размера) миллиона записей является слишком большим для вычисления и хранения.
Предварительный расчет
Сначала мы разбиваем данные на меньшие 'windows '(осколки, страницы, разделы).
Допустим, каждое окно содержит около 10 тыс. строк с примерно 20 тыс. различных имен и 3 тыс. пар (имя, значение) в каждой строке (выбор размера окна может повлиять на производительность, ивам может быть лучше с меньшими окнами).
Если предположить, что ~ 24 байта для имени и 2 байта для значения, каждое окно содержит 10k * 3k * (24 + 2 байта) = 780 МБ данных плюс некоторые издержкичто мы можем игнорировать.
Для каждого окна мы предварительно рассчитываем количество вхождений каждого имени, а также сумму значений для этого имени.С этими двумя значениями мы можем вычислить среднее значение для имени по любому набору окон следующим образом:
Average for name N = (sum of sums for N)/(sum of counts for N)
Вот небольшой пример с гораздо меньшим количеством данных:
Window 1
{'aaa':20,'abcd':25,'bb':10,'caca':25,'ddddd':50,'bada':30}
{'aaa':12,'abcd':31,'bb':15,'caca':24,'ddddd':48,'bada':43}
Window 2
{'abcd':34,'bb':8,'caca':22,'ddddd':67,'bada':9,'rara':36}
{'aaa':21,'bb':11,'caca':25,'ddddd':56,'bada':17,'rara':22}
Window 3
{'caca':20,'ddddd':66,'bada':23,'rara':29,'tutu':4}
{'aaa':10,'abcd':30,'bb':8,'caca':42,'ddddd':38,'bada':19,'tutu':6}
Предварительно вычисленное окно 1'index' с суммами и счетами:
{'aaa':[32,2],'abcd':[56,2],'bb':[25,2],'caca':[49,2],'ddddd':[98,2],'bada':[73,2]}
Этот 'index' будет содержать около 20k различных имен и двух значений для каждого имени, или 20k * (24 + 2 + 2 байта) = 560 КБ данных,Это в тысячу раз меньше, чем сами данные.
Запросы
Теперь давайте приведем это в действие: учитывая вход, охватывающий 1 миллион строк, вам нужно будет загрузить (1M /10k) = 100 индексов или 56 МБ, что легко помещается в память на одной машине (черт, она поместится в память на вашем смартфоне).
Но поскольку вы агрегируете результаты, вы можете добиться еще лучших результатов;вам даже не нужно загружать все индексы одновременно, вы можете загружать их по одному, фильтровать и суммировать значения и отбрасывать индекс перед загрузкой следующего.Таким образом, вы можете сделать это с помощью нескольких мегабайт памяти.
Что еще более важно, для любого набора окон и имен вычисление должно занять не более нескольких секунд.Если имена отсортированы в алфавитном порядке (еще одна полезная предварительная оптимизация), вы получите лучшую производительность, но даже с несортированными списками она должна работать более чем достаточно быстро.
Угловые случаи
Осталось только одноДля этого нужно обработать случай, когда входной диапазон не совпадает точно с предварительно рассчитанными окнами.Это требует немного логики для двух «концов» входного диапазона, но его можно легко встроить в ваш код.
Скажем, каждое окно содержит ровно одну неделю данных, с понедельника по воскресенье, ноВаш ввод указывает период, начиная со среды.В этом случае вам потребуется загрузить фактические необработанные данные со среды по воскресенье первой недели (несколько сотен мегабайт, как мы отмечали выше), чтобы сначала рассчитать (количество, сумма) кортежей для каждого имени, а затем использовать индексы дляостальная часть входного диапазона.
Это добавляет некоторое время обработки к вычислению, но с верхней границей 2 * 780 МБ оно все еще очень удобно помещается на одной машине.
По крайней мере, так я бы это сделал.