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

Ответ 1

Хм... 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. Но я сомневаюсь, что вы заметили разницу в операции с привязкой ввода-вывода, подобной этой.

Ответ 2

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

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.

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

Ответ 3

Аналогичный подход

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

Ответ 4

Что-то вроде этого, возможно:

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, который (хотя и немного быстрее для поиска/вставки) изменит порядок всех строк.

Ответ 5

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

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);
}

Ответ 6

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

Ответ 7

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

Ответ 8

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

<infile sort | uniq > outfile

Ответ 9

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

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

Ответ 10

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

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

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

Ответ 11

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

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

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

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

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

Ответ 12

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

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

Ответ 13

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

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

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

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

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

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

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

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

Ответ 14

void deleteDuplicates(File filename) throws IOException{
    @SuppressWarnings("resource")
    BufferedReader reader = new BufferedReader(new FileReader(filename));
    Set<String> lines = new LinkedHashSet<String>();
    String line;
    String delims = " ";
    System.out.println("Read the duplicate contents now and writing to file");
    while((line=reader.readLine())!=null){
        line = line.trim(); 
        StringTokenizer str = new StringTokenizer(line, delims);
        while (str.hasMoreElements()) {
            line = (String) str.nextElement();
            lines.add(line);
            BufferedWriter writer = new BufferedWriter(new FileWriter(filename));
            for(String unique: lines){
                writer.write(unique+" ");               
            }
            writer.close();
        }
    }
    System.out.println(lines);
    System.out.println("Duplicate removal successful");
}