C++ if语句顺序

Question

程序的一部分需要在搜索有序列表时检查两个 c 字符串是否相同（例如 {"AAA", "AAB", "ABA", "CLL", "CLZ"}）。列表可能变得非常大是可行的，因此速度上的小改进值得可读性下降。假设您仅限于使用 C++（请不要建议切换到汇编）。如何改进？

typedef char StringC[5];
void compare (const StringC stringX, const StringC stringY)
{
    // use a variable so compareResult won't have to be computed twice
    int compareResult = strcmp(stringX, stringY);
    if (compareResult < 0) // roughly 50% chance of being true, so check this first
    {
        // no match. repeat with a 'lower' value string
        compare(stringX, getLowerString() );
    }
    else if (compareResult > 0) // roughly 49% chance of being true, so check this next
    {
        // no match. repeat with a 'higher' value string
        compare(stringX, getHigherString() );
    }
    else // roughly 1% chance of being true, so check this last
    {
        // match
        reportMatch(stringY);
    }
}

您可以假设 stringX 和 stringY 的长度始终相同，您不会得到任何无效数据输入。

据我所知，编译器会编写代码，以便 CPU 将检查第一个 if 语句并在它为假时跳转，因此最好是第一个语句最有可能确实如此，因为跳跃会干扰管道。我还听说在进行比较时，[n Intel] CPU 会进行减法并查看标志的状态而不保存减法的结果。有没有办法只执行一次 strcmp，而不将结果保存到变量中，但仍然能够在前两个 if 语句中检查结果？

Answer 1

我认为使用哈希表可以大大提高比较速度。此外，如果您的程序是多线程的，您可以在英特尔线程构建块库中找到一些有用的哈希表。例如，tbb::concurrent_unordered_map 与 std::unordered_map

具有相同的 api

希望对你有所帮助

Answer 2

std::binary_search 可能有帮助：

bool cstring_less(const char (&lhs)[4], const char (&rhs)[4])
{
    return std::lexicographical_compare(std::begin(lhs), std::end(lhs),
                                        std::begin(rhs), std::end(rhs));
}

int main(int, char**)
{
    const char cstrings[][4] = {"AAA", "AAB", "ABA", "CLL", "CLZ"};
    const char lookFor[][4] = {"BBB", "ABA", "CLS"};

    for (const auto& s : lookFor)
    {
        if (std::binary_search(std::begin(cstrings), std::end(cstrings),
                               s, cstring_less))
        {
            std::cout << s << " Found.\n";
        }
    }
}

Demo

Answer 3

如果您尝试将所有字符串相互比较，您将遇到 O(N*(N-1)) 问题。正如您所说，列表可以变大，最好的办法是对它们进行排序（qsort 算法有 O(N*log(N))），然后将每个元素与列表中的下一个元素进行比较，它增加了一个新的 O(N)，总复杂度达到 O(N*log(N))。由于列表 已经排序 ，您可以遍历它（生成 O(N)），将每个元素与下一个元素进行比较。下面是一个在 C 和 C++ 中有效的示例：

for(i = 0; i < N-1; i++)  /* one comparison less than the number of elements */
    if (strcmp(array[i], array[i+1]) == 0) 
        break;
if (i < N-1) {  /* this is a premature exit from the loop, so we found a match */
    /* found a match, array[i] equals array[i+1] */
} else { /* we exhausted al comparisons and got out normally from the loop */
    /* no match found */
}

C++ if语句顺序

C++ if statement order

c++

performance

search

c-strings