Linux удалить повторяющиеся строки
Обновлено: 02.07.2024
Огромный (до 2 ГиБ) мой текстовый файл содержит около 100 точных дубликатов каждой строки в нем (в моем случае это бесполезно, поскольку файл представляет собой таблицу данных, похожую на CSV).
Что мне нужно, так это удалить все повторения, при этом (желательно, но этим можно пожертвовать ради значительного повышения производительности), сохраняя первоначальный порядок последовательности. В результате каждая строка должна быть уникальной. Если было 100 одинаковых строк (обычно дубликаты распределяются по файлу и не будут соседями), остается только один из них.
Я написал программу на Scala (рассмотрим Java, если вы не знаете о Scala), чтобы реализовать это. Но, может быть, есть более быстрые собственные инструменты, написанные на C, способные сделать это быстрее?
ОБНОВЛЕНИЕ: awk '!seen[$0]++' filename решение, казалось, работало очень хорошо для меня, пока файлы были около 2 ГБ или меньше, но теперь, когда я собираюсь очистить файл 8 ГБ, оно больше не работает. Кажется, что бесконечность на Mac с 4 ГБ ОЗУ и 64-битном ПК с Windows 7 с 4 ГБ ОЗУ и подкачкой 6 ГБ просто не хватает памяти. И я не испытываю энтузиазма по поводу того, чтобы попробовать это на Linux с 4 ГБ RAM, учитывая этот опыт.
это разрушит ваш порядок, но, если вы пробовали сортировать -u, я понятия не имею, как или если он может работать на таком массивном файле C часто не значительно быстрее, чем Java, и если вы запускаете его (по порядку) сейчас, есть большая вероятность, что он завершится до того, как вы получите ответ здесь, внедрите его, и он завершит работу; не в порядке, sort -u вероятно, будет быстрее. Просто попробовал это на 2G файле, и это заняло три минуты на моем ноутбуке. Неплохо. Я также попытался uniq имя файла | awk '! seen [$ 0] ++', но это было не так быстро. Это на удивление быстрее, чем более подробная awk версия, использующая 2 поиска в массивах (показано в расширенном объяснении в ответе Жиля): 0m36.132s против 0m49.958s .. для 50 миллионов строк . Я думал, что узким местом будет ввод / вывод, но дополнительный поиск в массиве . 1 миллион элементов в массиве, кажется, делает довольно существенную вмятину . @HashWizard: эта команда не сортирует, но устраняет все последующие вхождения одной и той же строки @MaxWilliams да, это работает, они случайным образом распределены.Существует простой (не сказать очевидный) метод, использующий стандартные утилиты, который не требует большого объема памяти, кроме как для запуска sort , который в большинстве реализаций имеет специфические оптимизации для больших файлов (хороший алгоритм внешней сортировки). Преимущество этого метода в том, что он зацикливается только на всех строках внутри специальных утилит, а не внутри интерпретируемых языков.
Если все строки начинаются с непробельного символа, вы можете обойтись без некоторых параметров:
Для большого количества дублирования метод, который требует только сохранения одной копии каждой строки в памяти, будет работать лучше. С некоторыми дополнительными интерпретациями для этого есть очень лаконичный сценарий awk (уже опубликованный enzotib ):
Менее сжато: !seen[$0] то есть вывести текущую строку, если она еще не видна, затем увеличить seen счетчик для этой строки (неинициализированные переменные или элементы массива имеют числовое значение 0).
Для длинных строк вы можете сэкономить память, сохраняя только несанкционированную контрольную сумму (например, криптографический дайджест) каждой строки. Например, используя SHA-1, вам нужно всего 20 байтов плюс постоянные издержки на строку. Но вычисление дайджестов происходит довольно медленно; Этот метод выиграет, только если у вас быстрый ЦП (особенно с аппаратным ускорителем для вычисления дайджестов) и не достаточно памяти относительно размера файла и достаточно длинных строк. Никакая базовая утилита не позволяет вычислить контрольную сумму для каждой строки; вам придется нести ответственность за интерпретацию Perl / Python / Ruby /… или написать специальную скомпилированную программу.
Читайте также: