给定字符串中每个字符出现多少

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

你正在使用桶排序正确地做到这一点.用于计算有限宇宙中的元素(例如字符)的快速(非并行)算法是不可能的.

如果只使用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所说,并行处理文本块可能会提高性能.但要注意创建一个线程是非常昂贵的,所以你应该测量,最低字符数是什么,这证明了线程创建时间的合理性.

Answer 2

你可以创建256个int的数组.每个角色一个.

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