Как очень эффективно сравнить все строки в отсортированном файле (размер файла> 1 ГБ)

Question

Допустим, входной файл:

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

Answer 1

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 и очень немногими переменными.

Answer 2

В большинстве случаев эта операция будет полностью связана с вводом / выводом.(Особенно с использованием хорошо разработанного C ++)

Учитывая, что, вероятно, единственное узкое место, о котором вам нужно заботиться, это диск.

Я думаю, вы найдете это актуальным: mmap () против блоков чтения

Бен Коллинз дает очень хороший ответ, сравнивая mmap со стандартным чтением / записью.

Answer 3

Ну, есть две шкалы времени, которые вы сравниваете, которые на самом деле не связаны друг с другом. Первый - это алгоритмическая сложность, которую вы выражаете в нотации. Это, однако, не имеет ничего общего со сложностью чтения из файла.

Скажем, в идеальном случае у вас есть все ваши данные в памяти, и вы должны найти дубликаты с помощью алгоритма - в зависимости от того, как организованы ваши данные (например, простой список, карта хеш-функции и т. Д.), Вы можете найти дубликаты, которые могли используйте O (n ^ 2), O (n) или даже O (1), если у вас есть идеальный хеш (только для обнаружения элемента).

Чтение из файла или отображение в память не имеет никакого отношения к нотации "большой-О" вообще, так что вы вообще не учитываете это для вычислений сложности. Вы просто выберете тот, который занимает меньше времени - больше ничего.