самый эффективный алгоритм подсчета символов?

Question

Допустим, вы хотите посчитать число символов в некотором тексте.

Самый быстрый способ, которым я мог придумать, это использовать массив типа unsigned char charcounts[256], инициализировать его нулями, затем посмотреть на каждый символ в текстовом вводе и выполнить charcounts[c]++. затем линейный поиск charcounts[] с использованием двух переменных, чтобы отследить самый низкий (пока что) символ и его счет, заменив его новым символом / счетчиком, когда мы найдем более низкий, до тех пор, пока не достигнем конца.

Таким образом, «текст» будет t = 2, e = 1, x = 1.

Есть ли более быстрый способ сделать это?

Answer 1

Первая часть вашего алгоритма - подсчет символов - это просто генерация ключей для сортировки.

Если вы знаете, что используете только алфавитные символы [A-Za-z] *, то вы можете оптимизировать свой алгоритм, уменьшив количество используемых сегментов, но это лишь незначительная настройка.

Вторая часть - просто стабильная сортировка - есть много способов сделать это - на странице в Википедии о сортировке есть хорошее резюме. Если вас интересует только персонаж, который встречается меньше всего, то описанный вами метод («Фаза 2»), вероятно, настолько эффективен, насколько вы можете.

Единственный другой способ улучшить это, если вы можете равномерно разбить ваши буквы на фиксированное количество сегментов (скажем, 16) по всему диапазону символов, а затем повторять их в каждом сегменте. Любые корзины без символов могут быть выброшены, что экономит время на этапе сканирования / сортировки. Точно так же, если у ведра есть один символ, это делается. Вы также хотите удостовериться, что вы разбили ведро только на 16, если знаете, что в нем более одного символа.

В качестве примера используется слово test (в расчете на 4 ведра и только строчные буквы:

1. генерирует 4 ведра (A-G, H-M, N-T, U-Z)
2. разделить слово test:
   • A-G: е,
   • Н-М:
   • N-T: tst
   • U-Z:
3. перейти к другим сегментам - (A-G имеет один символ - это должно быть как минимум, чтобы мы могли остановиться
4. Если бы это было не так (что касается слова "яички"), мы можем видеть, что H-M и U-Z пусты, поэтому нам нужно будет только проверить N-T (который будет содержать tsts).
   • Мы создаем 4 ведра (N-O, P-Q, R-S и T).
   • Разделить буквы
   • и т.д.

Преимущество этого метода в том, что нам не приходилось сканировать каждую букву. Если диапазон символов одинакового размера, то оба эти метода в лучшем случае O (n), где n - длина строки (это неизбежно, так как мы всегда должны смотреть на каждый символ), хотя при построении списков символов в мой пример может сделать алгоритм так же плохо, как O (n ^ 2). Однако по мере увеличения диапазона символов, особенно для коротких строк, использование подкадров значительно повысит производительность. Для строки в юникоде вы можете использовать гибридный подход - например, разделение всех не-ascii символов на первом этапе и использование более простого метода для части ascii.

Answer 2

Первая часть - Подсчет буквенных частот Две проблемы, на которые следует обратить внимание, если предположить, что здесь используется язык C или C ++:

• Ваш код не будет обрабатывать буквы, встречающиеся> 255 раз (или 127, если char окажется подписанным). Создание "charcounts" в виде массива целых чисел, вероятно, не сильно повлияет на производительность.
• Ваш код не будет работать для юникода / международных символов

Вторая часть - поиск наименее частой буквы

• Если вы имеете дело с короткими строками («текст», «Фред»), то сканирование всех 256 записей в вашей таблице является шагом, определяющим скорость. Вам лучше следить за буквой самой низкой частоты в начальном цикле сканирования.
• Но, если вы хотите просканировать все 256 записей, вы можете выйти из цикла, как только вы достигнете значения «один» (или нуля, если так работает ваш алгоритм)

Answer 3

Вы описали две задачи здесь. Первый - подсчитать, сколько раз каждый символ ASCII встречается в потоке, а второй - попытаться найти символ самой низкой частоты.

Первый алгоритм выглядит довольно эффективным. Сверху головы я не могу придумать более быстрого пути.

Однако я менее уверен в вашем втором алгоритме. Вы не говорите явно, почему вы хотите найти символ с самой низкой частотой, или каковы входные данные, но я могу себе представить, что легко иметь более одного символа с нулевым счетчиком частоты, так как вы хотите различать между ними?

Answer 4

Это звучит как один из самых эффективных способов сделать то, что вы описываете. Я не уверен, что вы хотите сделать со второй частью, похоже, вы хотите найти персонажа с минимальным количеством вхождений в данных сортировки?