5

通过 callgrind 运行我的应用程序发现，这条线比其他所有东西都相形见绌，大约是 10,000 倍。我可能会围绕它重新设计，但这让我想知道；有更好的方法吗？

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

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

它正在寻找 32 位无符号整数数组中第一块所需长度 0xffffffff 值的偏移量。

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

4

6 回答 6

4

我也会接受这个search_n建议，因为我很确定它可以正确地做到这一点。这实际上很简单，基本上可以通过所需长度的一个因子来加速。除非目标值在数组中非常密集。

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

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

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

于 2012-10-18T22:29:47.603 回答
3

您标记了 c++，所以我假设您有可用的 STL 算法：

std::search_n(buffer, bufferEnd, desiredLength, 0xffffffff);
于 2012-10-18T22:10:44.260 回答
2

尝试memcmp从 C 标准库中使用。现代编译器应具有非常优化的memxxx功能实现，从而最大限度地利用现代 CPU。

于 2012-10-18T22:09:18.847 回答
2

只是一个想法，但您一次迭代一个 int 数组，对吗？想一想，如果*(buffer) != 0xffffffff然后buffer[desiredLength-1] != 0xffffffff您可以确定在两者之间进行检查是没有意义的，因此您可以继续前进而不是仅前进buffer1 desiredLength，如果大于 1，这可能会显着提高您的速度desiredLength。当然，它会使您的功能复杂化，因为：

  1. 如果两者都*(buffer)相等，buffer[desiredLength-1]那么0xffffffff你不能假设它们之间是连续的，所以你仍然需要检查它。
  2. 如果*(buffer)不等于0xffffffff但buffer[desiredLength-1]确实等于0xffffffff，那么您必须跟踪到0xffffffff序列的开头。
  3. 您必须确保在检查时不会超出缓冲区buffer[desiredLength-1]

有点复杂，但它可能会加快速度。希望这是有道理的。

于 2012-10-18T22:28:23.953 回答
1

如果我想实现这一点，我将使用memchrand来实现memcmp：

bool found = false;
std::vector<unsigned char> tmp(desiredLength*sizeof(uint32_t), 0xFF);
while( true ) {
    void* p = memchr(bufferStart, 0xFF,
        (bufferEnd-bufferStart-desiredLength) * sizeof(uint32_t));
    if( !p ) break;
    if( !memcmp(p, &tmp[0], desiredLength * sizeof(uint32_t)) ) {
        found = true;
        break;
    }
}

您也可以使用std::search_n可能比您自己的代码更优化的代码

于 2012-10-18T22:13:00.173 回答
0

对于何时std::search_n不可用：

int i = 1;
while
(
    (
        i == 1
        &&
        buffer < bufferEnd
        &&
        (
            (
                *buffer == desired
                &&
                *(buffer + desiredLength - 1) == desired
                &&
                (i = 3)
            )
            ||
            (buffer += desiredLength && (i = 1))
        )
    )
    ||
    (
        i == 2
        &&
        (
            (
                buffer > arr
                &&
                (*(--buffer) == desired)
            )
            ||
            (i = 3)
        )
    )
    ||
    (
        i >= 3
        &&
        buffer < bufferEnd
        &&
        (
            (
                *(buffer++) == desired
                &&
                (i++ || true)
            )
            ||
            (i = 1)
        )
        &&
        (
            i < 3
            ||
            i - 3 < desiredLength + 1
        )
    )
);
buffer -= i - 4;

if (buffer > bufferEnd - (i-3))
    buffer = bufferEnd;

返回相同的结果仅略慢于std:search_n：

buffer = std::search_n(buffer, bufferEnd-1, desiredLength, desired);
if (buffer == bufferEnd-1)
    buffer = bufferEnd;
于 2012-10-19T12:38:49.497 回答