私は「Programming Pearls」を読んでいましたが、解決策の説明の 1 つ (列 1 の問題 9) で本当に混乱しています。
問題は、ビットマップ データを使用して整数のセットを表す場合、最初のフェーズでセットを空に初期化することでした。ただし、スペースの初期化自体にはかなりの時間がかかる場合があります。最初のアクセス時にベクトルのエントリをゼロに初期化する手法を設計して、この問題を回避する方法を示してください。
答えは次のとおりです。ベクトルデータ[0...n-1] を初期化する効果は、2 つの追加の n 要素ベクトルfromとto、および整数topに含まれるシグネチャで実現できます。要素 データ[i] が初期化されている場合、from [i] < top and to [*from*[i]] = i. したがって、fromは単純な署名であり、toとtopを組み合わせることで、メモリのランダムな内容によってfromが誤って署名されないようにすることができます。
この回答を何度か読みました。わかりません。
誰かがそれを説明できますか？
ありがとう、
このページは私を助けてくれました: http://comments.gmane.org/gmane.comp.programming.algogeeks/30667
しかし、説明できるかどうか見てみましょう。
基本的に問題は、ベクトルが十分に大きい場合、ベクトルをすべて 0 に初期化するのにかなりの時間がかかることです。では、より多くのスペースを使用して 0 への初期化を回避するにはどうすればよいでしょうか? つまり、このベクトル内のランダムなデータと、意図的に配置したデータをどのように区別できるでしょうか?
Bentley の解決策は、データ ベクトルと同じサイズの "from" (マップ) と "to" (署名 [実際には from のインデックスへの逆マップ]) ベクトルと、数値である "top" を使用することです。これまでのデータ配列の要素の数。from[i] < top以下に説明するように重要です。
ソリューションの例を使用します。データ配列を宣言し、要素数をゼロに設定します。
top = 0
data = int array of integers of size 1,000,000
(all random values since we did not initialize it)
インデックス 1 (この場合は i=1) に要素を挿入します。しかし、それがランダムな値ではないことをどうやって知るのでしょうか? 地図と署名を使用します。「from」のインデックスは、データのインデックスと同じです。
from[i] = top
to[top] = i
data[i] = 0 (I don't think it matters whether you set it to 0 or your intended value of 3)
top++ (top is now 1)
to[from[i]] == iだから、たまたまだと言うかもしれません。と述べているのでfrom[i] < top、これは不可能です。
次の 2 つのケースを調べます。
A) データ配列にまだ要素が挿入されていない (つまり、top = 0)from[i] < 0ため、有効な配列インデックスではありません。したがって、これは不可能です。
B）挿入された要素があります（つまり、トップ> 0、1であるとしましょう）from[i] < top=> from[i] = 0. ただし、1 つの要素をデータ配列に挿入したので、明示的に を設定しto[from[i]] = iました。
残りは top = 2...n に従います
HTH
次のリンクの投稿は、一定時間の初期化トリックの背後にあるアイデアを理解するのに非常に役立つことがわかりました。
リンク: http://eli.thegreenplace.net/2008/08/23/initializing-an-array-in-constant-time/
それが役に立てば幸い-