时间戳

首页 > 解决方案 > 计算在同一位置至少包含一个常见字符的不同字符串对

c++ - 计算在同一位置至少包含一个常见字符的不同字符串对

问题描述

有没有一种更有效的方法来计算数组中在同一位置至少有一个公共字符的不同字符串对。字符串的长度总是相同的 3。例如，

我尝试编写一个函数来检查它们是否匹配，然后使用 for 循环对其进行计数，但它似乎效率不高，尤其是当数组很大时。

bool match(std::string a, std::string b) {
    for (int i = 0; i < 3; i++) {
        if (a.at(i) == b.at(i)) {
            return true;
        }
    }
    return false;
}

int main() {
    const int count = 100000;
    std::string strings[count] = {...};

    long long int matches = 0;
    for (int i = 0; i < count; i++) {
        for (int j = i + 1; j < count; j++) {
            if (match(strings[i], strings[j])) {
                matches++;
            }
        }
    }
}

那么，有没有更有效的方法来实现这一目标？

标签： c++arrays

解决方案

下面是列表（假设字符串有 3 个字符）：

  1. 实际上是您的编译器可能尚未完成的唯一一个：传递std::stringby const&，这样您每次调用函数时都不需要复制它们
bool match(const std::string& a, const std::string& b){...}
  1. 避免代码中无用的分支（可以通过一些分支预测算法进行优化）：
 // from 
if (match(strings[i], strings[j])) {
   matches++;
}
 // to
matches = matches + match(strings[i], strings[j];
  1. 循环展开（编译器已经可以完成）：
bool match(std::string a, std::string b) {
    return a.at(0) == b.at(0) || a.at(1) == b.at(1) || a.at(2) == b.at(2);
}
  1. 您还可以尝试并行化这些条件（取决于架构，编译器已经可以完成）|，因此所有条件都可以由 ALU 并行完成，而不是 using|必须逐步执行（短路评估）：
bool match(std::string a, std::string b) {
    return a.at(0) == b.at(0) | a.at(1) == b.at(1) | a.at(2) == b.at(2);
}

  1. 使用最高优化编译（可以增加编译时间），使用-O3

  2. 使用前增量而不是后增量（后增量将生成第二个变量以在每次使用时返回，前增量没有）：

for (int i = 0; i < count; ++i) {
    for (int j = i + 1; j < count; ++j) {
    }
}

  1. 通过这一行std::string strings[count] = {...};，我假设您正在使用 initializarer 列表，因此如果您使用计算实际上可以在编译时执行std::string_view，因此在运行时没有要执行的编译（这仅适用于在编译时知道字符串的情况）

  2. 减少缓存未命中，但这 100% 取决于架构

  3. 内联函数（这样你的程序就不必每次调用都跳转match）：

// from:
bool match(const std::string& a, const std::string& b){...}
//to:
inline bool match(const std::string& a, const std::string& b){...}
  1. 使用operator[]而不是.at()因为它不会进行任何类型的边界检查
bool match(std::string a, std::string b) {
    return a[0] == b[0] | a[1] == b[1] | a[2] == b[2];
}

推荐阅读