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

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

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

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

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

Часть первая - Подсчет частот букв Следует отметить две проблемы, предполагая, что здесь используется язык C или C++:

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

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

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

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

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

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

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

Использование слова test в качестве примера (при условии, что 4 сегмента и только символы нижнего регистра:

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

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