У меня есть огромное количество данных (хранится в файле, но это не имеет значения - основная часть заключается в том, что данные не помещаются в память) - скажем, 10 9 строк записей.
Запись состоит из времени, некоторого набора ключей и данных. Ключи не уникальны.
например
keys: data:
A | B | C |
----------------------
1 | 2 | 3 | 10
1 | 1 | 3 | 150
1 | 1 | 2 | 140
1 | 2 | 5 | 130
5 | 3 | 2 | 120
...
Мне нужно просмотреть все данные и отфильтровать их, используя пользовательский фильтр (это не проблема), а затем агрегировать, подсчитывать сумму и возвращать строки с самыми высокими данными.
Например, в данных я хочу суммировать каждую группировку данных по A и C.
ожидаемый результат:
A | C | data
------------
1 | 3 | 160
1 | 2 | 140
1 | 5 | 130
------------ following (data isn't in 3 highest value) doesn't concern me.
5 | 2 | 120
Я реализовал это, используя наивное решение, у меня есть Dictionary<tuple(A, C), long>, и сумма там. Но проблема в том, что в памяти может быть больше уникальных комбинаций A, C, чем я могу.
Я не могу предварительно суммировать какие-либо данные, так как может появиться какая-либо фильтрация, или использовать SQL (реляционная БД мне не подходит).
Существуют ли алгоритмы с эффективным использованием памяти, пригодные для группировки таким образом? Как SQL обрабатывает так много данных? Я могу группировать по SQL, но есть несколько причин, по которым я не хочу его использовать.
Или что мне гуглить? Я не нашел ни одной полезной статьи по этому вопросу.
(я использую C #, вопрос скорее теоретический, чем «используйте следующий код:»)