バイナリ選択プロセス

Question

私はナットを運転している簡単な作業であると思われるものに取り組んでいます。あなたがプログラミング上の挑戦を夢中にしているならば、読んでください。

数字の範囲を取りたいと思っています。 [1:20]、バイナリ・セーチ・アルゴリズムに似たメカニズムを使って値を出力します。したがって、まず最初に最も低い値（この場合は1）を入力し、次に中間値（この場合は10）を印刷し、その範囲を四半期に分割し、その値を1/4と3/4で印刷します（この場合は5および15）、範囲内のすべての値が印刷されるまで8等分します。

このアプリケーション（ここでは必ずしも理解する必要はありません）は、最初に中間範囲でページにアクセスするとより効率的に動作するメモリページアクセスメカニズムです。

この問題では、任意の数値範囲をとり、上記の方法で値を印刷すれば十分です。

これについてのご意見はありますか？擬似コードの解決策は問題ありません。私はこれに試行を示すだろうが、これまでに試したことはすべてそれをカットしていない。ありがとう。

更新：要求されたように、例[1:20]の望ましい出力は、1,10,5,15,3,7,12,17,2,4,6,8,9,10,11,12,13,14、この出力は、使用されるアルゴリズムに応じて多くの同様の方法で提示することができます。しかし、アイデアは、最初に半分の値を表示し、次に四半期を表示し、次に8番目に16番目に表示することです。ここ

Answer 1

はあなたの例のような出力を生成するいくつかのPythonコードである：

def f(low, high): 
    ranges = collections.deque([(low, high)]) 
    while ranges: 
     low, high = ranges.popleft() 
     mid = (low + high) // 2 
     yield mid 
     if low < mid: 
      ranges.append((low, mid)) 
     if mid + 1 < high: 
      ranges.append((mid + 1, high)) 

例：Pythonで慣例であるように

>>> list(f(0, 20)) 
[10, 5, 15, 2, 8, 13, 18, 1, 4, 7, 9, 12, 14, 17, 19, 0, 3, 6, 11, 16] 

low, high範囲は、終点を除外するので、結果が含まれてい0から19までの数字。

このコードでは、依然として処理が必要な部分範囲を格納するためにFIFOが使用されます。 FIFOはフルレンジで初期化されます。各反復では、次の範囲がポップされ、中間点が生成されます。次に、空でない場合、現在の範囲の下位および上位の下位範囲がFIFOに追加されます。

編集：ここC99に完全に異なる実装である：

#include <stdio.h> 

int main() 
{ 
    const unsigned n = 20; 
    for (unsigned i = 1; n >> (i - 1); ++i) { 
     unsigned last = n; // guaranteed to be different from all x values 
     unsigned count = 1; 
     for (unsigned j = 1; j < (1 << i); ++j) { 
      const unsigned x = (n * j) >> i; 
      if (last == x) { 
       ++count; 
      } else { 
       if (count == 1 && !(j & 1)) { 
        printf("%u\n", last); 
       } 
       count = 1; 
       last = x; 
      } 
     } 
     if (count == 1) 
      printf("%u\n", last); 
    } 
    return 0; 
} 

これは、整数は、すでに以前の反復で発生したかどうかを決定するためにいくつかのトリックを使用してFIFOの必要性を回避します。

あなたはFIFOの最大サイズを知っているので（これは（n + 1）/ 2のようなものですが、これをもう一度確認する必要があります）、キューに入れられた範囲を保持するためにリングバッファを使用します。

編集2：これはC99のさらに別の解決策です。ループの反復の半分だけを実行し、ビットのオペレーションと加算のみを使用し、乗算や除算は使用しないように最適化されています。また、より簡潔で、結果に0が含まれていないので、最初に意図したとおりにこれを最初にすることができます。

for (int i = 1; n >> (i - 1); ++i) { 
    const int m = 1 << i; 
    for (int x = n; x < (n << i); x += n << 1) { 
     const int k = x & (m - 1); 
     if (m - n <= k && k < n) 
      printf("%u\n", x >> i); 
    } 
} 

（これは私が最初から右に書くことを意図したコードですが、それはそれのまわりで私の頭をラップするために私にいくつかの時間がかかりました。）

Answer 2

Binary Heap配列は、すでにこのような構造を持っているよう。このフォームに配列を格納し、順番に印刷したい場合があります。ノードiの場合、子は2i + 1,2i + 2です。

Answer 3

Hmmm ...基本的には、ある種のスペース充填曲線を探しています。私はあなたが巧妙なビットtwiddlingでそれを行うことができることをほとんど確信しています。キャッシュを無視するステンシルアルゴリズムで使用されるMorton ZオーダーまたはAhnentafelインデックスについて、インデックスが計算される方法を調べることをお勧めします。数年前に私はこれを見ていました。索引付けは、あなたが記述しているものと似ていました。

Answer 4

2分の1の方が簡単ですか？

だから、なぜ再帰的に行うのではなく、1/4が1/2の1/2で、1/8が1/4の1/2ですか？