Как очень эффективно сравнить все строки в отсортированном файле (размер файла> 1 ГБ)
Допустим, входной файл:
Hi my name NONE
Hi my name is ABC
Hi my name is ABC
Hi my name is DEF
Hi my name is DEF
Hi my name is XYZ
Я должен создать следующий вывод:
Hi my name NONE 1
Hi my name is ABC 2
Hi my name is DEF 2
Hi my name is XYZ 1
Количество слов в одной строке может варьироваться от 2 до 10. Размер файла будет более 1 ГБ.
Как я могу получить требуемый вывод в минимально возможное время. Моя текущая реализация использует программу на C++, чтобы прочитать строку из файла, а затем сравнить ее со следующей строкой. Время выполнения этой реализации всегда будет O(n), где n - количество символов в файле.
Чтобы улучшить время выполнения, следующим вариантом является использование mmap. Но прежде чем приступить к реализации, я просто хотел подтвердить, есть ли более быстрый способ сделать это? Использование любого другого языка / сценариев?
3 ответа
uniq -c filename | perl -lane 'print "@F[1..$#F] $F[0]"'
Шаг perl предназначен только для вывода uniq (который выглядит как "2 Привет, меня зовут ABC") и измените порядок на "Привет, меня зовут ABC 2". Вы можете использовать для этого другой язык, или же полностью его оставить.
Что касается вашего вопроса о времени выполнения, big-O здесь неуместен; конечно, нет никакой возможности просканировать весь файл менее чем за O(n). mmap а также strchr кажется, что возможности для ускорения с постоянным коэффициентом, но подход на основе stdio, вероятно, достаточно хорош, если ваш stdio не отстой.
Код для BSD uniq может быть здесь иллюстративным. Это делает очень простую работу с fgets, strcmpи очень мало переменных.
В большинстве случаев эта операция будет полностью связана с вводом / выводом. (Особенно с использованием хорошо разработанного C++)
Учитывая это, вероятно, единственное узкое место, о котором вам нужно заботиться, это диск.
Я думаю, вы найдете это актуальным: mmap () против блоков чтения
У Бена Коллинза очень хороший ответ, сравнивающий mmap со стандартным чтением / записью.
Ну, есть две шкалы времени, которые вы сравниваете, которые на самом деле не связаны друг с другом. Первый - это алгоритмическая сложность, которую вы выражаете в нотации. Это, однако, не имеет ничего общего со сложностью чтения из файла.
Скажем, в идеальном случае у вас есть все ваши данные в памяти, и вы должны найти дубликаты с помощью алгоритма - в зависимости от того, как организованы ваши данные (например, простой список, хэш-карта и т. Д.), Вы можете найти дубликаты, которые вы можете использовать с O(n^2), O(n) или даже O(1), если у вас есть идеальный хеш (только для обнаружения элемента).
Чтение из файла или отображение в память не имеет никакого отношения к нотации "большой-О" вообще, поэтому вы не учитываете это для вычислений сложности вообще. Вы просто выберете тот, который занимает меньше времени, больше ничего.