5

私は三角形シーケンス1を計算することに興味があります。これは、という制限で(i, j): (0, 0), (1, 0), (1, 1), (2, 0), (2, 1) ... すべてのペアを反復するペアのシーケンスです。i > j という制限を伴う同じシーケンスも興味深いものです。(i, j)i >= j

これらのシーケンスは、とりわけ、n 個の要素セット ( 2 までのシーケンス) から(n, n)2個の (おそらく同一の) 要素を選択するすべての方法、または行列3の下三角要素のインデックスを表します。ialoneの値のシーケンスはOEIS ではA003056jですが、 alone はA002262です。シーケンスは、パフォーマンスが重要になる組み合わせアルゴリズムで頻繁に発生します。

シーケンス内の次の値を生成する単純だが枝分かれした方法は次のとおりです。

if (i == j) {
    j = 0;
    i++;
  } else {
    j++;
  }      
}

ただし、これは、条件をチェックするときに、シーケンスの初期要素を計算する際に多くの誤予測に悩まされます。(i == j)通常、毎回 1 つの誤予測iがインクリメントされます。シーケンスが増加するにつれて、 のiインクリメント頻度が減少するため、誤予測の数が少なくなるため、j++ブランチが支配的になり、適切に予測されます。それでも、いくつかのタイプの組み合わせ検索は、シーケンス内の小さな用語を繰り返し反復するため、分岐のないアプローチまたは予測ミスが少ない他のアプローチを探しています。

多くの用途では、シーケンスの順序はそれほど重要ではないため、上記とは異なる順序で値を生成することは、より良い解決策につながる場合に許容されます。たとえば、jカウントアップではなくカウントダウンできます: (0, 0), (1, 1), (1, 0), (2, 2), (2, 1), ....

1また、このシーケンスの正しい名前を知りたいと思っています (おそらく、この質問により適切なタイトルを付けます)。私はちょっと「三角形のシーケンス」を作りました。

2ここで、i >= jバージョンはサブマルチセット (反復可能) をi > j表し、バリアントは通常のサブセット (反復なし) を表します。

3ここでは、i >= jバージョンにはメインの対角線が含まれていますが、i > jバリアントには含まれていません。

4

3 に答える 3

5

コストのかかる計算を一切使用しない 2 つのブランチ フリー アプローチを次に示します。最初のものは、比較と論理 AND を使用します。

const bool eq = i == j;
i += eq;
j = (j + 1) & (eq - 1);

2 つ目は、比較と乗算を使用します。

const bool eq = i == j;
i += eq;
j = (j + 1) * (1 - eq);

理論的には、「乗算」バリアントは「論理」バリアントよりも遅くなるはずですが、測定値はほとんど違いを示しません。

どちらのアプローチでも、ブランチレス比較が可能なプロセッサ (x86 など) でのみブランチレス コードが生成されます。また、これらのアプローチは、条件式の結果を簡単に整数に変換できる言語を使用して実装されることを前提としています (たとえば、C/C++ では、「偽」の比較はゼロの整数に変換され、「真」の比較は " 1")。

これらのアプローチの唯一の問題はパフォーマンスです。理論的には分岐コードよりも優れたパフォーマンスを発揮する可能性がありますが、それは予測ミスが実際に頻繁に発生する場合に限られます。「三角形シーケンス」を生成する以外に他の作業がない単純なテスト ( ideoneを参照) は、悲惨な誤予測率を示しているため、両方の分岐のない方法は、分岐のある方法よりも約 3 倍遅くなります。説明は簡単です。より長いシーケンスの予測ミスはあまりないはずです。短いものに関しては、最新のプロセッサには非常に優れた分岐予測子があり、短い分岐パターンの場合に失敗することはほとんどありません。したがって、多くの誤予測はありません。分岐のあるコードはほとんどの場合、2 つの命令 (比較、インクリメント) のみを実行しますが、分岐のないコードは、アクティブな「分岐」とアクティブな「分岐」の両方に加えて、分岐のないアプローチに固有の命令をいくつか実行します。

したい場合はrepeatedly iterate over the small terms in the sequence、おそらく他のアプローチが望ましいでしょう。シーケンスを 1 回だけ計算し、メモリから繰り返し読み取ります。

于 2016-07-27T13:44:55.883 に答える
1

Python では、これを次のように表現できます。

i, j = i + (i == j), (j + 1) * (i != j)

しかし、約 100 万回の反復で、私のマシンでは、次の、より長く、怠惰な評価コードが約 20% 高速であることがわかりました。

from itertools import count, repeat

def gen_i():
    """ A003056 """
    for x in count(0):  # infinitely counts up
        yield from repeat(x, x + 1)  # replication

def gen_j():
    """ A002262 """
    for x in count(0):  # infinitely counts up
        yield from range(x + 1)  # count up to (including) x

sequence = zip(gen_i(), gen_j())

for _ in range(1000000):
    i, j = next(sequence)

上記のコードでgen_i()は、gen_j()、count()、repeat()、zip()はすべてジェネレーター (およびrange()イテレーター) であるためsequence、新しい (i, j) ペアが必要になると、オンデマンドでコードを呼び出し続けます。range()の実装とrepeat()予測ミスで終了することを想定しています。

シンプルは必ずしも高速ではありません (つまり、ゼロの不要な加算と 1 による乗算をコンパクトな形式で検討してください)。

では、シーケンスを迅速に生成することと、予測ミスを回避することのどちらがより重要なのでしょうか?

于 2016-07-31T03:26:50.893 に答える
0

i から j を導出できます。

...set val...
old_j = j;
j = (j + 1) % (i + 1);
if (i == old_j) {
    i++;
}
...loop if more...

さらに、j と現在の i から i の増分を導き出します。

...set val...
old_j = j;
j = (j + 1) % (i + 1);
i = i + (i / old_j);
...loop if more...

（現時点ではテストできません...確認してください）

于 2016-07-10T14:02:16.613 に答える