python - プロットしたときの奇妙な結果（コーメン）赤黒木挿入

Question

Cormenの擬似コードに従って、Pythonの赤黒木に実装しましたIntroduction to Algorithms。

insert自分が本当に自分であるかどうかを自分の目で確認したかったので、ノードをツリーO(logn)に挿入するのにかかる時間をプロットしました。n=1, 10, 20, ..., 5000

結果は次のとおりです。

x-axisはnであり、-axisyはミリ秒単位の時間です。

私には、グラフは対数よりも線形に見えます。何がそれを説明できますか？

Answer 1

さて、グラフには、nツリーに要素を挿入するコストの測定値が表示されます。ここで、x軸は挿入した要素の数であり、y軸は合計時間です。

n個の要素をツリーに挿入するのにかかる時間を合計する関数を呼び出しましょうf(n)。

f次に、どのように見えるかについて大まかなアイデアを得ることができます。

f(1) < k*log(1)                 for some constant k.

f(2) < k*log(1) + k*log(2)      for some constant k

...

f(n) < k * [log(1) + log(2) + ... + log(n)]   for some constant k.

ログがどのように機能するかにより、折りたたむことができますlog(1) + ... + log(n)：

f(n) < k * [log(1*2*3*...*n)]     for some constant k

f(n) < k * log(n!)                for some constant k

ウィキペディアを見て、どのように見えるかのグラフを見ることができます。log(n!)記事のグラフを見てください。あなたにはかなりなじみがあるように見えるはずです。:)

つまり、これは誤って行ったと思います。

for n in (5000, 50000, 500000):
    startTime = ...
    ## .. make a fresh tree
    ## insert n elements into the tree
    stopTime = ...
    ## record the tuple (n, stopTime - startTime) for plotting

サイズnのツリーに1つの要素を挿入する個々のコストではなく、サイズnのツリーを構築するための合計時間をプロットします。

for n in range(50000):
    startTime = ...
    ## insert an element into the tree
    stopTime = ...
    ## record the tuple (n, stopTime - startTime) for plotting

---

クリス・テイラーはコメントの中で、プロットf(n)/nすると対数グラフが表示されると述べています。これは、がかなり厳密に近似されているためlog(n!)ですn*log(n)（ウィキペディアのページを参照）。だから私たちは自分の限界に戻ることができます：

f(n) < k * log(n!)                for some constant k

そして取得：

f(n) < k * n * log(n)             for some constant k

f(n)これで、で除算するnと、グラフが対数の形で上に囲まれることがわかりやすくなります。

Answer 2

5000対数を実際に「見る」には十分な大きさではない可能性があります。実行し50000てみてください500000。2秒と20秒かかる場合は、線形成長が理にかなっています。時間がかからない場合は、対数が理にかなっています。ほとんどの「単純な」関数を十分に拡大すると、結果はかなり直線的に見えます。

Answer 3

「なぜ」の質問には、常に一握りの憶測があります。あなたが見ているジャンプは、システムメモリ管理に関連しているのではないかと思います。システムが継続的な拡張のためにより大きなメモリスペースを割り当てる必要がある場合、プログラム全体の処理を完了するために一定の時間が追加されます。ノードに「ペイロード」フィールドを追加して、必要なストレージスペースの量を増やした場合、私は正しいですが、ジャンプがより頻繁に発生します。

ちなみに、素敵なグラフ。