17

簡単に言えば、1986 年にあるインタビュアーが Donald Knuth に、入力にテキストと数字 N を取り、最もよく使われる N 個の単語を頻度順に並べてリストするプログラムを書くように依頼しました。Knuth は 10 ページの Pascal プログラムを作成し、Douglas McIlroy は次の 6 行のシェル スクリプトで応答しました。

tr -cs A-Za-z '\n' |
tr A-Z a-z |
sort |
uniq -c |
sort -rn |
sed ${1}q

全文はhttp://www.leancrew.com/all-this/2011/12/more-shell-less-egg/でお読みください。

もちろん、両者の目標は大きく異なっていました。Knuth は、読み書きのできるプログラミングの概念を示し、すべてをゼロから作成しました。一方、McIlroy は、いくつかの一般的な UNIX ユーティリティを使用して、最短のソース コードを作成しました。

私の質問は：それはどれほど悪いですか？
(純粋にランタイム速度の観点から言えば、6 行のコードは 10 ページよりも理解しやすく維持しやすいという点で、私たち全員が同意していると確信しているため、プログラミングの知識があるかどうかは関係ありません。)

sort -rn | sed ${1}q一般的な単語を抽出する最も効率的な方法ではないことは理解できますが、何が問題なのtr -sc A-za-z '\n' | tr A-Z a-zですか? 私にはかなり良さそうです。についてsort | uniq -c、それは周波数を決定するのに非常に遅い方法ですか?

いくつかの考慮事項:

  • tr線形時間にする必要があります (?)
  • sort確信は持てませんが、それほど悪くはないと思います
  • uniq線形時間も必要です
  • 生成プロセスは線形時間 (プロセス数) である必要があります
4

2 に答える 2

8

スクリプトには、いくつかのUnix線形操作と 2 つの並べ替えがあります。計算順になりますO(n log(n))。

上位 N のみを取得するための Knuth アルゴリズムの場合: http://en.wikipedia.org/wiki/Selection_algorithm アルゴリズムの時間と空間の複雑さでいくつかのオプションを使用できますが、理論的には、いくつかの典型的な例では高速になる可能性があります多数の（異なる）単語。

したがって、Knuth の方が高速である可能性があります。確かに英語の辞書はサイズが限られているからです。log(n)多くのメモリを消費する可能性がありますが、大きな定数になる可能性があります。

しかし、おそらくこの質問はhttps://cstheory.stackexchange.com/に適しています

于 2014-09-21T10:08:39.670 に答える