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

Question

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

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

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

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

Answer 1

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

Answer 2

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

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

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

Answer 3

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

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

Вторая часть - местонахождение Реже письмо

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

Answer 4

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

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

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

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

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

1. генерируют 4 ведра (AG, HM, NT, UZ)
2. разделить тест слово:
   • AG: е,
   • HM:
   • NT: TST
   • UZ:
3. рекурсию к другим ковшей - (AG имеет один символ - это должно быть по меньшей мере таким образом мы можем остановить
4. Если бы это было не так (Что касается слова «семенников»), мы можем увидеть HM и UZ пусты, поэтому нам нужно было бы только проверить NT (который будет содержать tsts).
   • Мы создаем 4 ведра (N-O, P-Q, R-S и T).
   • Разделить буквы
   • т.д.

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