3

我需要计算给定字符串中每个字符出现的次数。我需要在 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 之外的任何其他结构，但我不知道哪种结构更好。

谢谢你的帮助！

4

4 回答 4

6

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

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

使用Duff 的设备（现在在某些 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 所说，并行处理文本块可能会给您带来性能提升。但是请注意，创建线程非常昂贵，因此您应该测量最少的字符数量是多少，这证明线程创建时间是合理的。

于 2011-07-31T19:46:19.753 回答
5

您可以创建一个包含 256 个整数的数组。每个字符一个。

将它们全部初始化为 0，然后对于您看到的每个字符，使用该 ascii 值增加表格中的单元格。

于 2011-07-31T19:47:58.070 回答
1

只需使用 256 个条目的表并按字符值索引该表。

int table[256];
// Wrong, if int table: memset(table, 0, 256);
memset(table, 0, sizeof(table));  // Right
for (int i = 0; i < text_length; i++) {
    table[text[i]]++;
}
于 2011-07-31T19:49:07.303 回答
1

您可以使用哈希映射进行 O(1) 插入和查找，这将为您提供 O(n) 运行时间而不是 O(n log n)。您可以在 Boost、TR1 或 C++0x 中找到一个。

于 2011-07-31T19:49:50.313 回答