Scala のベクトルの分岐係数が 32 で、他の数ではない理由は何ですか? より小さな分岐因子は、より多くの構造共有を可能にするのではないでしょうか? Clojure は同じ分岐係数を使用しているようです。私が見逃している分岐係数 32 についての魔法はありますか?
質問する
456 次
4 に答える
13
分岐要因とは何かを説明すると役立ちます。
ツリーまたはグラフの分岐係数は、各ノードの子の数です。
したがって、答えは主にここにあるようです。
http://www.scala-lang.org/docu/files/collections-api/collections_15.html
ベクトルは、分岐係数の高いツリーとして表されます。各ツリー ノードには、ベクトルの最大 32 要素、または最大 32 の他のツリー ノードが含まれます。最大 32 個の要素を持つベクトルを 1 つのノードで表すことができます。最大 32 * 32 = 1024 個の要素を持つベクトルは、1 つの間接参照で表すことができます。ツリーのルートから最終要素ノードまでの 2 ホップは、最大 2 15の要素を持つベクトルの場合、2 20のベクトルの場合は 3 ホップ、2 25の要素を持つベクトルの場合は 4 ホップ、最大 2 30のベクトルの場合は 5 ホップで十分です。要素。そのため、適切なサイズのすべてのベクトルについて、要素の選択には最大 5 つのプリミティブ配列の選択が含まれます。これは、要素アクセスが「事実上一定の時間」であると書いたときに意味したことです。
したがって、基本的に、各ノードにいくつの子を持たせるかについて設計上の決定を下す必要がありました。彼らが説明したように、32 は妥当に思えましたが、制限が厳しすぎると感じた場合は、いつでも独自のクラスを作成できます。
なぜ 32 だったのかについての詳細は、こちらの論文を参照してください。導入部では、ほぼ一定の時間であるという上記と同じ声明を出していますが、この論文では、Scala よりも Clojure を扱っているようです。
于 2012-09-17T16:45:42.560 に答える
8
ジェームズ・ブラックの答えは正しいです。32 アイテムを選択するもう 1 つの理由は、最近の多くのプロセッサのキャッシュ ライン サイズが 64 バイトであるため、2 つのラインがそれぞれ 4 バイトの 32 個の int、または 32 ビット マシンまたは 64 ビット JVM のヒープ サイズが最大ポインタ圧縮のため 32GB。
于 2012-09-17T16:58:09.300 に答える
4
ジェームズの答えに少し追加するだけです。
アルゴリズム分析の観点から
は、2つの関数の成長は対数であるため、同じようにスケーリングされます。
ただし、実際のアプリケーションで
は、ホップ数は、たとえば2進数よりもはるかに少ないホップ数であるため、Nの値がかなり大きい場合でも、ホップ数を一定時間に近づけることができます。
メモリブロックのサイズが大きいため、正確に32を選択したと確信していますが、主な理由は、小さいサイズに比べてホップ数が少ないことです。
また、InfoQでこのプレゼンテーションを視聴することをお勧めします。ここでは、Daniel Spiewakが約30分からベクターについて説明しています：http：//www.infoq.com/presentations/Functional-Data-Structures-in-Scala
于 2012-09-17T17:06:12.917 に答える
4
これは、更新のための「実質的に一定の時間」です。分岐係数が大きいため、テラバイト規模のベクトルであっても、5 レベルを超える必要はありません。チャネル 9 で、Rich がClojureのそれとその他の側面について話しているビデオを次に示し ます。 -Clojure
于 2012-09-17T16:47:59.267 に答える