Память эффективный способ удалить дублирующиеся строки в текстовом файле с помощью C++
Какова большая часть памяти эффективный способ удалить дублирующиеся строки в файле крупного текста с помощью C++?
Позвольте мне разъясниться, я не прошу код, просто лучший метод. Дублирующиеся строки, как гарантируют, не будут смежны. Я понимаю, что подход, оптимизированный для минимального использования памяти, привел бы к более медленным скоростям однако, это - мое ограничение, поскольку файлы являются слишком большими.
5 ответов
Я бы хешировал каждую строку, а затем возвращался к строкам, которые имеют неуникальные хеши, и сравнивал их по отдельности (или в буферизованном режиме). это будет хорошо работать с файлами с относительно низким количеством дубликатов.
Когда вы используете хэш, вы можете установить постоянный объем используемой памяти (т. Е. У вас может быть крошечная хеш-таблица с 256 слотами или чем-то большим. В любом случае количество памяти может быть ограничено любым постоянное количество.) значения в таблице - это смещение строк с этим хешем. поэтому вам понадобится только line_count * sizeof (int) плюс константа для поддержки хеш-таблицы.
Еще проще (но намного медленнее) сканировать весь файл для каждой строки. но я предпочитаю первый вариант. это наиболее эффективный вариант с точки зрения памяти. вам нужно будет сохранить только 2 смещения и 2 байта для сравнения.
Чтобы минимизировать использование памяти:
Если у вас неограниченный (или очень быстрый) дисковый ввод-вывод, вы можете написать каждая строка в свой собственный файл с именем файла, являющимся хешем + некоторый идентификатор, указывающий порядок (или без порядка, если порядок не имеет значения). Таким образом, вы используете файловую систему как расширенную память. Это должно быть намного быстрее, чем повторное сканирование всего файла для каждой строки.
В дополнение к сказанному ниже, если вы ожидаете высокой скорости дублирования, вы можете поддерживать некоторый порог хэшей в памяти, а также в файле. Это дало бы гораздо лучшие результаты при высоком уровне дублирования. Поскольку файл такой большой, я сомневаюсь, что n ^ 2 приемлемо для времени обработки. Мое решение - O (n) по скорости обработки и O (1) в памяти. Это O (n) необходимого дискового пространства, используемого во время выполнения, однако, которого нет в других решениях.
Похоже, вы работаете на ограниченном оборудовании с различными характеристиками, поэтому вам нужно протестировать несколько алгоритмов удаления дубликатов и профилей, прежде чем вы решите, какой из них лучше всего подходит для долгосрочной реализации.
Почему бы просто не проконсультироваться с Knuth, Sorting and Searching ? Это даст вам отличный фон для принятия взвешенного решения.
Простое решение методом перебора (очень небольшое потребление памяти): Выполните n ^ 2 проход через файл и удалите повторяющиеся строки. Скорость: O (n ^ 2), Память: константа
Быстро (но плохо, потребление памяти): Решение Стефана Кендалла: хэшируйте каждую строку, сохраните их на какой-либо карте и удалите строку, уже существует. Скорость: O (n), память: O (n)
Если вы готовы пожертвовать порядком файлов (я полагаю, что нет, но я добавлю его): Вы можете отсортировать строки, тогда пройти через удаление дубликатов. скорость: O (n * log (n)), Память: константа
edit: Если вам не нравится идея сортировки содержимого файла или попытки сохранить уникальные хэши, но вы можете обрабатывать память O (n) Использование: вы можете идентифицировать каждую строку с помощью 32-битного или 64-битного маркера позиции (в зависимости от размера файла) и отсортировать позиции файла вместо содержимого файла.
править №2: предостережение: строки сортировки в памяти разной длины сложнее, чем сказать, массив целых чисел ... на самом деле, думая о том, как память должна сдвигаться и перемещаться на этапе слияния, Я предполагаю, что могу отсортировать такой файл в n * log (n)
Вы можете использовать эффективную сортировку ввода-вывода (как команда unix sort) и затем читать файл построчно, сравнивая каждую строку с ранее прочитанной. Если они равны, то ничего не выводить, если не равны, то вывести строку.
Таким образом, объем памяти, используемый алгоритмом, остается постоянным.