Я хочу подсчитать количество повторений каждого символа в строке. Есть ли какой-либо конкретный способ сделать это, кроме сравнения каждого символа строки с A-Z и увеличение счетчика?
Обновить (ссылаясь на Anthony answer): Что бы вы ни предлагали до сих пор, мне приходится писать 26 раз. Есть ли более простой способ?
Моя первая идея состояла в том, чтобы сделать это:
chars = "abcdefghijklmnopqrstuvwxyz"
check_string = "i am checking this string to see how many times each character appears"
for char in chars:
count = check_string.count(char)
if count > 1:
print char, count
Однако это не очень хорошая идея! Это будет проверять строку 26 раз, поэтому вы будете потенциально выполнять в 26 раз больше работы, чем некоторые другие ответы. Вы действительно должны это сделать:
count = {}
for s in check_string:
if count.has_key(s):
count[s] += 1
else:
count[s] = 1
for key in count:
if count[key] > 1:
print key, count[key]
Это гарантирует, что вы проходите только строку один раз, а не 26 раз.
Кроме того, ответ Алекс отличный - я не был знаком с модулем коллекций. Я буду использовать это в будущем. Его ответ более краток, чем мой, и технически превосходный. Я рекомендую использовать его код поверх моего.
import collections
d = collections.defaultdict(int)
for c in thestring:
d[c] += 1
A collections.defaultdict похож на dict (подклассы он на самом деле), но когда запись запрашивается и не найдена, вместо того, чтобы сообщать, что она ее не имеет, она делает ее и вставляет ее, вызывая предоставленную 0-аргумент вызываемый. Наиболее популярными являются defaultdict(int), для подсчета (или, что то же самое, для создания структуры данных мультисети AKA) и defaultdict(list), что навсегда избавляет от необходимости использовать .setdefault(akey, []).append(avalue) и подобные неудобные идиомы.
Итак, как только вы это сделали, d представляет собой контейнер, подобный dict, сопоставляющий каждый символ с количеством раз, которое он появляется, и вы можете испускать его любым способом, как вам нравится. Например, наиболее популярный символ сначала:
for c in sorted(d, key=d.get, reverse=True):
print '%s %6d' % (c, d[c])
Python 2.7+ включает collections.Counter класс:
import collections
results = collections.Counter(the_string)
print(results)
Поскольку у меня не было "ничего лучше" (понимаю: у меня было много работы), я решил сделать
небольшой конкурс производительности. Я собрал самые разумные или интересные ответы и сделал
некоторые простые timeit в CPython 3.5.1 на них. Я проверил их только с одной строкой, которая
типичный вход в моем случае:
>>> s = 'ZDXMZKMXFDKXZFKZ'
>>> len(s)
16
Помните, что результаты могут отличаться для разных входных данных, будь то разная длина строки или различное количество отдельных символов или различное среднее число вхождений на символ.
Python сделал это простым для нас. Класс collections.Counter делает именно то, что мы хотим
и многое другое. Его использование на сегодняшний день является самым простым из всех методов, упомянутых здесь.
взят из @oefe, хорошая находка
>>> timeit('Counter(s)', globals=locals())
8.208566107001388
Counter проходит лишнюю милю, поэтому так долго.
Давайте попробуем вместо этого использовать простой dict. Во-первых, давайте сделаем это декларативно, используя dict
понимание.
Я сам придумал это...
>>> timeit('{c: s.count(c) for c in s}', globals=locals())
4.551155784000002
Это будет проходить через s от начала до конца, и для каждого символа он будет считать число
его вхождений в s. Поскольку s содержит повторяющиеся символы, вышеуказанный метод выполняет поиск
s несколько раз для одного и того же персонажа. Результат, естественно, всегда одинаков. Так что давайте считать
количество вхождений только один раз для каждого символа.
Я сам придумал это, как и @IrshadBhat.
>>> timeit('{c: s.count(c) for c in set(s)}', globals=locals())
3.1484066140001232
лучше. Но мы все еще должны искать в строке, чтобы посчитать вхождения. Один поиск каждый отдельный персонаж. Это означает, что мы собираемся прочитать строку более одного раза. Мы сможем лучше чем это! Но для этого нам нужно сойти с нашей декларативистской лошади и спуститься в императив мышления.
Ака Должен поймать их всех!
вдохновленный @anthony
>>> timeit('''
... d = {}
... for c in s:
... try:
... d[c] += 1
... except KeyError:
... d[c] = 1
... ''', globals=locals())
3.7060273620008957
Ну, это стоило попробовать. Если вы покопаетесь в источнике Python (я не могу сказать с уверенностью, потому что
Я никогда не делал этого на самом деле), вы, вероятно, обнаружите, что когда вы делаете except ExceptionType,
Python должен проверить, действительно ли возникшее исключение относится к ExceptionType или другому
тип. Просто, черт возьми, давайте посмотрим, сколько времени это займет, если мы пропустим эту проверку и поймать
все исключения.
сделано @anthony
>>> timeit('''
... d = {}
... for c in s:
... try:
... d[c] += 1
... except:
... d[c] = 1
... ''', globals=locals())
3.3506563019982423
Это экономит некоторое время, поэтому можно испытать искушение использовать это как своего рода оптимизацию.
Не делай этого! Или на самом деле. Сделай это сейчас:
ИНТЕРЛЮД 1
import time
while True:
try:
time.sleep(1)
except:
print("You're trapped in your own trap!")
Видишь? Ловит KeyboardInterrupt, кроме прочего. На самом деле, он ловит все
исключения есть. Включая те, о которых вы, возможно, даже не слышали, например, SystemExit.
ИНТЕРЛЮД 2
import sys
try:
print("Goodbye. I'm going to die soon.")
sys.exit()
except:
print('BACK FROM THE DEAD!!!')
Теперь вернемся к подсчету букв, цифр и других символов.
Исключения - не тот путь. Вы должны изо всех сил пытаться догнать их, и когда вы, наконец, да, они просто подбрасывают тебя, а потом поднимают брови, как будто это твоя вина. К счастью, храбрый ребята проложили наш путь, чтобы мы могли покончить с исключениями, по крайней мере, в этом небольшом упражнении.
Класс dict имеет хороший метод - get, который позволяет нам извлечь элемент из
словарь, как и d[k]. За исключением случаев, когда ключ k отсутствует в словаре, он может вернуть
значение по умолчанию. Давайте использовать этот метод вместо того, чтобы возиться с исключениями.
кредит идет на @Usman
>>> timeit('''
... d = {}
... for c in s:
... d[c] = d.get(c, 0) + 1
... ''', globals=locals())
3.2133633289995487
Почти так же быстро, как и основанное на множестве понимание. На больших входах этот, вероятно, будет еще быстрее.
По крайней мере, для слегка осведомленного программиста на Python первое, что приходит на ум, это
вероятно defaultdict. Он делает то же самое, что и версия выше, за исключением того, что вместо
значения, вы даете ему значение фабрики. Это может вызвать некоторые накладные расходы, потому что значение имеет
быть "построенным" для каждого недостающего ключа индивидуально. Давайте посмотрим, как это работает.
надеюсь, что @AlexMartelli меня не распят за from collections import defaultdict
>>> timeit('''
... dd = defaultdict(int)
... for c in s:
... dd[c] += 1
... ''', globals=locals())
3.3430528169992613
Не так уж и плохо. Я бы сказал, что увеличение времени исполнения - это небольшой налог, чтобы платить за улучшение читаемость. Однако мы также отдаем предпочтение производительности и не будем останавливаться на достигнутом. Давай дальше и предварительно заполнить словарь нулями. Тогда нам не придется каждый раз проверять, если товар уже там.
снимаю шляпу перед @sqram
>>> timeit('''
... d = dict.fromkeys(s, 0)
... for c in s:
... d[c] += 1
... ''', globals=locals())
2.6081761489986093
Это хорошо. В три раза быстрее, чем Counter, но все же достаточно просто. Лично это
мой любимый на случай, если вы не хотите добавлять новых персонажей позже. И даже если вы делаете, вы можете
все еще делай это. Это менее удобно, чем в других версиях:
d.update({ c: 0 for c in set(other_string) - d.keys() })
Теперь немного другой вид счетчика. @IdanK придумал что-то интересное. Вместо
использования хеш-таблицы (a.k.a. словарь a.k.a. dict), мы можем избежать риска хеш-конфликтов
и последующие накладные расходы на их решение. Мы также можем избежать издержек хэширования ключа,
и дополнительное свободное место в таблице. Мы можем использовать list. Значения символов ASCII будут
индексы и их количество будут значениями. Как указал @IdanK, этот список дает нам постоянный
время доступа к количеству символов. Все, что нам нужно сделать, это преобразовать каждый символ из str в
int с использованием встроенной функции ord. Это даст нам индекс в списке, который мы будем
затем используйте для увеличения количества символов. Так что мы делаем это: мы инициализируем список
с нулями сделайте работу, а затем преобразуйте список в dict. Этот dict будет содержать только
те символы, которые имеют ненулевое значение, чтобы сделать его совместимым с другими версиями.
В качестве примечания, этот метод используется в алгоритме сортировки по линейному времени, известному как счетная сортировка или счетная сортировка. Это очень эффективно, но диапазон значений сортируется ограничено, так как каждое значение должно иметь свой собственный счетчик. Чтобы отсортировать последовательность из 32-разрядных целых чисел, Потребуется 4,3 миллиарда счетчиков.
>>> timeit('''
... counts = [0 for _ in range(256)]
... for c in s:
... counts[ord(c)] += 1
... d = {chr(i): count for i,count in enumerate(counts) if count != 0}
... ''', globals=locals())
25.438595562001865
Ой! Не круто! Давайте попробуем и посмотрим, сколько времени понадобится, когда мы не будем строить словарь.
>>> timeit('''
... counts = [0 for _ in range(256)]
... for c in s:
... counts[ord(c)] += 1
... ''', globals=locals())
10.564866792999965
Все еще плохо. Но подождите, что [0 for _ in range(256)]? Разве мы не можем написать это проще? Как насчет
[0] * 256? Это чище. Но будет ли он лучше?
>>> timeit('''
... counts = [0] * 256
... for c in s:
... counts[ord(c)] += 1
... ''', globals=locals())
3.290163638001104
Радикально. Теперь давайте вернем словарь обратно.
>>> timeit('''
... counts = [0] * 256
... for c in s:
... counts[ord(c)] += 1
... d = {chr(i): count for i,count in enumerate(counts) if count != 0}
... ''', globals=locals())
18.000623562998953
Почти в шесть раз медленнее. Почему это так долго? Потому что, когда мы enumerate(counts), мы имеем
проверить каждый из 256 отсчетов и посмотреть, равен ли он нулю. Но мы уже знаем, какие цифры
ноль, а которые нет.
>>> timeit('''
... counts = [0] * 256
... for c in s:
... counts[ord(c)] += 1
... d = {c: counts[ord(c)] for c in set(s)}
... ''', globals=locals())
5.826531438000529
Это, вероятно, не станет намного лучше, по крайней мере, для такого маленького вклада. Плюс это только можно использовать для 8-битных символов EASCII. О блять!
>>> timeit('''
... d = {}
... for c in s:
... if c in d:
... d[c] += 1
... else:
... d[c] = 1
... ''', globals=locals())
1.8509794599995075
Угу. Даже если вам нужно каждый раз проверять, находится ли c в d, для этого входа он самый быстрый
путь. Никакое предварительное заполнение d не сделает его быстрее (опять же, для этого ввода). Это намного больше
более подробный, чем Counter или defaultdict, но также более эффективный.
Это небольшое упражнение учит нас уроку: при оптимизации всегда измеряйте производительность, в идеале с вашими ожидаемыми входами. Оптимизировать для общего случая. Не думайте, что что-то на самом деле более эффективен только потому, что его асимптотическая сложность ниже. И последнее, но не менее важное удобочитаемость. Попробуйте найти компромисс между "дружественным к компьютеру" и "дружественным для человека".
@MartijnPieters сообщил мне о функции collections._count_elements
доступно в Python 3.
Help on built-in function _count_elements in module _collections:
_count_elements(...)
_count_elements(mapping, iterable) -> None
Count elements in the iterable, updating the mappping
Эта функция реализована в C, поэтому она должна быть быстрее, но эта дополнительная производительность приходит по цене. Цена несовместима с Python 2 и, возможно, даже будущими версиями, так как мы используем приватную функцию.
Из документации:
[...] имя с префиксом подчеркивания (например,
_spam) следует рассматривать как непубличную часть API (будь то функция, метод или элемент данных). Это следует считать деталями реализации и могут быть изменены без предварительного уведомления.
Тем не менее, если вы все еще хотите сохранить эти 620 наносекунд на итерацию:
>>> timeit('''
... d = {}
... _count_elements(d, s)
... ''', globals=locals())
1.229239897998923
Я подумал, что будет хорошей идеей перезапустить тесты на более крупном вводе, так как 16 символов Строка настолько мала, что все возможные решения были сравнительно быстрыми (1000 итераций менее чем за 30 миллисекунд).
Я решил использовать полное собрание сочинений Шекспира в качестве тестового корпуса, что оказалось довольно сложной задачей (так как его размер превышает 5 МБ 😅). Я просто использовал первый 100 000 символов, и мне пришлось ограничить количество итераций от 1 000 000 до 1 000.
import urllib.request
url = 'https://ocw.mit.edu/ans7870/6/6.006/s08/lecturenotes/files/t8.shakespeare.txt'
s = urllib.request.urlopen(url).read(100_000)
collections.Counter был очень медленным на небольшом входе, но таблицы перевернулись
Counter(s)
=> 7.63926783799991
Наивное Θ (n 2) словарь времени просто не работает
{c: s.count(c) for c in s}
=> 15347.603935000052s (tested on 10 iterations; adjusted for 1000)
Умный Θ (n) словарь времени работает хорошо
{c: s.count(c) for c in set(s)}
=> 8.882608592999986
Исключения неуклюжи и медленны
d = {}
for c in s:
try:
d[c] += 1
except KeyError:
d[c] = 1
=> 21.26615508399982
Пропуск проверки типа исключения не экономит время (поскольку исключение выдается только несколько раз)
d = {}
for c in s:
try:
d[c] += 1
except:
d[c] = 1
=> 21.943328911999743
dict.get выглядит хорошо, но работает медленно
d = {}
for c in s:
d[c] = d.get(c, 0) + 1
=> 28.530086210000007
collections.defaultdict тоже не очень быстрый
dd = defaultdict(int)
for c in s:
dd[c] += 1
=> 19.43012963199999
dict.fromkeys требует прочитать (очень длинную) строку дважды
d = dict.fromkeys(s, 0)
for c in s:
d[c] += 1
=> 22.70960557699999
Использование list вместо dict не слишком хорошо и не быстро
counts = [0 for _ in range(256)]
for c in s:
counts[ord(c)] += 1
d = {chr(i): count for i,count in enumerate(counts) if count != 0}
=> 26.535474792000002
Выход из окончательного преобразования в dict не помогает
counts = [0 for _ in range(256)]
for c in s:
counts[ord(c)] += 1
=> 26.27811567400005
Неважно, как вы построите list, так как это не узкое место
counts = [0] * 256
for c in s:
counts[ord(c)] += 1
=> 25.863524940000048
counts = [0] * 256
for c in s:
counts[ord(c)] += 1
d = {chr(i): count for i,count in enumerate(counts) if count != 0}
=> 26.416733378000004
Если вы конвертируете list в dict "умным" способом, он будет еще медленнее (поскольку вы выполняете итерацию по
строка дважды)
counts = [0] * 256
for c in s:
counts[ord(c)] += 1
d = {c: counts[ord(c)] for c in set(s)}
=> 29.492915620000076
Вариант dict.__contains__ может быть быстрым для маленьких строк, но не так много для больших
d = {}
for c in s:
if c in d:
d[c] += 1
else:
d[c] = 1
=> 23.773295123000025
collections._count_elements примерно так же быстро, как collections.Counter (который использует
_count_elements изнутри)
d = {}
_count_elements(d, s)
=> 7.5814381919999505
collections.Counter, если вы не можете или не хотите :)Пакет 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}.
import numpy as np
def count_chars(s):
# The following statement needs to be changed for different input types.
# Our input 's' is actually of type 'bytes', so we use 'np.frombuffer'.
# For inputs of type 'str', change 'np.frombuffer' to 'np.fromstring'
# or transform the input into a 'bytes' instance.
arr = np.frombuffer(s, dtype=np.uint8)
unique_chars, char_counts = np.unique(arr, return_counts=True)
return dict(zip(unique_chars, char_counts))
Для тестового ввода (первые 100 000 символов из полного сочинения Шекспира) этот метод работает лучше, чем любой другой тестированный здесь. Но обратите внимание, что на с другой стороны, этот подход может дать худшую производительность, чем другие методы. Предварительная сортировка ввода и количество повторений на элемент являются важными факторами, влияющими на производительность.
count_chars(s)
=> 2.960809530000006
Если вы думаете об использовании этого метода, потому что он в два раза быстрее, чем
collections.Counter, учтите это:
collections.Counter имеет линейную сложность по времени. numpy.unique в лучшем случае линейный, квадратичный
в худшем случае.
Ускорение не так уж существенно - вы экономите ~ 3,5 миллисекунды за итерацию на входе длиной 100 000.
Использование numpy.unique очевидно требует numpy.
Учитывая это, кажется разумным использовать Counter, если вам не нужно быть очень быстрым. И в
в этом случае вам лучше знать, что вы делаете, иначе вы будете медленнее работать с numpy, чем
без этого.
Это самый короткий, самый практичный, с которым я могу работать без импорта дополнительных модулей.
text = "hello cruel world. This is a sample text"
d = dict.fromkeys(text, 0)
for c in text: d[c] += 1
print d ['a'] выводит 2
И это также быстро.
Вы хотите использовать dict.
#!/usr/bin/env python
input = "this is a string"
d = {}
for c in input:
try:
d[c] += 1
except:
d[c] = 1
for k in d.keys():
print "%s: %d" % (k, d[k])
Если кто-то ищет самый простой способ без модуля collections. Я думаю, это будет полезно:
>>> s = "asldaksldkalskdla"
>>> {i:s.count(i) for i in set(s)}
{'a': 4, 'd': 3, 'k': 3, 's': 3, 'l': 4}
или
>>> [(i,s.count(i)) for i in set(s)]
[('a', 4), ('k', 3), ('s', 3), ('l', 4), ('d', 3)]
Вы можете использовать словарь:
s = "asldaksldkalskdla"
dict = {}
for letter in s:
if letter not in dict.keys():
dict[letter] = 1
else:
dict[letter] += 1
print dict
Я могу подсчитать количество дней, когда я знаю Python на моих двух руках, поэтому простите меня, если я отвечу на что-то глупое:)
Вместо использования dict я подумал, почему не использовать список? Я не уверен, как списки и словари реализованы на Python, поэтому это нужно измерить, чтобы узнать, что быстрее.
Если бы это был С++, я бы просто использовал обычный c-array/vector для постоянного доступа времени (это определенно было бы быстрее), но я не знаю, какой соответствующий тип данных находится в Python (если есть...)
count = [0 for i in range(26)]
for c in ''.join(s.lower().split()): # get rid of whitespaces and capital letters
count[ord(c) - 97] += 1 # ord('a') == 97
Также можно сделать размер списка ord ('z'), а затем избавиться от вычитания 97 всюду, но если вы оптимизируете, почему бы не полностью:)
EDIT: Один комментатор предположил, что соединение/раскол не стоит возможного выигрыша в использовании списка, поэтому я подумал, почему бы не избавиться от него:
count = [0 for i in range(26)]
for c in s:
if c.isalpha(): count[ord(c.lower()) - 97] += 1
dict = {}
for i in set(str):
b = str.count(i, 0, len(str))
dict[i] = b
print dict
Если моя строка:
str = "this is string!"
Над кодом будет напечатан:
{'!': 1, ' ': 2, 'g': 1, 'i': 3, 'h': 1, 'n': 1, 's': 3, 'r': 1, 't': 2}
это покажет букву символов с числом встречаемости
str = 'aabcdefghijklmnopqrstuvwxyz'
mydict = {}
for char in str:
mydict[char]=mydict.get(char,0)+1
print mydict
Вот решение..
my_list=[]
history=""
history_count=0
my_str="happppyyyy"
for letter in my_str:
if letter in history:
my_list.remove((history,history_count))
history=letter
history_count+=1
else:
history_count=0
history_count+=1
history=letter
my_list.append((history,history_count))
print my_list
Если это проблема просто подсчета количества повторений данного символа в данной строке, попробуйте что-то вроде этого.
word = "babulibobablingo" letter = 'b' if letter in word: print(word.count(letter))
Ниже код работал у меня, не ища каких-либо других библиотек Python.
def count_repeated_letter(string1):
list1=[]
for letter in string1:
if string1.count(letter)>=2:
if letter not in list1:
list1.append(letter)
for item in list1:
if item!= " ":
print(item,string1.count(item))
count_repeated_letter('letter has 1 e and 2 e and 1 t and two t')
Выход:
e 4
t 5
a 4
1 2
n 3
d 3
Для подсчета символа в строке вы должны использовать YOUR_VARİABLE.count('WHAT_YOU_WANT_TO_COUNT').
Если требуется суммирование, вы должны использовать функцию count().
variable = 'turkiye'
print(variable.count('u'))
выход: 1