c++ - 给定字符串中每个字符出现的次数

Question

我需要计算给定字符串中每个字符出现的次数。我需要在 C 或 C++ 上完成，我可以使用任何库。问题是我不是 C/C++ 开发人员，所以我不确定我的代码是否最优。我想得到最好的性能算法，这是这个问题的主要原因。

目前我正在使用以下代码:

using namespace std;
...

char* text;        // some text, may be very long
int text_length;   // I know this value, if it can help

map<char,int> table;
map<char,int>::iterator it;

for(int i = 0; c = text[i]; i++) {
    it = table.find(c);
    if (it2 == table.end()) {
        table[c] = 1;
    } else {
        table[c]++;
    }
}

我可能会使用除 std::map 之外的任何其他结构，但我不知道哪种结构更好。

感谢您的帮助!

Answer 1

您正在使用 bucket sort 做对.不可能有更快(非并行)的算法来计算有限宇宙中的元素(例如字符)。

如果只使用 ASCII 字符，可以使用简单的数组 int table[256] 来避免 C++ 容器的开销。

使用 Duff's device (现在在某些 CPU 上实际上速度较慢):

int table[256];
memset(table, 0, sizeof(table));
int iterations = (text_length+7) / 8;
switch(count % 8){
    case 0:      do {    table[ *(text++) ]++;
    case 7:              table[ *(text++) ]++;
    case 6:              table[ *(text++) ]++;
    case 5:              table[ *(text++) ]++;
    case 4:              table[ *(text++) ]++;
    case 3:              table[ *(text++) ]++;
    case 2:              table[ *(text++) ]++;
    case 1:              table[ *(text++) ]++;
                 } while(--iterations > 0);
}

更新:正如 MRAB 所说，并行处理文本 block 可能会给您带来性能提升。但请注意，创建线程的成本非常高，因此您应该衡量最少的字符数是多少，这证明线程创建时间是合理的。