Подсчет повторяющихся символов в строке в Python
Я хочу подсчитать количество повторений каждого символа в строке. Есть ли какой-либо конкретный способ сделать это, кроме сравнения каждого символа строки с A-Z и увеличение счетчика?
Обновить (ссылаясь на Anthony answer): Что бы вы ни предлагали до сих пор, мне приходится писать 26 раз. Есть ли более простой способ?
15 ответов
Моя первая идея состояла в том, чтобы сделать это:
Однако это не очень хорошая идея! Это будет проверять строку 26 раз, поэтому вы будете потенциально выполнять в 26 раз больше работы, чем некоторые другие ответы. Вы действительно должны это сделать:
Это гарантирует, что вы проходите только строку один раз, а не 26 раз.
Кроме того, ответ Алекс отличный — я не был знаком с модулем коллекций. Я буду использовать это в будущем. Его ответ более краток, чем мой, и технически превосходный. Я рекомендую использовать его код поверх моего.
A collections.defaultdict похож на dict (подклассы он на самом деле), но когда запись запрашивается и не найдена, вместо того, чтобы сообщать, что она ее не имеет, она делает ее и вставляет ее, вызывая предоставленную 0-аргумент вызываемый. Наиболее популярными являются defaultdict(int) , для подсчета (или, что то же самое, для создания структуры данных мультисети AKA) и defaultdict(list) , что навсегда избавляет от необходимости использовать .setdefault(akey, []).append(avalue) и подобные неудобные идиомы.
Итак, как только вы это сделали, d представляет собой контейнер, подобный dict, сопоставляющий каждый символ с количеством раз, которое он появляется, и вы можете испускать его любым способом, как вам нравится. Например, наиболее популярный символ сначала:
Python 2.7+ включает collections.Counter класс:
Это самый короткий, самый практичный, с которым я могу работать без импорта дополнительных модулей.
print d [‘a’] выводит 2
И это также быстро.
Великолепное сравнение производительности
Поскольку у меня не было «ничего лучше» (понимаете: у меня было много работы), я решил устроить небольшой конкурс производительности. Я собрал наиболее разумные или интересные ответы и сделал несколько простых timeit в CPython 3.5.1. Я протестировал их только с одной строкой, что типично для моего случая:
Помните, что результаты могут отличаться для разных входных данных, будь то разная длина строки или разное количество отдельных символов, или разное среднее число вхождений на символ.
Не изобретай велосипед
Python сделал это простым для нас. Класс collections.Counter делает именно то, что мы хотим, и многое другое. Его использование на сегодняшний день является самым простым из всех методов, упомянутых здесь.
взято из @oefe, хорошая находка
Counter проходит лишнюю милю, поэтому так долго.
¿Словарь, comprende?
Давайте попробуем вместо этого использовать простой dict . Во-первых, давайте сделаем это декларативно, используя диктовку.
Я придумал это сам.
Это будет проходить через s от начала до конца, и для каждого символа он будет подсчитывать количество его вхождений в s . Поскольку s содержит повторяющиеся символы, вышеуказанный метод ищет s несколько раз один и тот же символ. Результат, естественно, всегда одинаков. Итак, давайте посчитаем количество вхождений только один раз для каждого персонажа.
Я сам придумал это, как и @IrshadBhat
Лучше. Но мы все еще должны искать в строке, чтобы посчитать вхождения. Один поиск для каждого отдельного символа. Это означает, что мы собираемся прочитать строку более одного раза. Мы можем сделать лучше, чем это! Но для этого мы должны сойти с нашей декларативистской высокой лошади и погрузиться в императивное мышление.
Исключительный код
Ака Должен поймать их всех!
вдохновленный @anthony
Ну, это стоило попробовать. Если вы покопаетесь в исходном коде Python (я не могу с уверенностью сказать, потому что я никогда этого не делал), вы, вероятно, обнаружите, что когда вы делаете, except ExceptionType , Python должен проверить, действительно ли возникшее исключение — ExceptionType или какой-либо другой. тип. Просто, черт возьми, давайте посмотрим, сколько времени это займет, если мы пропустим эту проверку и перехватим все исключения.
сделано @anthony
Это экономит некоторое время, поэтому можно испытать соблазн использовать это как своего рода оптимизацию.
Не делай этого! Или на самом деле. Сделай это сейчас:
ИНТЕРЛЮД 1
Ты видишь? Ловит KeyboardInterrupt , кроме прочего. На самом деле, он улавливает все исключения. Включая те, о которых вы, возможно, даже не слышали, например, SystemExit .
ИНТЕРЛЮД 2
Теперь вернемся к подсчету букв, цифр и других символов.
Игра в догонялки
Исключения — не тот путь. Вы должны изо всех сил пытаться догнать их, и когда вы, наконец, сделаете это, они просто подбрасывают вас, а затем поднимают брови, как будто это ваша вина. К счастью, отважные ребята проложили наш путь, чтобы мы могли покончить с исключениями, по крайней мере, в этом небольшом упражнении.
У класса dict есть хороший метод get который позволяет нам извлекать элемент из словаря, как и d[k] . За исключением случаев, когда ключ k отсутствует в словаре, он может вернуть значение по умолчанию. Давайте использовать этот метод вместо возни с исключениями.
заслуга @Usman
Почти так же быстро, как и основанное на множестве понимание. На больших входах этот, вероятно, будет еще быстрее.
Используйте правильный инструмент для работы
По крайней мере, для слегка осведомленного программиста на Python первое, что приходит на ум, это, вероятно, defaultdict . Он делает почти то же самое, что и версия выше, за исключением того, что вместо значения вы присваиваете ему фабрику значений. Это может вызвать некоторые издержки, потому что значение должно быть «построено» для каждого отсутствующего ключа в отдельности. Давайте посмотрим, как это работает.
надеюсь, @AlexMartelli меня не распят за from collections import defaultdict
Не так уж плохо. Я бы сказал, что увеличение времени выполнения — это небольшой налог, чтобы заплатить за улучшенную читаемость. Однако мы также отдаем предпочтение производительности и не будем останавливаться на достигнутом. Давайте возьмем его дальше и наполним словарь нулями. Тогда нам не нужно будет каждый раз проверять, есть ли уже товар.
снимаю шляпу перед @sqram
Это хорошо. Более чем в три раза быстрее, чем Counter , но все же достаточно просто. Лично это мой фаворит, если вы не хотите добавлять новых персонажей позже. И даже если вы это сделаете, вы все равно можете это сделать. Это просто менее удобно, чем было бы в других версиях:
Практичность превосходит чистоту (кроме случаев, когда она не очень практична)
Теперь немного другой вид счетчика. @IdanK придумал что-то интересное. Вместо того, чтобы использовать хеш-таблицу (он же словарь или dict ), мы можем избежать риска хеш-коллизий и связанных с этим накладных расходов на их разрешение. Мы также можем избежать издержек хэширования ключа и дополнительного незанятого табличного пространства. Мы можем использовать list . Значения ASCII символов будут индексами, а их значения будут значениями. Как указал @IdanK, этот список дает нам постоянный доступ к количеству символов. Все, что нам нужно сделать, — это преобразовать каждый символ из str в int используя встроенную функцию ord . Это даст нам индекс в списке, который мы затем будем использовать для увеличения количества символов. Итак, мы делаем следующее: мы инициализируем список нулями, делаем работу, а затем преобразуем список в dict . Этот dict будет содержать только те символы, которые имеют ненулевое число, чтобы сделать его совместимым с другими версиями.
В качестве примечания, этот метод используется в алгоритме сортировки по линейному времени, известному как сортировка по счету или сортировка по счету. Это очень эффективно, но диапазон сортируемых значений ограничен, так как у каждого значения должен быть свой счетчик. Чтобы отсортировать последовательность из 32-битных целых, потребуется 4,3 миллиарда счетчиков.
Ой! Не круто! Давайте попробуем и посмотрим, сколько времени понадобится, когда мы не будем строить словарь.
Все еще плохо. Но подождите, что [0 for _ in range(256)] ? Разве мы не можем написать это проще? Как насчет [0] * 256 ? Это чище. Но будет ли это лучше?
Радикально. Теперь давайте вернем словарь.
Почти в шесть раз медленнее. Почему это так долго? Потому что, когда мы enumerate(counts) считаем enumerate(counts) , мы должны проверять каждый из 256 счетчиков и видеть, равен ли он нулю. Но мы уже знаем, какие отсчеты равны нулю, а какие нет.
Это, вероятно, не станет намного лучше, по крайней мере, не для такого маленького вклада. Кроме того, его можно использовать только для 8-битных символов EASCII. О блять!
И победитель.
Ага. Даже если вам нужно каждый раз проверять, находится ли c в d , для этого ввода это самый быстрый способ. Никакое предварительное заполнение d не сделает это быстрее (опять же, для этого ввода). Это намного более многословно, чем Counter или defaultdict , но также более эффективно.
Это все люди
Это небольшое упражнение преподает нам урок: при оптимизации всегда измеряйте производительность, в идеале с учетом ожидаемых результатов. Оптимизировать для общего случая. Не думайте, что что-то на самом деле более эффективно только потому, что его асимптотическая сложность ниже. И последнее, но не менее важное: имейте в виду удобочитаемость. Попробуйте найти компромисс между «дружественным к компьютеру» и «дружественным для человека».
ОБНОВИТЬ
@MartijnPieters сообщил мне о функции collections._count_elements доступной в Python 3.
Эта функция реализована в C, поэтому она должна быть быстрее, но эта дополнительная производительность имеет свою цену. Цена несовместима с Python 2 и, возможно, даже будущими версиями, так как мы используем приватную функцию.
[. ] имя с префиксом подчеркивания (например, _spam ) следует рассматривать как непубличную часть API (будь то функция, метод или элемент данных). Это следует рассматривать как деталь реализации и может быть изменено без предварительного уведомления.
Тем не менее, если вы все еще хотите сохранить эти 620 наносекунд на итерацию:
ОБНОВЛЕНИЕ 2: Большие строки
Я подумал, что было бы хорошей идеей перезапустить тесты для некоторого большего ввода, поскольку строка из 16 символов является настолько маленьким вводом, что все возможные решения были достаточно быстрыми (1000 итераций менее чем за 30 миллисекунд).
Я решил использовать полное собрание сочинений Шекспира в качестве тестового корпуса, что оказалось довольно сложной задачей (поскольку его размер превышал 5 МБ ). Я просто использовал первые 100 000 символов, и мне пришлось ограничить количество итераций от 1 000 000 до 1 000.
collections.Counter был очень медленным на небольшом входе, но таблицы превратились
Наивное Θ (n 2 ) понимание словаря времени просто не работает
Smart Θ (n) время словарь понимает отлично работает
Исключения — неуклюжие и медленные
Пропуск проверки типа исключения не экономит время (поскольку исключение выдается только несколько раз)
dict.get выглядит красиво, но работает медленно
collections.defaultdict тоже не очень быстрый
dict.fromkeys требует чтения (очень длинной) строки дважды
Использование list вместо dict ни приятно, ни быстро
Пропуск окончательного преобразования в dict не помогает
Неважно, как вы строите list , так как это не узкое место
Если преобразовать list в dict в «умный» способ, это еще медленнее (так как вы перебрать строки дважды)
Вариант dict.__contains__ может быть быстрым для маленьких строк, но не для больших
collections._count_elements примерно так же быстро, как collections.Counter (который использует _count_elements внутри)
Окончательный вердикт: пользуйся collections.Counter Если не можешь или не хочешь 🙂
Приложение: NumPy
Пакет numpy предоставляет метод numpy.unique который выполняет (почти) именно то, что мы хотим.
Способ работы этого метода сильно отличается от всех вышеперечисленных методов:
Сначала сортируется копия входных данных с использованием быстрой сортировки, которая в худшем случае является O (n 2 ) -временной операцией, хотя в среднем O (n log n), а в лучшем случае O (n).
Затем он создает массив «mask», содержащий True в индексах, где начинается прогон с теми же значениями, а именно. в индексах, где значение отличается от предыдущего значения. Повторные значения производят False в маске. Пример: [5,5,5,8,9,9] создает маску [True, False, False, True, True, False] .
Затем эта маска используется для извлечения уникальных значений из отсортированного ввода — unique_chars в приведенном ниже коде. В нашем примере они будут [5, 8, 9] .
Массив индексов значений True создается из маски, а длина ввода добавляется в конец массива. Для приведенного выше примера этот массив будет [0, 3, 4, 6] .
Для этого массива вычисляются различия между его элементами, например. [3, 1, 2] . Это соответствующие количества элементов в отсортированном массиве — char_counts в приведенном ниже коде.
Наконец, мы создаем словарь, unique_chars и char_counts : <5: 3, 8: 1, 9: 2>.
Для тестового ввода (первые 100 000 знаков полного собрания сочинений Шекспира) этот метод работает лучше, чем любой другой, протестированный здесь. Но обратите внимание, что на другом входе этот подход может дать худшую производительность, чем другие методы. Предварительная сортировка ввода и количество повторений на элемент являются важными факторами, влияющими на производительность.
Если вы думаете об использовании этого метода, потому что он в два раза быстрее, чем collections.Counter , подумайте об этом:
collections.Counter Счетчик имеет линейную сложность по времени. numpy.unique в лучшем случае линейный, в худшем — квадратичный.
Ускорение не так уж и существенно — вы экономите
3,5 миллисекунды за итерацию на входе длиной 100000.
Использование numpy.unique очевидно, требует numpy .
Учитывая это, кажется разумным использовать Counter если вам не нужно быть очень быстрым. И в этом случае вам лучше знать, что вы делаете, иначе вы в конечном итоге будете медленнее с numpy чем без него.
Найти все повторяющиеся символы из строки на Python
Одна строка дается. Наша задача — найти те символы, частота которых в данной строке больше одного.
В качестве примера мы видим, что строка «Hello World. Давайте изучать Python », поэтому алгоритм найдет те буквы, которые встречаются несколько раз. В этом случае вывод будет выглядеть так:
Для реализации этой проблемы мы используем Python Collections. Из коллекции мы можем получить метод Counter(). Метод Counter() используется для подсчета объектов хеш-таблицы. В этом случае он отделяет символы от текста и делает каждый символ ключом словаря, а количество символов — это значение этих ключей.
Поиск с регулярными выражениями
Регулярные выражения (RE, regexp) нужны, чтобы находить в строках подстроки не по точному вхождению, а описываемые правилами-шаблонами.
! Если нужно найти точное вхождение, лучше использовать стандартные методы строк, а не re .
Специальные символы, с помощью которых мы будем задавать правила поиска строк:
- . один любой символ
- ? 0 или 1 вхождение предыдущего символа
- * предыдущий символ повторяется ≥ 0 раз (0, 1, 2, 3 и т. д.)
- + предыдущий символ повторяется ≥ 1 раз (1, 2, 3 и т. д.)
- ^ начало строки
- $ конец строки
- [abc] «или»: любой из символов а, b, c
- [а-я] любая буква русского алфавита от «а» до «я» Внутри квадратных скобок большинство специальных символ не действуют: . обозначает точку, ? — вопросительный знак. Вне квадратных скобок, чтобы получить точку или, например, плюс, специальные символы надо экранировать с помощью \ ( \. обозначает точку, \+ обозначает плюс).
- [^abc] — отрицание: любой символ, кроме a, b, c.
- \d любая цифра, аналогично [0-9]
- \D — любой символ, кроме цифр (отрицание \d или [^0-9] )
- \w — буквы, цифры, _ (то же, что [a-zA-Z0-9_] ), \W — всё кроме букв, цифр, _ .
- \s — любой пробелоподбный символ ( [ \t\n\r\f\v] ), \S — любой непробелоподбный символ
Регулярные выражения в питоне
Мы будем использовать модуль re :
Функция re.search(pattern, string) возвращает первое вхождение подстроки, которая подходит под регулярное выражение. Обратите внимание на порядок аргументов: первый — это регулярное выражение, второй — исходная строка, в которой мы ищем.
re.search возвращает объект match (или None , если ничего не нашлось), из которого затем можно извлечь результат методом group() :
Ещё одна полезная функция re.findall(pattern, string) находит все вхождения подходящих строк:
“Сырые” (raw) строки
Для регулярных выражений в питоне лучше использовать синтаксис для «сырых» (raw) строк. Если добавить r в начале строки ( r’\d’ ), то питон будет обрабатывать эту строку не как обычную, а как сырую.
Зачем это нужно? В регулярных выражениях для экранирования специальных символов используется \ – например, \. обозначает точку, \+ – плюс, и т. д. Но когда питон читает обычные, не “сырые” строки (ещё до того, как мы с этой строкой что-то сделали), он тоже использует \ для экранирования символов, но по-другому (например \n – это перенос строки, \t – табуляция, а \\ – буквально символ \ ). Из-за различий в правилах экранирования может возникнуть путаница – например, при попытке обработать строку \d как обычную, не как “сырую”, питон выдаст синтаксическую ошибку, потому что он не знает, во что преобразовать \d . Другой пример – в синтаксисе регулярных выражений \b обозначает границу слова, а в синтаксисе питоновских строк – символ backspace (поэтому, когда мы не используем “сырые” строки, \b преобразуется в backspace).
Предположим, нам нужно написать регулярное выражение, соответствующее подстроке \section . В синтаксисе регулярных выражений оно будет выглядеть так: \\section (символ \ должен быть экранирован). Но, если мы не используем “сырые” строки, то нам придётся записать его как \\\\section – оба символа \ должны быть экранированы ещё раз, чтобы питон их правильно прочитал. Довольно неудобно.
В “сырых” строках питон ничего не экранирует, а \ читается как обычный символ и экранируется только в регулярном выражении, поэтому путаницы не возникает. Например, на print(‘Hello!\nHi!’) мы получим
a на print(r’Hello!\nHi!’) –
Соответственно, “сырая” строка с регулярным выражением для поиска подстроки \section будет выглядеть просто как r’\\section’ .
Кроме того, “сырые” строки удобно использовать для хранения пути к файлам в Windows (например r’C:\Documents\myfile.txt’ ), так как там тоже используется \ .
Ограничение: “сырые” строки не могут содержать нечётное количество символов \ в конце.
Найдем все числа в строке:
Домашнее задание
Задача для всех вариантов – написать 10 функций, использующих регулярные выражения. Решение не должно содержать в себе ничего, кроме функций. Для того, чтобы удалять из текста подстроки, соответствующие определённому паттерну, воспользуйтесь функцией re.sub .
Скелет программы для работы вот такой:
Первые 4 функции принимают на вход строку и возвращают True или False в зависимости от того, является ли строка:
- номером мобильного телефона формата +7 (9ХХ) ХХХ-ХХ-ХХ
- датой формата DD.MM.YYYY в диапазоне от 1000 до 1999 года включительно (например, 127.0.0.1 )
Следующие 4 функции принимают на вход название текстового файла с русским текстом в кодировке UTF-8 и:
- удаляет из текста все лишние пробелы и переносы строк – заменяет все последовательности из двух и более пробелов или переносов строк на один пробел или перенос строки соотвественно, и возвращает очищенный текст.
- возвращает частотный словарь (воспользуйтесь классом collections.Counter ) всех словоформ имён собственных, кроме тех, которые стоят в начале предложения
- удаляет из текста нумерацию глав и возвращает очищенный текст. Нумерацией глав считать любые арабские или римские числа, находящиеся на отдельной строке (после числа может стоять одна точка).
- возвращает список заимствований в тексте. Заимствованиями считать любые последовательности букв латинского алфавита (кроме римских цифр), разделённых пробелами и переносами строк (примеры из тестового текста: ‘Hollywood Canteen’ , ‘Black and Tan Fantasy’ ). Подсказка: пользуйтесь функциями, написанными ранее.
Последние 2 функции принимают на вход название HTML-файла в кодировке UTF-8 и:
Как определить повторяющиеся символы в строке с помощью Python?
Я новичок в python, и я хочу написать программу, которая определяет, состоит ли строка из повторяющихся символов. Список строк, которые я хочу проверить:
-
Str1 = «AAAA» Str2 = «AGAGAG» Str3 = «AAA»
Псевдокод, который я придумал:
Я не уверен, что это применимый способ решения проблемы. Любые идеи, как подойти к этой проблеме?
Вы можете использовать библиотеку Counter для подсчета наиболее часто встречающихся символов.
Чтобы получить единственный повторяющийся (общий) характер:
Предполагая, что вы имеете в виду, что вся строка повторяется, этот ответ имеет хорошее решение:
Чтобы найти шаблон в Python, вам понадобится использовать «Регулярные выражения». Регулярное выражение обычно записывается как:
За этим обычно следует if-statement, чтобы определить, удалось ли выполнить поиск.
например, вот как вы можете найти шаблон «AAAA» в строке:
Это возвращает «найденный» AAAA «
Сделайте то же самое для двух других строк, и он будет работать одинаково. Регулярные выражения могут делать намного больше, чем просто так, работать с ними и видеть, что еще они могут сделать.