Мне нужно дедуплицировать большой список слов. Я попробовал несколько команд и провел некоторое исследование здесь и здесь, где они объясняют, что самый быстрый способ дедупликации списка слов, кажется, использует awk.
awk -> O (n)? сортировать -> O (n log n)?
Однако я обнаружил, что это, похоже, не соответствует действительности. Вот мои результаты тестирования:
sort -u input.txt -o output.txt реальный 0m12.446s
пользователь 0m11.347s
sys 0m0.906s
awk '!x[$0]++' input.txt > output.txtреальный 0m47.221s
пользователь 0m45.419s
sys 0m1.260s
Таким образом, использование сортировки -u происходит в 3,7 раза быстрее. Почему это? Есть ли еще более быстрый способ дедупликации?
*********** Обновить ********
Как кто-то указал в комментариях, возможно, мой список слов уже был в некоторой степени отсортирован. Чтобы исключить эту возможность, я сгенерировал два списка слов, используя этот скрипт на python .
List1 = 7 Мб
List2 = 690 Мб
Результаты AWK:
List1
реальный 0m1.643s
пользователь 0m1.565s
sys 0m0.062s
List2
реальный 2m6.918s
пользователь 2m4.499s
sys 0m1.345s
Результаты SORT:
List1
real 0m0.724s
user 0m0.666s
sys 0m0.048s
List2
real 1m27.254s
user 1m25.013s
sys 0m1.251s
источник
Ответы:
Вы задаете неправильный вопрос или задаете вопрос неправильно и в неправильном стеке, этот вопрос лучше задавать в переполнении стека / программирования, чтобы люди давали вам ответы на основе алгоритмов, используемых внутри awk и sort.
PS: также сделайте необходимое с nawk, mawk и gawk, чтобы дать нам больше деталей для «зоны в»;) и выполните пробеги по 100 раз с минимальным, максимальным, средним и стандартным отклонением.
В любом случае вернемся к рассматриваемому вопросу, взятому из CompSci 210, речь идет об используемых алгоритмах. Сортировка использует несколько, в зависимости от размеров и ограничений памяти, которые она ударила, чтобы сохранить файлы на диск во временных файлах, которые будут отсортированы слиянием, когда ему не хватит памяти, и вам придется заглянуть в исходный код, чтобы увидеть, что конкретная команда sort (1) использует конкретную операционную систему, на которой вы ее запускаете, но по своему опыту она загружает в память столько, сколько может, выполняет некоторую быструю сортировку, записывает на диск, повторяет промывку и при конец это будет делать сортировку слиянием небольших отсортированных файлов. Итак, здесь у вас будет O (n * log2 (N)) для частей, а затем приблизительная операция объединения O (n * log (n))
awk: механизм x [$ 0] ++ предполагает, что используется хеширование. НО проблема с хешированием, предполагаемой операцией поиска (1), заключается в коллизиях и обработке коллизий. Это может вызвать проблему, когда данные распределяются некорректно, не заполняются сегменты и т. Д., А в больших списках хеширование может быть большой проблемой с памятью, если обработка коллизий выполняется неправильно (и вам может понадобиться настроить алгоритмы хеширования для ожидаемых данных), а затем вам нужно посмотреть на производительность реальных функций хеширования, и тогда O (1) может быть ближе к O (log (n)) для вставок (т. е. O (1) для первого поиска, и если он НЕ существует, вы добавляете его, который может быть O (log (n))), и тогда n * O (1) становится * O (log (n)) = > O (n * log (n)), не говоря уже о том, что вы также делаете вещи «интерпретированным» образом :)
источник
Разница в скорости объясняется тем, что «sort» - это команда ( ссылка ), а «awk» - язык программирования ( ссылка ).
Команда 'sort' принимает ввод и возвращает вывод. Принимая во внимание, что «awk» является языком программирования, который сначала интерпретирует код (терминальную команду), а затем начинает обработку на нем. Просто как тот.
источник