Zdobądź pierwszą literę z maksimum występowania ciągu znaków

Question

Chciałbym uzyskać pierwszą literę z maksymalną liczbą znaków.

Na przykład:

"google" -> g 
"azerty" -> a 
"bbbaaa" -> b 

Mam już kod do pracy, używając klawiszy OrdererDict() aby uniknąć automatycznych rearangement:

from collections import OrderedDict 

sentence = "google" 

d = OrderedDict() 

for letter in sentence: 
    if letter not in d.keys(): 
     d[letter] = sentence.count(letter) 

print(max(d, key=d.get)) # g 

ale szukam dla ewentualnego jednej liniowej lub bardziej elegancki rozwiązanie (jeśli to możliwe).

Uwaga: Próbowałem już używać Counter() ale to nie działa, ponieważ dict w python nie pamiętam kolejności, które zostały wstawione klucze.

np

from collections import Counter 

sentence = "bbbaaa" 

c = Counter(sentence) 
print(c.most_common()[0][0]) # have 50% chances of printing 'a' rather than 'b'. 

Bonus pytanie: Czy ktoś tłumaczy, dlaczego OrderedDict() nie są domyślne zachowanie słownika w python?

Answer 1

Dokumentacja collections.OrderedDict faktycznie ma a recipe for an OrderedCounter:

In [5]: from collections import Counter, OrderedDict 

In [6]: class OrderedCounter(Counter, OrderedDict): 
    ...:  pass 
    ...: 

In [7]: OrderedCounter("google").most_common()[0][0] 
Out[7]: 'g' 

Answer 2

Prawdopodobnie niezbyt szybko, ale jedno-liner!

>>> s = "aaabbbbc" 
>>> sorted(s, key=lambda c: (-s.count(c), s.index(c)))[0] 
'b' 

Edit

nawet krótszy, dzięki komentarzu @Ohad Eytan za:

>>> min(s, key=lambda c: (-s.count(c), s.index(c))) 
'b' 

Benchmark

Nudzisz się dzisiaj, więc na podstawie porównania (za pomocą timeit) Test @ Joohwan's most_common_char() rozwiązanie (mostcc), @ Blender's OrderedCounter rozwiązanie (odict) i moje własne rozwiązanie liniowe (onelin, przy użyciu wariantu min). Najszybszym rozwiązaniem było konsekwentnie mostcc: do ~ 10x szybciej niż onelin w przypadku długich ciągów zawierających kilka różnych znaków i do ~ 4x szybciej niż w przypadku bardzo krótkich łańcuchów. W przypadku krótkich łańcuchów lub ciągów z małymi powtórzonymi znakami, onelin bije oktyk (w przeciwnym razie jest odwrotnie). Oto szczegóły (Długość = długość ciągu, # znaki = liczba różnych znaków Unicode do losowego wyboru dla każdego znaku, mostcc = czas wykonania 10 000 razy większośćc, odict = ile dłuższego terminu w porównaniu do większościcc, onelin = o ile dłuższa linia na linii była porównywana z większością).

Length #chars mostcc odict onelin 
10  10:  0.08s 3.76x 1.61x 
10  100: 0.10s 3.57x 1.27x 
10  1000: 0.12s 3.12x 1.34x 
100  10:  0.43s 1.96x 3.29x 
100  100: 0.59s 2.16x 2.18x 
100  1000: 0.80s 1.92x 1.72x 
1000 10:  3.48s 1.56x 9.79x 
1000 100: 3.44s 1.72x 6.43x 
1000 1000: 6.55s 1.68x 3.30x 

Answer 3

Można użyć Counter() wraz z next() znaleźć pierwszą literę, która spełnia warunek:

>>> s = "google" 
>>> c = Counter(s) 
>>> next(x for x in s if c[x] == c.most_common(1)[0][1]) 
'g' 

Answer 4

Można również ustalić ty opisać w końcu pytanie o użyciu licznika poprzez problemu wynikowa lista posortowana według różnych atrybutów: po pierwsze policz, po drugie, kolejność leksykograficzna:

from collections import Counter 

sentence = "google" 

c = Counter(sentence) 
print(sorted(c.most_common(), key = lambda x: (-x[1], sentence.index(x[0])))) 

Wynik:

=> [('g', 2), ('o', 2), ('l', 1), ('e', 1)] 

Just for Fun:

golfed Wersja:

# If your sentence is s: 
print(sorted(collections.Counter(s).most_common(),key=lambda x:(-x[1],s.index(x[0])))) 

Answer 5

Zdaję sobie sprawę, że chcesz jedno-liner, ale co jeśli trzeba było powtarzać tę czynność wielokrotnie lub obsłużyć naprawdę długie zdania? Nie znam dokładnego przypadku użycia, ale może być warta twojego czasu, biorąc pod uwagę złożoność czasu i czasu algorytmu.

W rozwiązaniu, na przykład, powtarzasz zdanie wielokrotnie, niż jest to konieczne z sentence.count(), co zajmuje O(n * number of unique characters). Następnie należy powtórzyć kolejność raz jeszcze, aby znaleźć maksimum (kolejna operacja O(number of unique characters)).

W przyjętym rozwiązaniu, musimy zdefiniować nową klasę (która łamie twoje 1 wymaganie liniowe) i tworzyć nowe obiekty z wieloma kodami i funkcjami, których prawdopodobnie nie będziesz potrzebował za każdym razem, gdy chcesz wykonać Twoje zadanie.

Jeśli nie przeszkadza mając jeszcze kilka linijek kodu (ponownie, wiem, że to nie jest kwestia tego, co jest pytaniem), możemy zbudować wielokrotnego użytku, który posiada funkcję tylko do iteracji łańcucha i raz użyć stałej i minimalnej przestrzeni:

from collections import defaultdict 


def most_common_char(sentence): 
    if not sentence: 
     return '' 

    max_count = 1 
    max_char = sentence[-1] 
    char_counts = defaultdict(int) 
    char_counts[max_char] = 1 

    for i in xrange(len(sentence) - 2, -1, -1): 
     char = sentence[i] 
     char_counts[char] += 1 
     if char_counts[char] >= max_count: 
      max_count = char_counts[char] 
      max_char = char 

    return max_char 

mamy śledzić charakteru z max count jak przechodzimy struny i wypluć na koniec iteracji. Zauważ, że powtarzamy od tyłu, ponieważ chcesz, aby pierwsza, która jest pierwsza (czyli ostatnia aktualizacja, wygrała).