9

私は、単純な作業のように思われることに取り組んできました。だから、プログラミングの挑戦が好きなら...読み続けてください。

[1:20]などの数値範囲を取得し、バイナリ検索アルゴリズムと同様のメカニズムを使用して値を出力できるようにしたいと考えています。したがって、最初に最小値（この場合は1）を印刷し、次に中間値（この場合は10）を印刷してから、範囲を4分の1に分割し、1/4と3/4（この場合は5）の値を印刷します。 15）次に、範囲内のすべての値が出力されるまで、8に分割します。

これのアプリケーション（ここで実際に理解する必要はありません）は、ページが最初にミッドレンジでアクセスされるときに、より効率的に動作するメモリページアクセスメカニズムのためのものです。

この問題の場合、任意の数値範囲を取得し、上記の方法で値を出力するだけで十分です。

これについて何か考えはありますか？疑似コードソリューションで十分です。私はこれへの試みを示しますが、私がこれまでに試みたすべてはそれをカットしません。ありがとう。

更新：要求に応じて、例[1:20]の目的の出力は次のようになります：1、10、5、15、3、7、12、17、2、4、6、8、11、13 16、18、9、19、20

この出力は、使用するアルゴリズムに応じて、多くの同様の方法で表示できます。ただし、最初に半分の値を表示し、次に4分の1、次に8、16分の1などを表示して、以前に表示された値を除外するという考え方です。

4

4 に答える 4

10

これがあなたの例と同様の出力を生成するいくつかの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))

例：

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

Pythonの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の必要性を回避できます。

元のソリューションをCで簡単に実装することもできます。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);
    }
}

（これは私が最初から書きたいと思っていたコードですが、頭を包むのに少し時間がかかりました。）

于 2012-08-08T18:41:19.933 に答える
0

うーん...あなたは基本的にある種の空間充填曲線を探しています。私はあなたが巧妙なビットをいじることでそれをすることができるとほぼ確信しています。一部のキャッシュを無視するステンシルアルゴリズムで使用されるMortonZ-orderまたはAhnentafelインデックスのインデックスが計算される方法を確認することをお勧めします。私は数年前にこれを調べましたが、索引付けはあなたが説明しているものと似ていて、ビットをいじることで行われました。

于 2012-08-08T18:57:47.927 に答える
0

配列としてのバイナリヒープはすでにこの構造を持っています。配列をこの形式で保存し、順番に印刷することをお勧めします。ノードの場合i、子は2i + 1、2i + 2です。

于 2012-08-08T18:51:41.067 に答える
0

1/2は簡単ですよね？

では、1/4が1/2の1/2、1/8が1/4の1/2になるように、再帰的に実行してみませんか？

于 2012-08-08T20:27:00.447 に答える