私はインタビューで上記の質問をされましたが、インタビュアーは答えを確信しています。しかし、よくわかりません。誰でもここで私を助けることができますか?
3 に答える
2
もちろん。明らかな強引な方法は、入力数値のすべての可能な値に対して 1 つのエントリを持つ大きなルックアップ テーブルです。数が非常に大きい場合、これはあまり実用的ではありませんが、それでも可能であることを証明するには十分です。
編集：これは完全にナンセンスであるという考えが提起されており、基本的にどのアルゴリズムについても同じことが言えます。
ある程度までは、それは公正な声明ですが、制限が非常に厳しいため、ほとんどのアルゴリズムではまったく意味がありません.
私の最初のポイント (少なくとも私が覚えている限り) は、人口のカウントは、通常は O(1) であると想定される足し算や引き算などの他の多くの操作とほぼ同等であるということでした。
ハードウェア レベルでは、シングル サイクル命令の回路は、POPCNTおそらくシングル サイクル命令の回路よりも簡単ですADD。1 つの例として、実際のデータ ワードのサイズに関係なく、4 ビットのチャンクでテーブル ルックアップを並列に使用し、それらの断片からの結果を加算することができます。かなりありそうにない最悪のケースの仮定 (たとえば、それらのテーブルごとに個別のストレージ) を使用しても、これは最新の CPU で実装するのは簡単です。上記1。
これは、他の多くのアルゴリズムとは明らかに対照的です。分かりやすい例として、並べ替えを考えてみましょう。ほとんどの人が想像できる最も些細な並べ替え (2 つの項目、それぞれ 8 ビット) でさえ、一定の複雑さを得るために既に 64 キロバイトのルックアップ テーブルにいます。単純な並べ替え (たとえば、100 項目) を実行できるようになるずっと前に、宇宙に存在する原子よりもはるかに多くのデータ項目を含むルックアップ テーブルが必要です。
反対の方向から見ると、ある時点で本質的に何も O(1)でなくなっていることは確かです。可能な最も単純な操作を考えてみましょう。N ビット CPU の場合、ビット単位ORは通常OR、並列の N ゲートのセットとして実装されます。追加とは異なり、1 つのビットと別のビットの間に相互作用がないため、実際のサイズの CPU では、これを 1 つの命令で簡単に実行できます。
ORそれにもかかわらず、各オペランドが 100 ペタビットであるビット単位を指定すると、一定の複雑さでジョブを実行する実用的な方法に近づくことさえありません。並列ゲートの通常の方法を使用するORと、(とりわけ) 300 ペタビット相当の入力および出力ラインが得られます。これは、最大の CPU のピン数でさえも完全に小さくなります。
妥当なハードウェアでは、OR100 ペタビットのオペランドをビット単位で処理するには、しばらく時間がかかります (かなりのハード ドライブ容量は言うまでもありません)。これを 200 ペタビット オペランドに増やすと、時間は (約) 2 倍になる可能性があります。つまり、その観点からすると、これは O(N) 演算です。AND明らかに、足し算、引き算、bit-wise 、bit-wiseなどの他の「自明な」操作でも同じことが言えますXOR。
それにもかかわらず、非常に巨大なオペランドを扱うつもりであるという非常に具体的な指示がない限り、通常、これらのすべてを一定の複雑さの操作として扱います。これらの観点から見ると、POPCNT 命令は、固定時間内での実行の難しさという点で、ビット単位のAND/ OR/XORと加算/減算のほぼ中間に位置します。
1.他の操作を行っaddた後に実際に が含まれている場合よりも単純になる可能性があることに疑問を抱くかもしれません。addもしそうなら、称賛 - それは素晴らしい質問です。
答えは、はるかに小さな加算器しか必要ないからです。たとえば、64 ビット CPU には 1 つの半加算器と 63 の全加算器が必要です。単純な実装では、加算をビットごとに実行します。つまり、一方のオペランドのビット 0 を他方のビット 0 に加算します。これにより、出力ビットとキャリー ビットが生成されます。そのキャリー ビットは、次のビット ペアの加算への入力になります。それをある程度並列化するためのいくつかのトリックがありますが、獣の性質は (いわば) ビットシリアルです。
POPCNT 命令では、個々のテーブル ルックアップを実行した後に加算がありますが、結果は入力ワードのサイズに制限されます。同じサイズの入力 (64 ビット) を考えると、最終結果は 64 よりも大きくなりません。つまり、必要なのは 64 ビット加算器ではなく 6 ビット加算器だけです。
上で概説したように、加算は基本的にビットシリアルであるため、これは、POPCNT命令の最後の加算が基本的に通常の加算よりもはるかに高速であることを意味します。具体的には、オペランド サイズに対して対数ですが、単純な加算はオペランド サイズに対してほぼ線形です。
于 2012-04-27T02:32:40.327 に答える
1
于 2012-04-27T11:24:20.637 に答える
1
ビット サイズが固定されている場合 (たとえば、32 ビットまたは 64 ビット マシンの自然なワード サイズ)、ビットを反復処理して、O(1) 時間で直接カウントできます (ただし、より高速な方法は確かにあります)。 . 任意精度の数値 (BigInt など) の場合、答えはノーでなければなりません。
于 2012-04-27T02:51:10.580 に答える