4 ms·

All of your examples work in memory.

justinsaccount 7y ago
Not exactly. sort (at least GNU sort) will end up doing external merge sort on temporary files if you give it more data than you have memory. Which, if you give it 100GB of 5 different strings, ends up being a huge waste.
- tuldia 7y ago
  Not only GNU sort, but also postgresql, mysql and many more... Please, "huge waste"? How do you sort something that does not fit in memory?
  - justinsaccount 7y ago
    Are you being difficult on purpose? I posted a comment on how 'sort | uniq -c | sort -n' is an interesting and very capable pipeline, but often misused and slower than other alternatives. > you are comparing Yes, I am comparing two methods of accomplishing the same thing. That is how comparing things works. > Please, "huge waste"? How do you sort something that does not fit in memory? Note how the full sentence included "if you give it 100GB of 5 different strings". If your input is 100GB of 5 different strings, then the hash table will easily fit in memory, and sorting the entire data set only to pass it to 'uniq -c' is indeed a 'huge waste'. There are tons of large data sets that only have a small number of unique values in particular fields. protocols, ports, http status codes, hour of the day, etc. 'sort | uniq -c | sort -n' will work for all of them, but not nearly as efficient a hash table.
    - tuldia 7y ago
      > Are you being difficult on purpose? Programming is about paying the bare minimum attention to the details. > [...] two methods of accomplishing the same thing [...] Absolutelly not. one prints: 72000000 hello 72000000 world the other hello 72000000 world 72000000 Now try both examples against a file with more than one column to understand what I'm talking about ;)
dredmorbius 7y ago
Even working in memory, there are different efficiencies for different methods. Awk includes an asort() function which can sort an array, such that it would be possible to create a similar process entirely within awk to the sort | uniq -c pipeline: #!/usr/bin/gawk -f { x[NR] = $1 } END { rc = asort(x) j=0 for(i in x) { if( x[i] "" == x[i-1] "" ) freq[j]++ else { j++ elem[j] = x[i] freq[j] = 1 } } for(j in elem) { printf( "%6i %s\n", freq[j], elem[j]) } } As compares with a hash-based counter: #!/usr/bin/gawk -f { x[$1]++ } END { for(i in x ) printf( "%6i %s\n", x[i], i ) } On a 2,000 value test dataset with 10 unique values: sort | uniq -c takes 0.019s (8 runs averaged) awk hash takes 0.023s (8 runs averaged) awk-implemented sort + unique takes 0.33s (8 runs averaged) In this case, sort | uniq is the fastest option. But the all-in-memory sort + separate tabulation of unique values in awk is notably slower (running in 143% of the time) than the also all-in-memory hash accumulator. As I bump up the dataset size (20,000 records) that discrepency increases, roughly 0.052s sort|uniq, 0.065s hash, and 0.217s ask sort-unique. TL;DR: test your assumptions, especially regarding performance. Note: Data were generated with a simple bash loop: for i in {1..2000}; do echo $((RANDOM%10)); done > data
- justinsaccount 7y ago
  With super small dataset sizes like that it'll fit in the L2 cache and can behave differently. I did test this though, and for 20,000 items generated with your loop: sort | uniq -c takes .017s (fastest out of a few runs) the awk command I used above takes .013s A trivial implementation I have in go takes .08s Additionally, using this 'protos' file which is 1,000,000 lines of tcp,udp,icmp: $ time (sort protos|uniq -c) 5915 icmp 332003 tcp 662082 udp real 0m0.232s user 0m0.739s sys 0m0.100s $ # fixed to count 'lines' and not the first column, which makes it faster. $ time awk '{lines[$0]++} END {for (l in lines) printf("%s %d\n", l, lines[l])}' < protos icmp 5915 udp 662082 tcp 332003 real 0m0.194s user 0m0.190s sys 0m0.004s $ time ./c < protos 662082 udp 332003 tcp 5915 icmp real 0m0.088s user 0m0.084s sys 0m0.005s so yes, I do test my assumptions.
  - 7y ago

Not exactly. sort (at least GNU sort) will end up doing external merge sort on temporary files if you give it more data than you have memory. Which, if you give it 100GB of 5 different strings, ends up being a huge waste.

tuldia 7y ago
Not only GNU sort, but also postgresql, mysql and many more... Please, "huge waste"? How do you sort something that does not fit in memory?
- justinsaccount 7y ago
  Are you being difficult on purpose? I posted a comment on how 'sort | uniq -c | sort -n' is an interesting and very capable pipeline, but often misused and slower than other alternatives. > you are comparing Yes, I am comparing two methods of accomplishing the same thing. That is how comparing things works. > Please, "huge waste"? How do you sort something that does not fit in memory? Note how the full sentence included "if you give it 100GB of 5 different strings". If your input is 100GB of 5 different strings, then the hash table will easily fit in memory, and sorting the entire data set only to pass it to 'uniq -c' is indeed a 'huge waste'. There are tons of large data sets that only have a small number of unique values in particular fields. protocols, ports, http status codes, hour of the day, etc. 'sort | uniq -c | sort -n' will work for all of them, but not nearly as efficient a hash table.
  - tuldia 7y ago
    > Are you being difficult on purpose? Programming is about paying the bare minimum attention to the details. > [...] two methods of accomplishing the same thing [...] Absolutelly not. one prints: 72000000 hello 72000000 world the other hello 72000000 world 72000000 Now try both examples against a file with more than one column to understand what I'm talking about ;)

dredmorbius 7y ago

Even working in memory, there are different efficiencies for different methods. Awk includes an asort() function which can sort an array, such that it would be possible to create a similar process entirely within awk to the sort | uniq -c pipeline: #!/usr/bin/gawk -f { x[NR] = $1 } END { rc = asort(x) j=0 for(i in x) { if( x[i] "" == x[i-1] "" ) freq[j]++ else { j++ elem[j] = x[i] freq[j] = 1 } } for(j in elem) { printf( "%6i %s\n", freq[j], elem[j]) } } As compares with a hash-based counter: #!/usr/bin/gawk -f { x[$1]++ } END { for(i in x ) printf( "%6i %s\n", x[i], i ) } On a 2,000 value test dataset with 10 unique values: sort | uniq -c takes 0.019s (8 runs averaged) awk hash takes 0.023s (8 runs averaged) awk-implemented sort + unique takes 0.33s (8 runs averaged) In this case, sort | uniq is the fastest option. But the all-in-memory sort + separate tabulation of unique values in awk is notably slower (running in 143% of the time) than the also all-in-memory hash accumulator. As I bump up the dataset size (20,000 records) that discrepency increases, roughly 0.052s sort|uniq, 0.065s hash, and 0.217s ask sort-unique. TL;DR: test your assumptions, especially regarding performance. Note: Data were generated with a simple bash loop: for i in {1..2000}; do echo $((RANDOM%10)); done > data

justinsaccount 7y ago
With super small dataset sizes like that it'll fit in the L2 cache and can behave differently. I did test this though, and for 20,000 items generated with your loop: sort | uniq -c takes .017s (fastest out of a few runs) the awk command I used above takes .013s A trivial implementation I have in go takes .08s Additionally, using this 'protos' file which is 1,000,000 lines of tcp,udp,icmp: $ time (sort protos|uniq -c) 5915 icmp 332003 tcp 662082 udp real 0m0.232s user 0m0.739s sys 0m0.100s $ # fixed to count 'lines' and not the first column, which makes it faster. $ time awk '{lines[$0]++} END {for (l in lines) printf("%s %d\n", l, lines[l])}' < protos icmp 5915 udp 662082 tcp 332003 real 0m0.194s user 0m0.190s sys 0m0.004s $ time ./c < protos 662082 udp 332003 tcp 5915 icmp real 0m0.088s user 0m0.084s sys 0m0.005s so yes, I do test my assumptions.
- 7y ago