Фильтрация и сортировка большого количества пар ключ-значение (Java) - PullRequest
Новая
       21

Фильтрация и сортировка большого количества пар ключ-значение (Java)

0 голосов
/ 01 июля 2019

У меня очень большой набор пар ключ-значение (ТБ данных), считанных из некоторых файлов.

Для простоты, давайте предположим, что ключи и значения являются целыми числами.

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

Нет проблем, если выходной файл содержит более N записей для данного ключа, если среди них есть наименьшие 3 значения.

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

Сохранение всех данных в памяти явно не вариант.

Таким образом, я ищу какой-то кеш.Что-то, где я могу хранить отсортированный список для каждого ключа, который я найду, и как только будет достигнут определенный лимит размера, я просто сбрасываю половину записей из кэша на выход.LoadingCache Гуавы, похоже, не помогает мне здесь, потому что веса computed at entry creation time, and are static thereafter.

Есть ли конкретная структура данных / алгоритм, который я могу использовать / реализовать, который может помочь мне здесь?

1 Ответ

0 голосов
/ 02 июля 2019

Простой подход:

  1. Сортировка исходного файла. Критерием сортировки является ключ в порядке возрастания, значение в порядке убывания. Утилита Linux sort делает это быстро. (Ну, быстро, как быстро набрать команду. Сортировка терабайтов данных займет некоторое время.)
  2. Напишите программу, которая последовательно просматривает файл и сохраняет верхние значения N.

Вы все сделали.

Если данные распределены по нескольким файлам, где значения для определенного ключа могут быть в нескольких файлах, тогда вы сортируете каждый файл по отдельности, а затем объединяете несколько файлов вместе. Опять же, sort может сделать это для вас.

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

...