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

Хм... 40 мегабайт кажется достаточно маленьким, чтобы вы могли построить Set строк, а затем распечатать их все обратно. Это было бы намного быстрее, чем выполнение операций ввода-вывода за O(n²).

Это будет примерно так (игнорируя исключения):

public void stripDuplicatesFromFile(String filename) {
    BufferedReader reader = new BufferedReader(new FileReader(filename));
    Set<String> lines = new HashSet<String>(10000); // maybe should be bigger
    String line;
    while ((line = reader.readLine()) != null) {
        lines.add(line);
    }
    reader.close();
    BufferedWriter writer = new BufferedWriter(new FileWriter(filename));
    for (String unique : lines) {
        writer.write(unique);
        writer.newLine();
    }
    writer.close();
}

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

Редактировать: Как отметил Алекс из Мастерской, если вы не возражаете против создания временного файла, вы можете просто распечатать строки по мере их чтения. Это позволяет вам использовать простой HashSet вместо LinkedHashSet. Но я сомневаюсь, что вы заметите разницу в такой операции ввода-вывода, как эта.

Хорошо, большинство ответов немного глупы и медленны, поскольку они включают добавление строк в какой-то хеш-набор или что-то еще, а затем снова перемещение их обратно из этого набора. Покажу самое оптимальное решение в псевдокоде:

Create a hashset for just strings.
Open the input file.
Open the output file.
while not EOF(input)
  Read Line.
  If not(Line in hashSet)
    Add Line to hashset.
    Write Line to output.
  End If.
End While.
Free hashset.
Close input.
Close output.

Пожалуйста, ребята, не усложняйте задачу больше, чем нужно. :-) Даже не беспокойтесь о сортировке, вам это не нужно.

Подобный подход

public void stripDuplicatesFromFile(String filename) {
    IOUtils.writeLines(
        new LinkedHashSet<String>(IOUtils.readLines(new FileInputStream(filename)),
        "\n", new FileOutputStream(filename + ".uniq"));
}

Что-то вроде этого, пожалуй:

BufferedReader in = ...;
Set<String> lines = new LinkedHashSet();
for (String line; (line = in.readLine()) != null;)
    lines.add(line); // does nothing if duplicate is already added
PrintWriter out = ...;
for (String line : lines)
    out.println(line);

LinkedHashSet сохраняет порядок вставки, в отличие от HashSet, который (хотя и немного быстрее для поиска/вставки) меняет порядок всех строк.

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

Set<String> uniqueStrings = new HashSet<String>();

// read your file, looping on newline, putting each line into variable 'thisLine'

    uniqueStrings.add(thisLine);

// finish read

for (String uniqueString:uniqueStrings) {
  // do your processing for each unique String
  // i.e. System.out.println(uniqueString);
}

Если порядок не имеет значения, простейшим способом является сценарий оболочки:

<infile sort | uniq > outfile

Попробуйте простой HashSet, в котором хранятся строки, которые вы уже прочитали. Затем переберите файл. Если вы сталкиваетесь с дубликатами, они просто игнорируются (поскольку набор может содержать каждый элемент только один раз).

• Прочитать в файле, сохранив номер строки и строку: O(n)
• Отсортируйте его в алфавитном порядке: O (n log n)
• Удалить дубликаты: O(n)
• Отсортируйте его в исходном порядке номеров строк: O (n log n)

Подход Hash Set в порядке, но вы можете настроить его так, чтобы не хранить все строки в памяти, а логический указатель на местоположение в файле, чтобы вы могли вернуться, чтобы прочитать фактическое значение, только если вам это нужно.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поэтому учитывайте сложность и использование памяти:

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

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

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

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

Все эти ответы основаны на том, что файл достаточно мал для хранения в памяти.

Если файл можно отсортировать, этот алгоритм можно использовать для файла любого размера.

Вам понадобится эта библиотека: https://github.com/lemire/externalsortinginjava

Я предполагаю, что вы начинаете с файла fileDumpCsvFileUnsorted, а закончите с новым файлом fileDumpCsvFileSorted, который отсортирован и не содержит дубликатов.

ExternalSort.sort(fileDumpCsvFileUnsorted, fileDumpCsvFileSorted);
int numDupes = 0;
File dupesRemoved = new File(fileDumpCsvFileSorted.getAbsolutePath() + ".nodupes");
String previousLine = null;
try (FileWriter fw = new FileWriter(dupesRemoved);
     BufferedWriter bw = new BufferedWriter(fw);
     FileReader fr = new FileReader(fileDumpCsvFileSorted);
     LineIterator lineIterator = new LineIterator(fr)
) {
  while (lineIterator.hasNext()) {
    String nextLine = lineIterator.nextLine();
    if (StringUtils.equals(nextLine, previousLine)) {
      ++numDupes;
      continue;
    }
    bw.write(String.format("%s%n", nextLine));
    previousLine = nextLine;
  }
}
logger.info("Removed {} dupes from {}", numDupes, fileDumpCsvFileSorted.getAbsolutePath());
FileUtils.deleteQuietly(fileDumpCsvFileSorted);
FileUtils.moveFile(dupesRemoved, fileDumpCsvFileSorted);

Файл fileDumpCsvFileSorted теперь создается отсортированным без дубликатов.