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

发布时间：2020-12-16 10:29:42 所属栏目：百科来源：网络整理

导读：我需要计算给定字符串中每个字符出现的次数.我需要在C或C上做,我可以使用任何库.问题是我不是C/C++开发人员,所以我不确定我的代码是否是最佳的.我想获得最佳性能算法,这是这个问题的主要原因. 我目前正在使用以下代码： using namespace std;...char* text;

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

谢谢你的帮助！

解决方法

你正在使用 bucket sort正确地做.没有更快(非并行)的算法来计算有限宇宙中的元素(例如字符).

如果只使用ASCII字符,则可以使用简单的数组int表[256]来避免C容器的开销.

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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!