5

我有兴趣计算三角形序列1，它是对的序列，(i, j): (0, 0), (1, 0), (1, 1), (2, 0), (2, 1) ... 它遍历所有对(i, j)，限制为i >= j. 具有 i > j 限制的相同序列也很有趣。

(n, n)除其他外，这些序列表示从 n 元素集（对于最多2的序列）中选择 2 个（可能相同）元素的所有方式，或矩阵3的下三角元素的索引。在 OEIS 中，单独的值序列i是A003056，而j单独的是A002262。该序列经常出现在组合算法中，它们的性能可能很关键。

在序列中生成下一个值的一种简单但复杂的方法是：

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

然而，在计算序列的初始元素时，在检查条件时会出现许多错误预测(i == j)——通常每次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

这里有两种不使用任何昂贵计算的无分支方法。第一个使用比较和逻辑与：

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

第二个使用比较和乘法：

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，可能其他方法会更可取。您只计算一次序列，然后反复从内存中读取它。

于 2016-07-27T13:44:55.883 回答
1

在 Python 中，我们可以将其表示为：

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

但事实证明，在我的机器上进行大约一百万次迭代时，以下更冗长、懒惰的评估代码大约快 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()终止都发生了错误的预测。

简单不一定也很快（即考虑所有不必要的零加法和紧凑形式的乘以一。）

那么哪个更重要，快速生成序列还是避免错误预测？

于 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 回答