Сколько каждого символа встречается в данной строке

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 ++.

Использование устройства Даффа (которое на самом деле медленнее на некоторых процессорах в настоящее время):

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 дюймов. по одному на каждого персонажа.

Инициализируйте их все до 0, затем для каждого символа, который вы видите, увеличьте ячейку в таблице с этим значением ascii.

Answer 3

Вы можете использовать хеш-карту для вставки и поиска O (1), что даст вам O (n) время выполнения вместо O (n log n). Вы можете найти его в Boost, TR1 или C ++ 0x.

Answer 4

Просто используйте таблицу из 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]]++;
}