Fastest way to delete duplicates in large wordlist?

Question

I need to deduplicate a large wordlist. I tried several commands and did some research in Fastest `uniq` tool in linux and How to remove duplicate lines in a large multi-GB textfile? where they explain that the fastest way to deduplicate a wordlist seems to be using awk.

awk  --> O(n) ?
sort --> O(n log n) ?

However, I found that this seems to be not true. Here are my testing results:

time sort -u input.txt -o output.txt 
real    0m12.446s  
user    0m11.347s  
sys 0m0.906s**


time awk '!x[$0]++' input.txt > output.txt
real    0m47.221s  
user    0m45.419s  
sys 0m1.260s

So using sort -u is 3.7 times faster. Why is this? is there an even faster method to do deduplication?

*********** Update ********

As someone pointed out in the comments, it could be that my wordlist was already sorted to some extent. To exclude this possibility I generated two wordlists using random_number_wordlist_generator.py.

List1 = 7 Mb  
List2 = 690 Mb

**Results AWK:**  
***List1***  
real    0m1.643s  
user    0m1.565s  
sys     0m0.062s

***List2***  
real    2m6.918s  
user    2m4.499s  
sys     0m1.345s

**Results SORT:**  
***List1***  
real    0m0.724s  
user    0m0.666s  
sys     0m0.048s

***List2***  
real    1m27.254s  
user    1m25.013s  
sys     0m1.251s

Answer 1

You are asking the wrong question, or asking the question wrongly and in the wrong stack, this is a better question to ask in the programming/stack-overflow for people to give you answers based on the algorithms used inside awk and sort.

PS: also do the needed with nawk, mawk and gawk to give us some more details to "zone into" ;) and do the runs like a 100 times each with the min, max, avg and standard deviation.

Any case back to the question at hand, from CompSci 210, it is about the algorithms used. Sort makes use of several, depending on the sizes, and memory constraints it hit to save files out to disk in temporary files to be merge sorted once it ran out of memory, and you'll have to look into the source code to see what the specific sort(1) command uses on the specific OS your are running it on, but from experience it's loading into memory as much as it can, do some quick-sort on it, write out to disk, rinse repeat, and at the end it'll do a merge-sort of the small sorted files. So here you'll have the O(n*log2(N)) for the parts, and then a approximate O(n*log(n)) merging operation

awk: The x[$0]++ mechanism is "suppose" to use hashing. BUT the problem with hashing, a supposed O(1) "lookup" operation, is collisions, and the handling of collisions. This might cause a problem when the data isn't nicely spread, nor filling the buckets etc. and in large lists, the hashing might be a big memory problem if the handling of the collisions isn't done right (and you might need to tune the hashing algorithms for the data expected), and then you need to look at the performance of the actual hashing functions and then the O(1) might be closer to a O(log(n)) for the inserts (Ie. O(1) for the first search, and if it does NOT exist you add it which could be O(log(n))), and that then the n*O(1) becomes a n*O(log(n))=> O(n*log(n)), not to mention you are also doing things in a "interpreted" manner :)

Answer 2

I'd look hard how to use sort -u (possibly with further switches!) for the task, before breaking out some serious scripting language (Python/Perl/Raku, very probably after sorting), and only after seeing absolute need for utmost speed would I consider other alternatives.

Answer 3

The speed difference is because 'sort' is a command (link), whereas 'awk' is a programming language (link).

'sort' command is takes input and return output. Whereas 'awk' is a programming language, which first interprets the code (terminal command) then starts processing on it. Simple as that.