配列とハッシュマップのアクセス時間はどのように一定ですか？

Question

具体的には、ハッシュ（または配列インデックス）を指定すると、マシンは一定の時間内にどのようにデータに到達しますか？

他のすべてのメモリ位置（または何でも）を渡しても、渡された場所の数に等しい時間がかかるように見えます（線形時間）。同僚は私にこれを説明するために勇敢に試みましたが、私たちが回線に乗ったときにはあきらめなければなりませんでした。

例：私たちは「foo」がであるバケット知っているので、位置20にある「foo」というの

my_array = new array(:size => 20) 
my_array[20] = "foo" 
my_array[20] # "foo" 

アクセスが一定でどのように我々は魔法のように途中で他のすべてを渡すことなく、そのバケットに手に入れました。 ？あるブロックに20番の家に入るためには、もう1つのブロックを通過する必要があります。

Answer 1

どのように我々は魔法のように途中で他のすべて を通過せず、その バケットになりましたか？

「We」はバケツにまったく行きません。 RAMの物理的な仕組みは、すべてのバケツが聞いているチャンネルにバケツの番号をブロードキャストするようなもので、番号が付いたものがその内容を送信します。

CPUで計算が行われます。理論的には、CPUはすべてのメモリ位置と同じ「距離」です（実際にはパフォーマンスに大きな影響を与える可能性があるキャッシングのためではありません）。

ぎりぎりの詳細を知りたい場合は、"What every programmer should know about memory"と読んでください。

Answer 2

次に、メモリの構成とアクセス方法を見てください。 address decoderの仕組みを見なければならないかもしれません。問題は、あなたがメモリに必要なものに到達するために他のすべてのアドレスを渡す必要はないということです。あなたは実際にあなたが望むものにジャンプすることができます。さもなければ私たちのコンピュータは本当に遅くなるでしょう。

Answer 3

メモリを順番にアクセスする必要があるチューリングマシンとは異なり、コンピュータはランダムアクセスメモリまたはRAMを使用します。つまり、アレイの開始位置を知り、アレイの20番目の要素にアクセスすることを知っている場合、見るべき記憶の部分を知る。

これは、通りを運転するようなことではなく、共有メールボックス内のアパートメントの正しいメールスロットを選ぶようなものです。

Answer 4

2事が重要です。

1. my_arrayでは、メモリ、コンピュータでこの配列を取得するためにジャンプしなければならない場所に関する情報を持っています。
2. index * sizeof型は配列の先頭からオフセットされます。

1 + 2 = Oデータを見つけることができる場合（1）

Answer 5

ビッグOは、そのように働きません。これは、特定のアルゴリズムと機能によってどれくらいのリソースが使用されているかの尺度になっています。これは、使用されるメモリの量を測定することを意味するものではなく、そのメモリを移動することについて話している場合、それはまだ一定の時間です。配列の2番目のスロットを見つける必要がある場合は、ポインタにオフセットを追加することです。さて、もし私が木構造を持っていて、特定のノードを探したいのであれば、O（log n）について話しています。なぜなら、最初のパスでそれを見つけられないからです。 平均でノードを見つけるのにO（log n）が必要です。

Answer 6

これについてはC/C++の用語で説明します。 C＃の配列について知っておくべき追加のものがありますが、それは実際には意味がありません。 16ビット整数値の配列を指定して

：

short[5] myArray = {1,2,3,4,5}; 

本当に起こった何は、コンピュータがメモリ内のスペースのブロックを割り当てられていることです。このメモリブロックはその配列のために予約されています。完全な配列（この場合は16 * 5 == 80ビット== 10バイト）を保持するのに必要なサイズであり、連続しています。これらの事実はあきらかです。いつでもあなたの環境に該当するものもあれば、まったく存在しないものもあれば、アクセスのバイアローションのためにプログラムがクラッシュする危険性があります。

このように、変数myArrayが本当に舞台裏であるのは、メモリブロックの先頭のメモリアドレスです。これは、便利なことに、最初の要素の開始点でもあります。各追加要素は、最初の要素の直後に順に並べられます。 myArrayに割り当てられたメモリブロックは、次のようになります。

00000000000000010000000000000010000000000000001100000000000001000000000000000101 
^    ^   ^   ^   ^
myArray([0]) myArray[1]  myArray[2]  myArray[3]  myArray[4] 

メモリ・アドレスにアクセスし、バイトの一定の数を読み出すために一定時間操作と見なされます。上記の図のように、3つのことを知っていれば、それぞれのメモリアドレスを取得できます。メモリブロックの開始、各要素のメモリサイズ、および必要な要素のインデックスが含まれます。あなたのコードでmyArray[3]を求めるときに、その要求は次式でメモリ・アドレスに変換されます。

myArray[3] == &myArray+sizeof(short)*3; 

このように、一定時間の計算では、4番目の要素のメモリアドレスを発見しました（インデックス3）、別の一定時間の操作（または少なくともそのように考えられますが、実際のアクセスの複雑さはハードウェアの詳細であり、あなたが気にしてはいけないほど速い）、そのメモリを読み取ることができます。これは、あなたが今まで疑問に思ったことがある場合、ほとんどのC言語でのコレクションのインデックスがゼロから始まる理由は何ですか？配列の最初の要素は配列自体の位置から開始し、オフセットはありません（sizeof（anything）* 0 == 0）

C＃では、2つの顕著な違いがあります。 C＃配列には、CLRに使用されるいくつかのヘッダー情報があります。ヘッダは、メモリブロックに最初に来る、およびアドレス式は一つだけ重要な違いがありますので、このヘッダのサイズは、定数と知られている：C＃は、あなたが直接その管理にメモリを参照することはできません

myArray[3] == &myArray+headerSize+sizeof(short)*3; 

ランタイム自体は、このようなものを使用してヒープからのメモリアクセスを実行します。

2番目のことは、C/C++のほとんどの味にも共通していることですが、特定の型は常に「参照」によって扱われるということです。 newキーワードを使用して作成する必要があるものは、参照型です（文字列のようなオブジェクトもありますが、参照型ですが、コード内の値型のように見えます）。参照型は、インスタンス化されるとメモリに置かれ、移動せず、通常はコピーされません。そのオブジェクトを表す任意の変数は、その場で、メモリ内のオブジェクトのメモリアドレスだけである。配列は参照型です（myArrayは単なるメモリアドレスだったことを忘れないでください）。参照型の配列はこれらのメモリアドレスの配列なので、配列内の要素であるオブジェクトへのアクセスは2段階の処理です。まず、配列内の要素のメモリアドレスを計算して取得します。それは実際のオブジェクトの位置（または少なくともその変更可能なデータ;複合型がメモリ内でどのように構造化されているかは、他のすべてのものがワームであるか）である別のメモリアドレスです。これは依然として一定時間動作です。 1つではなく2つのステップだけです。