Я пытаюсь найти наиболее часто встречающееся письмо в списке слов. Я борюсь с алгоритмом, потому что мне нужно подсчитывать частоту букв в слове только один раз, пропуская дубликаты, поэтому мне нужна помощь в поиске способа подсчета частоты букв во всем списке только с одним вхождением на слово, игнорируя Второе явление.
Например, если у меня есть:
words=["tree","bone","indigo","developer"]
Частота будет:
letters={a:0, b:1, c:0, d:2, e:3, f:0, g:1, h:0, i:1, j:0, k:0, l:1, m:0, n:2, o:3, p:1, q:0, r:2, s:0, t:1, u:0, v:1, w:0, x:0, y:0, z:0}
Как видно из словаря букв: "е" равно 3, а не 5, потому что, если "е" повторяется более одного раза в одном и том же слове, его следует игнорировать.
Это алгоритм, который я придумал, он реализован на Python:
for word in words:
count=0;
for letter in word:
if(letter.isalpha()):
if((letters[letter.lower()] > 0 && count == 0) ||
(letters[letter.lower()] == 0 && count == 0)):
letters[letter.lower()]+=1
count=1
elif(letters[letter.lower()]==0 && count==1):
letters[letter.lower()]+=1
Но это все еще требует работы, и я не могу думать ни о чем другом, я был бы рад любому, кто поможет мне подумать о рабочем решении.
Вариант ответа @Primusa без обновления:
from collections import Counter
words = ["tree", "bone", "indigo", "developer"]
counts = Counter(c for word in words for c in set(word.lower()) if c.isalpha())
Выход
Counter({'e': 3, 'o': 3, 'r': 2, 'd': 2, 'n': 2, 'p': 1, 'i': 1, 'b': 1, 'v': 1, 'g': 1, 'l': 1, 't': 1})
В основном конвертируйте каждое слово в набор, а затем итерируйте по каждому набору.
Создайте объект счетчика, а затем обновите его наборами для каждого слова:
from collections import Counter
wordlist = ["tree","bone","indigo","developer"]
c = Counter()
for word in wordlist:
c.update(set(word.lower()))
print(c)
Выход:
Counter({'e': 3, 'o': 3, 'r': 2, 'n': 2, 'd': 2, 't': 1, 'b': 1, 'i': 1, 'g': 1, 'v': 1, 'p': 1, 'l': 1})
Обратите внимание, что, хотя письма, которые не присутствовали в wordlist нет в в Counter, это хорошо, потому что Counter ведет себя как defaultdict(int), поэтому доступ к значению нет автоматически возвращает значение по умолчанию 0.
Один без счетчика
words=["tree","bone","indigo","developer"]
d={}
for word in words: # iterate over words
for i in set(word): # to remove the duplication of characters within word
d[i]=d.get(i,0)+1
Выход
{'b': 1,
'd': 2,
'e': 3,
'g': 1,
'i': 1,
'l': 1,
'n': 2,
'o': 3,
'p': 1,
'r': 2,
't': 1,
'v': 1}
Сравнение скорости представленных решений:
def f1(words):
c = Counter()
for word in words:
c.update(set(word.lower()))
return c
def f2(words):
return Counter(
c
for word in words
for c in set(word.lower()))
def f3(words):
d = {}
for word in words:
for i in set(word.lower()):
d[i] = d.get(i, 0) + 1
return d
Моя функция синхронизации (используя разные размеры для списка слов):
word_list = [
'tree', 'bone', 'indigo', 'developer', 'python',
'language', 'timeit', 'xerox', 'printer', 'offset',
]
for exp in range(5):
words = word_list * 10**exp
result_list = []
for i in range(1, 4):
t = timeit.timeit(
'f(words)',
'from __main__ import words, f{} as f'.format(i),
number=100)
result_list.append((i, t))
print('{:10,d} words | {}'.format(
len(words),
' | '.join(
'f{} {:8.4f} sec'.format(i, t) for i, t in result_list)))
Результаты, достижения:
10 words | f1 0.0028 sec | f2 0.0012 sec | f3 0.0011 sec
100 words | f1 0.0245 sec | f2 0.0082 sec | f3 0.0113 sec
1,000 words | f1 0.2450 sec | f2 0.0812 sec | f3 0.1134 sec
10,000 words | f1 2.4601 sec | f2 0.8113 sec | f3 1.1335 sec
100,000 words | f1 24.4195 sec | f2 8.1828 sec | f3 11.2167 sec
Counter с пониманием списка (здесь как f2()) кажется самым быстрым. Использование counter.update() кажется медленной точкой (здесь как f1()).
Попробуйте использовать словарь понимания:
import string
print({k:max(i.count(k) for i in words) for k in string.ascii_lowercase})
Слишком поздно для вечеринки, но здесь вы идете:
freq = {k: sum(k in word for word in words) for k in set(''.join(words))}
который возвращает:
{'i': 1, 'v': 1, 'p': 1, 'b': 1, 'e': 3, 'g': 1, 't': 1, 'n': 2, 'd': 2, 'o': 3, 'l': 1, 'r': 2}
from collections import Counter
import string
words=["tree","bone","indigo","developer"]
y=Counter(string.ascii_lowercase)
new_dict=dict(y)
for k in new_dict:
new_dict[k]=0
trial = 0
while len(words) > trial:
for let in set(words[trial]):
if let in new_dict:
new_dict[str(let)]=new_dict[str(let)]+1
trial = trial +1
print(new_dict)
Другие решения хороши, но они конкретно не включают буквы с нулевой частотой. Здесь подход, который делает, но примерно в 2-3 раза медленнее, чем другие.
import string
counts = {c: len([w for w in words if c in w.lower()]) for c in string.ascii_lowercase}
который производит dict как это:
{'a': 4, 'b': 2, 'c': 2, 'd': 4, 'e': 7, 'f': 2, 'g': 2, 'h': 3, 'i': 7, 'j': 0, 'k': 0, 'l': 4, 'm': 5, 'n': 4, 'o': 4, 'p': 1, 'q': 0, 'r': 5, 's': 3, 't': 3, 'u': 2, 'v': 0, 'w': 3, 'x': 0, 'y': 2, 'z': 1}
Вот мое обновление времени Ральфа:
10 words | f1 0.0004 sec | f2 0.0004 sec | f3 0.0003 sec | f4 0.0010 sec
100 words | f1 0.0019 sec | f2 0.0014 sec | f3 0.0013 sec | f4 0.0034 sec
1,000 words | f1 0.0180 sec | f2 0.0118 sec | f3 0.0140 sec | f4 0.0298 sec
10,000 words | f1 0.1960 sec | f2 0.1278 sec | f3 0.1542 sec | f4 0.2648 sec
100,000 words | f1 2.0859 sec | f2 1.3971 sec | f3 1.6815 sec | f4 3.5196 sec
на основе следующего кода и списка слов из https://github.com/dwyl/english-words/
import string
import timeit
import random
from collections import Counter
def f1(words):
c = Counter()
for word in words:
c.update(set(word.lower()))
return c
def f2(words):
return Counter(
c
for word in words
for c in set(word.lower()))
def f3(words):
d = {}
for word in words:
for i in set(word.lower()):
d[i] = d.get(i, 0) + 1
return d
def f4(words):
d = {c: len([w for w in words if c in w.lower()]) for c in string.ascii_lowercase}
return d
with open('words.txt') as word_file:
valid_words = set(word_file.read().split())
for exp in range(5):
result_list = []
for i in range(1, 5):
t = timeit.timeit(
'f(words)',
'from __main__ import f{} as f, valid_words, exp; import random; words = random.sample(valid_words, 10**exp)'.format(i),
number=100)
result_list.append((i, t))
print('{:10,d} words | {}'.format(
len(words),
' | '.join(
'f{} {:8.4f} sec'.format(i, t) for i, t in result_list)))
print(f4(random.sample(valid_words, 10000)))
print(f4(random.sample(valid_words, 1000)))
print(f4(random.sample(valid_words, 100)))
print(f4(random.sample(valid_words, 10)))