4 ms·

I use "sort | uniq -c | sort -n | tail" all the time to find the most frequent items, so McIlroy's program is no surprise. Compared to something like python's

by jepler 9y ago

I use "sort | uniq -c | sort -n | tail" all the time to find the most frequent items, so McIlroy's program is no surprise. Compared to something like python's heapq.nlargest, though, there's a key difference: The first sort has to temporarily keep all the items (storage: O(n)) and it has to sort them all (time: O(n lg n)). With another algorithm, the storage is only O(d+m) where d is the number of distinct words and m is the number of most frequent items sought; and I think the complexity of the d operations on an m-item heap is O(d lg m). Since typically m << d << n, this can be a big savings in storage and time!

deleted 9y ago
[deleted]
LukeShu 9y ago
Since we're on the topic of Unix philosophers: "When in doubt, use brute force." -- Ken Thompson "Fancy algorithms are slow when n is small, and n is usually small. Fancy algorithms have big constants. Until you know that n is frequently going to be big, don't get fancy. (Even if n does get big, use Rule 2 [measure before you optimize] first.)" -- Rob Pike Which is to say: McIlroy's team had a culture that favored simpler solutions with worse storage/time, until actual usage informs them that performance is an issue.
- vram22 9y ago
  And also (after Rule 5): Rule 6: There is no Rule 6. :)
  - vram22 9y ago
    Hasty downvoter, do your research first. That Rule 6 was not made up by me, it was the real thing, by one of the people mentioned in the parent comment - Rob Pike: https://www.lysator.liu.se/c/pikestyle.html https://www.lysator.liu.se/c/pikestyle.html
    - LukeShu 9y ago
      I suspect you were not down-voted because they didn't believe that it was accurate, but because they believe that it didn't meaningfully contribute to the discussion.
- yongjik 9y ago
  ...and Rob Pike now works for Google, where the prevailing ethos is "If your service cannot run in three distributed datacenters with a million simultaneous connections, why even bother?" Well, I guess engineering is all about being successful and boring, in the long run.
- jepler 9y ago
  True enough, so I wondered: on a corpus of reasonable size, will the "sophisticated" python solution beat the "classic UNIX shell" solution. #!/usr/bin/env python3 import collections, sys if len(sys.argv) > 1: N = int(sys.argv[1]) else: N = 10 for line, count in collections.Counter(sys.stdin).most_common(N): print("%d\t%s" % (count, line.rstrip('\n'))) In either case, the "tr | tr |" part of the pipeline remains the same, but "| python3 commonline.py" replaces the rest of the original pipeline. On my system, with the input being the 100,117 word "kjv10.txt" (from project gutenberg a decade ago), the Python solution takes about 1/4 of the time, .974s best of 8 "real" time for the original pipeline, and .209s for the python3 pipeline. According to "perf stat", the classic solution has 2,938 page faults instead of 1,877 for the solution that includes Python. So even at this input size, you can measure the difference; and depending how often you ran the procedure, it might even pay off vs the time it took me to research and implement the Python version. (curiously, pulling the downcasing and splitting into python didn't seem beneficial)
- taeric 9y ago
  I've always felt, "while thinking about it, kick off a brute force attempt." Though, this is really only applicable to "one and done" tasks. Which is the majority of tasks you will run interactively.
ww520 9y ago
That's functional vs imperative programming.

by jepler 9y ago

deleted 9y ago

[deleted]

LukeShu 9y ago

Since we're on the topic of Unix philosophers: "When in doubt, use brute force." -- Ken Thompson "Fancy algorithms are slow when n is small, and n is usually small. Fancy algorithms have big constants. Until you know that n is frequently going to be big, don't get fancy. (Even if n does get big, use Rule 2 [measure before you optimize] first.)" -- Rob Pike Which is to say: McIlroy's team had a culture that favored simpler solutions with worse storage/time, until actual usage informs them that performance is an issue.

vram22 9y ago
And also (after Rule 5): Rule 6: There is no Rule 6. :)
- vram22 9y ago
  Hasty downvoter, do your research first. That Rule 6 was not made up by me, it was the real thing, by one of the people mentioned in the parent comment - Rob Pike: https://www.lysator.liu.se/c/pikestyle.html https://www.lysator.liu.se/c/pikestyle.html
  - LukeShu 9y ago
    I suspect you were not down-voted because they didn't believe that it was accurate, but because they believe that it didn't meaningfully contribute to the discussion.
yongjik 9y ago
...and Rob Pike now works for Google, where the prevailing ethos is "If your service cannot run in three distributed datacenters with a million simultaneous connections, why even bother?" Well, I guess engineering is all about being successful and boring, in the long run.
jepler 9y ago
True enough, so I wondered: on a corpus of reasonable size, will the "sophisticated" python solution beat the "classic UNIX shell" solution. #!/usr/bin/env python3 import collections, sys if len(sys.argv) > 1: N = int(sys.argv[1]) else: N = 10 for line, count in collections.Counter(sys.stdin).most_common(N): print("%d\t%s" % (count, line.rstrip('\n'))) In either case, the "tr | tr |" part of the pipeline remains the same, but "| python3 commonline.py" replaces the rest of the original pipeline. On my system, with the input being the 100,117 word "kjv10.txt" (from project gutenberg a decade ago), the Python solution takes about 1/4 of the time, .974s best of 8 "real" time for the original pipeline, and .209s for the python3 pipeline. According to "perf stat", the classic solution has 2,938 page faults instead of 1,877 for the solution that includes Python. So even at this input size, you can measure the difference; and depending how often you ran the procedure, it might even pay off vs the time it took me to research and implement the Python version. (curiously, pulling the downcasing and splitting into python didn't seem beneficial)
taeric 9y ago
I've always felt, "while thinking about it, kick off a brute force attempt." Though, this is really only applicable to "one and done" tasks. Which is the majority of tasks you will run interactively.

ww520 9y ago

That's functional vs imperative programming.