在给定的字符串中每个字符出现的次数是多少

Question

在给定的字符串中每个字符出现的次数是多少

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 之外的任何其他结构，但我不知道哪种结构更好。感谢您的帮助！

- Dmitrii Tarasov

2

似乎你可以使用索引作为键将你的映射更改为std::vector。我把它留给你作为练习来重写它 =) - Viktor Sehr

2

你对仅使用ASCII编码的文本感到满意吗？还是想要Unicode？如果是，那么文本将采用哪种编码？ - Adam Wright

对于主要为ASCII的Unicode，混合使用std::vector和哈希方法。 - Karoly Horvath

1

@Dmitry 是整个 ASCII 码，还是只有 0-9、a-z、A-Z？我问这个是因为我在考虑矢量化的解决方案。 - Adam Wright

4个回答

5

你可以创建一个包含256个整数的数组，每个字符对应一个整数。

将它们全部初始化为0，然后每当你看到一个字符时，就增加与该字符的ASCII值相对应的表中的单元格。

- Yochai Timmer

1

你可以使用哈希表进行O(1)的插入和查找，这将使你的运行时间从O(n log n)变为O(n)。你可以在Boost、TR1或C++0x中找到一个。

- Puppy

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]]++;
}

- Hot Licks

1

应该是 memset(table,0,256*sizeof(int)) 吧？ - lccarrasco

1

更好的做法： memset(table, 0, sizeof(table)) - RocketR

5

更好的写法：int table[256] = {0};。 - gwiazdorrr

没错，就是这样。我一开始使用字节表，但觉得更好改为整数。 - Hot Licks

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kijewski · Accepted Answer

你正在正确地使用桶排序。在有限的宇宙中（例如字符），计算元素数量没有比这更快的（非并行）算法。

如果您只使用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所指出的，使用并行处理文本块可能会提高性能。但是请注意，创建线程是非常昂贵的，因此您应该测量哪些最少数量的字符可以证明线程创建时间。