Проверьте уникальные данные строки из файла с 5 миллионами строк в Java

Question

У меня большой файл со строкой типа ID|VALUE за один проход.

В случае повторения идентификатора, строка должна игнорироваться.

Как эффективно сделать эту проверку?
добавлено: Идентификатор длинный (8 байт). Мне нужно решение, которое использует минимум памяти.
Спасибо за помощь, ребята. Мне удалось увеличить пространство кучи и использовать Set сейчас.

Answer 1

Вы можете сохранить данные в TLongObjectHashMap или использовать TLongHashSet. Эти классы эффективно хранят информацию на основе примитивов.

5 миллионов длинных значений будут использовать <60 МБ в TLongHashSet, однако TLongObjectHashMap также будет эффективно хранить ваши значения. </p>

Чтобы узнать больше об этих классах

http://www.google.co.uk/search?q=TLongHashSet

http://www.google.co.uk/search?q=TLongObjectHashMap

Answer 2

Существует два основных решения:

Во-первых, как предложено выше duffymo и Andreas_D, вы можете сохранить все значения в Set.Это дает вам O (n) временную сложность и O (n) использование памяти.

Во-вторых, если O (n) памяти слишком много, вы можете сделать это в O (1) памяти, жертвуя скоростью.Для каждой строки в файле прочитайте все остальные строки перед ним и отмените, если идентификатор появляется перед текущей строкой.

Answer 3

Для меня это выглядит как типичная задача для базы данных. Если у вас есть база данных, используемая в вашем приложении, вы можете использовать ее для выполнения своей задачи. Создайте таблицу с полем UNIQUE INTEGER и начните добавлять строки; вы получите исключение для дублированных идентификаторов. Ядро базы данных позаботится об оконном перемещении курсора и кэшировании, чтобы оно соответствовало вашему бюджету памяти. Тогда просто бросьте этот стол, когда закончите.

Answer 4

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

Вы сами написали сценарий использования;здесь нет магии.

Answer 5

Вы должны будете хранить идентификаторы где-нибудь, чтобы обнаружить дубликаты. Здесь я бы использовал HashSet<String> и метод contains.

Answer 6

А как насчет вероятностных алгоритмов ?

Фильтр Блума ... - это вероятностная структура данных с эффективным использованием пространства, которая используется для проверки того, является ли элемент членом набора. Возможны ложные срабатывания, а ложные - нет.