Удаление повторяющихся строк в файле с использованием Java

Question

Как часть проекта, над которым я работаю, я бы хотел очистить файл, который я генерирую, от повторяющихся записей строк. Однако эти дубликаты часто не встречаются рядом друг с другом. Я придумал способ сделать это в Java (который в основном делал копию файла, а затем использовал вложенный оператор while для сравнения каждой строки в одном файле с остальной частью другого). Проблема в том, что мой сгенерированный файл довольно большой и тяжелый (около 225 тыс. Строк текста и около 40 мегабайт). Я считаю, что мой текущий процесс занимает 63 часа! Это определенно не приемлемо.

Однако для этого мне нужно интегрированное решение. Желательно на Яве. Есть идеи? Спасибо!

Answer 1

Я сделал два предположения для этого эффективного решения:

1. Существует BLOB-эквивалент строки или мы можем обработать его как двоичный файл
2. Мы можем сохранить смещение или указатель на начало каждой строки.

На основании этих предположений решение: 1. прочитайте строку, сохраните длину в hashmap как ключ, чтобы у нас была более легкая hashmap. Сохраните список как запись в hashmap для всех строк, длина которых указана в ключе. Построение этой хэш-карты - это O (n). При сопоставлении смещений для каждой строки в хэш-карте сравните двоичные объекты со всеми существующими записями в списке строк (смещений) для этой длины ключа, за исключением записи -1 в качестве смещения. Если найден дубликат, удалите обе строки и сохраните смещение - 1 в этих местах в списке.

Итак, рассмотрим сложность и использование памяти:

Память Hashmap, сложность пространства = O (n), где n - количество строк

Сложность времени - если нет дубликатов, но все строки одинаковой длины, учитывая длину каждой строки = m, рассмотрим количество строк = n, тогда это будет O (n). Поскольку мы предполагаем, что можем сравнивать BLOB-объекты, значение m не имеет значения. Это был худший случай.

В других случаях мы экономим на сравнениях, хотя у нас будет немного дополнительного места, необходимого в hashmap.

Кроме того, мы можем использовать mapreduce на стороне сервера, чтобы разделить набор и объединить результаты позже. И используя длину или начало строки в качестве ключа сопоставления.

Answer 2

Имеет ли значение, в каком порядке идут строки, и сколько дубликатов вы рассчитываете увидеть?

Если нет, и если вы рассчитываете на большое количество дураков (т. Е. Намного больше читаете, чем пишете), я бы также подумал о распараллеливании решения хэш-набора с хэш-набором в качестве общего ресурса. ,

Answer 3

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

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

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

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

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

Answer 4

Если бы вы могли использовать команды оболочки UNIX, вы могли бы сделать что-то вроде следующего:

for(i = line 0 to end)
{
    sed 's/\$i//2g' ; deletes all repeats
}

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