Java эффективная дедупликация

Question

Допустим, у вас большой текстовый файл. Каждая строка содержит идентификатор электронной почты и некоторую другую информацию (скажем, некоторый идентификатор продукта). Предположим, что в файле миллионы строк. Вы должны загрузить эти данные в базу данных. Как бы вы эффективно расшифровывали данные (то есть исключали дубликаты)?

Answer 1

Безумное количество рядов

• Используйте каркас Map & Reduce (например, Hadoop). Это полноценные распределенные вычисления, поэтому это излишне, если у вас нет данных в ТБ. (j / k :))

Невозможно разместить все строки в памяти

• Даже результат не подходит: используйте сортировку слиянием, сохраняя промежуточные данные на диск. При слиянии вы можете отказаться от дубликатов (вероятно, этот пример помогает). Это может быть многопоточным, если хотите.
• Результаты будут соответствовать: вместо того, чтобы читать все данные в памяти и затем помещать их в HashSet (см. Ниже), вы можете использовать линейный итератор или что-то еще и продолжать добавлять этот HashSet. Вы можете использовать ConcurrentHashMap и использовать несколько потоков для чтения файлов и добавления к этой карте. Другим многопоточным вариантом является использование ConcurrentSkipListSet. В этом случае вы будете реализовывать compareTo () вместо equals () / hashCode () (compareTo () == 0 означает дублирование) и продолжите добавлять к этому SortedSet.

Умещается в памяти

• Разработайте объект, содержащий ваши данные, реализуйте хороший метод equals () / hashCode () и поместите их все в HashSet.
• Или используйте методы, приведенные выше (вы, вероятно, не хотите сохранять их на диске).

О, и на вашем месте я все равно наложу уникальное ограничение на БД ...

Answer 2

Взгляните на Duke (https://github.com/larsga/Duke) - быстрый механизм дедупликации и записи, написанный на Java. Он использует Lucene для индексации и сокращения количества сравнений (чтобы избежать недопустимого декартового сравнения продуктов). Он поддерживает наиболее распространенный алгоритм (редактирование расстояния, jaro winkler и т. д.), и он чрезвычайно расширяемый и настраиваемый.

Answer 3

У вас есть два варианта,

1. сделать это в Java: вы можете собрать что-то вроде HashSet для тестирования - добавление идентификатора электронной почты для каждого элемента, который появляется, если его нет в наборе.

2. сделать это в базе данных: наложить уникальное ограничение на таблицу, чтобы дубликаты не добавлялись в таблицу. Дополнительным бонусом является то, что вы можете повторить процесс и удалить дубли с предыдущих прогонов.

Answer 4

Начну с очевидного ответа. Создайте хэш-карту и введите идентификатор электронной почты в качестве ключа, а остальную информацию - в значение (или создайте объект для хранения всей информации). Когда вы доберетесь до новой строки, проверьте, существует ли ключ, перемещается ли он на следующую строку. В конце запишите все ваши операторы SQL, используя HashMap. Я согласен с eqbridges, что ограничения памяти будут важны, если у вас есть «gazillion» строк.

Answer 5

Ваша проблема может быть решена с помощью Извлечения, преобразования, загрузки (ETL) подхода:

• Вы загружаете свои данные в схему импорта;
• Выполняйте любые преобразования данных, которые вам нравятся;
• Затем загрузите его в схему целевой базы данных.

Вы можете сделать это вручную или использовать инструмент ETL.

Answer 6

Не можете ли вы проиндексировать таблицу по электронной почте и идентификатору продукта? Затем чтение по индексу должно сделать дубликаты либо электронной почты, либо электронной почты + prodId, легко идентифицируемые путем последовательного чтения и просто совпадающие с предыдущей записью.