c++ - 在数组中查找 y 的 x 个连续值的最有效方法是什么？

Question

通过 callgrind 运行我的应用程序表明，这条线使其他一切相形见绌约 10,000 倍。我可能会围绕它重新设计，但这让我想知道；有更好的方法吗？

这是我目前正在做的事情:

int i = 1;
while
(
    (
        (*(buffer++) == 0xffffffff && ++i) || 
        (i = 1)
    )
    &&
    i < desiredLength + 1
    &&
    buffer < bufferEnd
);

它正在寻找 32 位无符号整数数组中 desiredLength 0xffffffff 值的第一个 block 的偏移量。

它比我想出的涉及内部循环的任何实现都要快得多。但它仍然太慢了。

Answer 1

我也会采纳 search_n 建议，因为我很确定它能正确地做到这一点。这实际上很容易，而且基本上可以通过 desired_length 的一个因子来加速。除非目标值在数组中非常密集。

想法是这样的:如果从位置 I 开始有 K 个值的连续实例，那么位置 I + K - 1 包含该值。所以你先检查一下；如果不是，那么最早可能包含 K 个连续值的位置是 I + K，因此您可以在那里重新启动算法。

另一方面，如果您找到 I + K - 1 处的值，则您向后扫描直到到达 I(在这种情况下您成功了)，或者你到达了某个不包含目标值的位置 J - 1。在后一种情况下，您知道有从 J 到 I + K - 1 的目标值，因此您现在检查 J + K - 1 .如果可行，您只需向后扫描到 I + K。如果它不起作用，则在 J + K 处重新启动算法。

大多数时候，您只会查看 vector 中的每个 K'th 位置。对于大的 K，这是一个巨大的胜利。