Licząc miliony cyfr, zwracaj wszystkie powtarzające się 3 cyfry

ezzzCash 11/30/2017. 10 answers, 9.911 views
python algorithm data-structures number-theory

Kilka miesięcy temu miałem wywiad z towarzystwem funduszy hedgingowych w Nowym Jorku i niestety nie dostałem oferty stażu w charakterze inżyniera danych / oprogramowania. (Poprosili również, aby rozwiązanie było w języku Python).

Naprawdę spieprzyłem pierwszy problem z rozmową ...

Pytanie: Biorąc pod uwagę ciąg miliona liczb (np. Pi), napisz funkcję / program, który zwraca wszystkie powtarzające się 3 cyfry i liczbę powtórzeń większą niż 1

Na przykład: jeśli ciąg znaków brzmiał: 123412345123456 to funkcja / program powróciłaby:

123 - 3 times
234 - 3 times
345 - 2 times 

Nie dali mi rozwiązania po tym, jak nie udało mi się przeprowadzić wywiadu, ale powiedzieli mi, że złożoność czasowa rozwiązania była stała 1000, ponieważ wszystkie możliwe wyniki są pomiędzy:

000 -> 999

Teraz, kiedy o tym myślę, nie wydaje mi się, że możliwe jest stworzenie algorytmu o stałym czasie. Czy to jest?

5 Comments
56 mypetlion 11/30/2017
Jeśli uważają, że rozwiązanie jest stałe o wartości 1000, to powoduje, że myślę, że zbudowaliby wszystkie liczby trzycyfrowe, a następnie wyszukał je regex. Bardzo często ludzie myślą, że operacje, których faktycznie nie napisali / zobaczą, są "darmowe". Jestem prawie pewny, że będzie to liniowa długość struny.
45 Paŭlo Ebermann 11/30/2017
Nitpickingly, jeśli wielkość wejściowa jest stała, każdy algorytm jest stałym czasem ;-)
25 ilkkachu 11/30/2017
stała 1000 what ? (dodatki? słonie?)
26 Kevin 12/01/2017
Cóż, jeśli długość łańcucha jest stała (1M), a długość podłańcucha / liczby jest stała (3), to technicznie każde rozwiązanie jest stałym czasem ...
6 TechMedicNYC 12/01/2017
They did not give me the solution after I failed the interview, but they did tell me that the time complexity for the solution was constant of 1000 since all the possible outcomes are between: 000 --> 999 To był prawdopodobnie prawdziwy test. Aby sprawdzić, czy możesz udowodnić im, dlaczego nie jest to możliwe i pokazać im prawidłową złożoność minimalnego czasu.

10 Answers


paxdiablo 12/06/2017.

Zrobiło się lekko, prawdopodobnie don't chcesz pracować dla funduszu hedgingowego, gdzie kwanty nie rozumieją podstawowych algorytmów :-)

Nie no możliwości przetworzenia struktury danych o dowolnych rozmiarach w O(1) jeśli, tak jak w tym przypadku, musisz co najmniej raz odwiedzić każdy element. best co możesz liczyć, to O(n) w tym przypadku, gdzie n jest długością łańcucha.

Chociaż na marginesie, nominalny algorytm O(n) will miał wartość O(1) dla ustalonego rozmiaru wejściowego, więc technicznie mogły być tutaj poprawne. Jednak nie jest to zwykle sposób, w jaki ludzie wykorzystują analizę złożoności.

Wydaje mi się, że mógłbyś wywrzeć na nich wrażenie na wiele sposobów.

Po pierwsze, informując ich, że not można tego zrobić w O(1) , chyba że użyjesz "podejrzanego" rozumowania podanego powyżej.

Po drugie, pokazując swoje elitarne umiejętności, dostarczając kod Pythonic, taki jak:

inpStr = '123412345123456'

# O(1) array creation.
freq = [0] * 1000

# O(n) string processing.
for val in [int(inpStr[pos:pos+3]) for pos in range(len(inpStr) - 2)]:
    freq[val] += 1

# O(1) output of relevant array values.
print ([(num, freq[num]) for num in range(1000) if freq[num] > 1]) 

To daje wynik:

[(123, 3), (234, 3), (345, 2)] 

choć oczywiście można zmodyfikować format wyjściowy do dowolnych potrzeb.

I na koniec, mówiąc im, że prawie na pewno no problemu z rozwiązaniem O(n) , ponieważ powyższy kod zapewnia wyniki dla ciągu miliona cyfr w czasie krótszym niż pół sekundy. Wydaje się również skalować dość liniowo, ponieważ ciąg znaków o wielkości 10 000 000 znaków zajmuje 3,5 sekundy, a 100 000 000 znaków trwa 36 sekund.

A jeśli need czegoś lepszego, istnieją sposoby na paralele tego rodzaju rzeczy, które mogą znacznie przyspieszyć.

Nie w obrębie single interpretera Pythona oczywiście, ze względu na GIL, ale można podzielić ciąg na coś podobnego (nałożenie wskazane przez vv jest wymagane, aby umożliwić prawidłowe przetwarzanie obszarów granicznych):

vv
123412  vv
    123451
        5123456 

Możesz je wydzielić do oddzielnych pracowników i połączyć wyniki później.

Podział danych wejściowych i łączenie danych wyjściowych prawdopodobnie spowolni każde oszczędzanie małymi strunami (i być może nawet milionowymi ciągami znaków), ale w przypadku dużo większych zbiorów danych może to mieć znaczenie. "measure, don't guess" moją zwykłą mantrą "measure, don't guess" .


Ta mantra odnosi się także do other możliwości, takich jak omijanie Pythona i używanie innego języka, który może być szybszy.

Na przykład następujący kod C, działający na tym samym sprzęcie co wcześniejszy kod Pythona, obsługuje hundred milionów cyfr w 0,6 sekundy, mniej więcej tyle samo czasu, ile kod Pythona przetworzył milion. Innymi słowy, much szybciej:

 #include #include int main(void) {
    static char inpStr[100000000+1];
    static int freq[1000];

    // Set up test data.

    memset(inpStr, '1', sizeof(inpStr));
    inpStr[sizeof(inpStr)-1] = '\0';

    // Need at least three digits to do anything useful.

    if (strlen(inpStr) <= 2) return 0;

    // Get initial feed from first two digits, process others.

    int val = (inpStr[0] - '0') * 10 + inpStr[1] - '0';
    char *inpPtr = &(inpStr[2]);
    while (*inpPtr != '\0') {
        // Remove hundreds, add next digit as units, adjust table.

        val = (val % 100) * 10 + *inpPtr++ - '0';
        freq[val]++;
    }

    // Output (relevant part of) table.

    for (int i = 0; i < 1000; ++i)
        if (freq[i] > 1)
            printf("%3d -> %d\n", i, freq[i]);

    return 0;
} 
5 comments
14 Eric Duminil 12/01/2017
Ten "ustalony rozmiar wejściowy" naprawdę brzmi jak zły żart albo osoba przesłuchująca, albo osoba, z którą rozmawiał, nie dostała. Każdy algorytm staje się O(1) n jest stałe lub ograniczone.
4 Sebastian Redl 12/01/2017
Jeśli potrzebują czegoś lepszego, może nie powinni używać Pythona, przynajmniej dla konkretnego algorytmu.
2 ray 12/01/2017
@ezzzCash Ponieważ mogą występować nakładki w punktach, w których ciąg jest "rozbijany" podczas próby równoległego podejścia. Ponieważ szukasz grup 3-cyfrowych, -2 umożliwia sprawdzenie obu grupowań równoległych, aby not przegapić potencjalnie zgodnego dopasowania.
5 ray 12/02/2017
@ezzzCash Nie jest to brak wiedzy o programowaniu równoległym. Rozważmy ciąg długości N Jeśli podzielisz go na dwie części na pozycji N/2 , nadal musisz wziąć pod uwagę fakt, że możesz pominąć ważny 3-cyfrowy mecz na "granicy", na końcu string1 i początku string2 . Dlatego musisz sprawdzić dopasowanie pomiędzy string1[N/2-2] i string2[2] (używając indeksu bazującego na zera), itp. To jest idea.
1 Peter Cordes 12/02/2017
W przypadku dłuższych sekwencji cyfr można uzyskać optymalizację konwersji na liczbę całkowitą za pomocą przesuwanego okna, w którym można upuścić najwyższą cyfrę i dodać nową cyfrę. (Python narzut prawdopodobnie zabiłby to, więc dotyczyłoby tylko C lub innych implementacji niskiego poziomu). val -= 100 * (d[i]-'0'); zrzucić pierwszą cyfrę. val = 10*val + d[i+2]-'0' aby zgromadzić nową najmniej znaczącą cyfrę (normalny ciąg-> całkowite parsowanie). val % 100 jest prawdopodobnie niepoprawny, ale tylko wtedy, gdy 100 jest stałą czasu kompilacji, więc nie używa prawdziwego podziału HW.

rcgldr 11/30/2017.

Stały czas nie jest możliwy. Wszystkie miliony cyfr muszą być przeglądane przynajmniej raz, więc jest to złożoność czasowa O (n), gdzie n = 1 milion w tym przypadku.

W przypadku prostego rozwiązania O (n) utwórz tablicę o rozmiarze 1000, która reprezentuje liczbę wystąpień każdej możliwej 3-cyfrowej liczby. Przesuwaj o 1 cyfrę naraz, pierwszy indeks == 0, ostatni indeks == 999997 i zwiększaj tablicę [liczbę 3-cyfrową], aby utworzyć histogram (liczbę wystąpień dla każdej możliwej 3-cyfrowej liczby). Następnie wypisz zawartość tablicy za pomocą counts> 1.

5 comments
23 rcgldr 11/30/2017
@ezzzCash - tak, słownik będzie działał, ale nie jest potrzebny. Wszystkie możliwe "klucze" są znane z wyprzedzeniem, ograniczone do zakresu od 0 do 999. Różnica w narzucie to czas potrzebny do wykonania dostępu opartego na kluczach przy użyciu 3 ciągów znaków jako kluczy, w przeciwieństwie do czasu potrzebnego na przekształcenie 3 cyfrowy ciąg do indeksu, a następnie za pomocą indeksu, aby uzyskać dostęp do tablicy.
3 Yann Vernier 11/30/2017
Jeśli chcesz sztuczki numeryczne, możesz również zdecydować się na BCD i zapisać trzy cyfry w 12 bitach. I dekoduj cyfry ASCII przez maskowanie niskich 4 bitów. Ale ten wzorzec x-'0' nie jest poprawny w Pythonie, jest to C-ism (gdzie znaki są liczbami całkowitymi).
4 Aleksi Torhamo 12/01/2017
@LorenPechtel: Wyszukiwanie w języku Python jest bardzo szybkie. Przyznane, dostęp do tablicy jest jeszcze szybszy, więc gdybyśmy mieli do czynienia z liczbami całkowitymi od samego początku, mielibyście rację. Jednak w tym przypadku mamy ciągi o długości 3, które najpierw musimy przekonwertować na liczby całkowite, jeśli chcemy ich użyć z tablicami. Okazuje się, że w przeciwieństwie do tego, czego można się spodziewać, wyszukiwanie słownika jest w rzeczywistości szybsze niż całkowity dostęp do konwersji i dostępu do tablicy. Rozwiązanie macierzy jest w tym przypadku w rzeczywistości o 50% wolniejsze.
1 tobias_k 12/01/2017
Sądzę, że można argumentować, że jeśli liczba wejściowa ma always exactly 1 milion cyfr, wówczas algorytm ten is O (1), przy stałym współczynniku 1 miliona.
1 rcgldr 12/01/2017
@AleksiTorhamo - Jeśli celem jest porównanie względnych prędkości implementacji dla algorytmu, wolałbym tradycyjny język, taki jak C lub C ++, ponieważ Python jest znacznie wolniejszy i wydaje się mieć narzut ogólny unikalny dla Pythona w porównaniu do innych języków.

Daniel 12/01/2017.

Proste rozwiązanie O (n) polegałoby na zliczaniu każdej 3-cyfrowej liczby:

for nr in range(1000):
    cnt = text.count('%03d' % nr)
    if cnt > 1:
        print '%03d is found %d times' % (nr, cnt) 

Przeszukałoby to 1000 milionów cyfr 1000 razy.

Przemierzanie cyfr tylko raz:

counts = [0] * 1000
for idx in range(len(text)-2):
    counts[int(text[idx:idx+3])] += 1

for nr, cnt in enumerate(counts):
    if cnt > 1:
        print '%03d is found %d times' % (nr, cnt) 

Czas pokazuje, że powtarzanie tylko raz nad indeksem jest dwa razy szybsze niż count .

5 comments
33 Eric Duminil 11/30/2017
Czy jest czarny piątek zniżki na text.count() ?
2 John1024 11/30/2017
@EricDuminil Masz dobry punkt, ale ponieważ text.count odbywa się w szybkim języku kompilowanym (np. C), w przeciwieństwie do powolnego pętli zinterpretowanego poziomu Pythona, tak jest zniżka.
Loren Pechtel 11/30/2017
To bardzo nieefektywne zliczanie każdej liczby osobno, ale jest to stały czas, a więc wciąż O (n).
10 Cireo 12/01/2017
Proponowana opcja, która używa count jest niepoprawna, ponieważ nie zlicza nakładających się wzorów. Zwróć uwagę, że '111'.count('11') == 1 gdy spodziewamy się, że wynosi 2 .
2 Eric Duminil 12/01/2017
Również twoje "proste rozwiązanie O(n) " jest faktycznie O(10**d * n) z d liczbą wyszukiwanych cyfr oraz n całkowitą długością ciągu. Drugi to czas O(n) i O(10**d + n) .

Paddy3118 12/03/2017.

Milion jest mały na odpowiedź, którą podaję poniżej. Oczekując tylko, że musisz być w stanie uruchomić rozwiązanie w wywiadzie, bez przerwy, to następujące działa w mniej niż dwie sekundy i daje wymagany wynik:

from collections import Counter

def triple_counter(s):
    c = Counter(s[n-3: n] for n in range(3, len(s)))
    for tri, n in c.most_common():
        if n > 1:
            print('%s - %i times.' % (tri, n))
        else:
            break

if __name__ == '__main__':
    import random

    s = ''.join(random.choice('0123456789') for _ in range(1_000_000))
    triple_counter(s) 

Miejmy nadzieję, że ankieter będzie szukał standardowej biblioteki collects.Counter class.

Równoległa wersja wykonania

Napisałem na ten temat post na blogu z dodatkowymi wyjaśnieniami.

5 comments
Eric Duminil 12/01/2017
Działa dobrze i wydaje się być najszybszym, niestramnym rozwiązaniem.
2 Paddy3118 12/01/2017
@EricDuminil, nie sądzę, że powinieneś martwić się o czasy postów, kiedy większość podanych rozwiązań nie opóźni cię zbytnio. O wiele lepiej jest pokazać, że dobrze znasz standardową bibliotekę Pythona i umiesz napisać kod, który można zachować w sytuacji, w której mógłbym pomyśleć. (Chyba że ankieter stressed krytyczność czasową, po której powinieneś zapytać o rzeczywiste czasy przed oceną, co będzie dalej).
1 Eric Duminil 12/01/2017
Zgadzamy się w 100%. Chociaż nie jestem pewien, czy jakakolwiek odpowiedź jest istotna, jeśli osoba przeprowadzająca wywiad naprawdę myśli, że jest to możliwe w O(1) .
Paddy3118 12/01/2017
Zachichotałem z tego :-)
1 TemporalWolf 12/01/2017
Jeśli ankieter podkreślił, że czas jest krytyczny, to after profilowaniu, aby potwierdzić, że jest to limit, może nadszedł czas, aby napisać moduł C, aby rozwiązać ten problem. Mam skrypt, który zobaczył 84-krotne ulepszenie w stosunku do kodu Pythona po tym, jak przełączyliśmy się na używanie modułu AC.

Paul Panzer 12/01/2017.

Oto implementacja NumPy algorytmu O (n) "consensus": przechodź przez wszystkie triplety i bin w trakcie pracy. Kojarzenie następuje po napotkaniu powiedz "385", dodając jeden do bin [3, 8, 5], który jest operacją O (1). Pojemniki są ułożone w kostkę o 10x10x10 . Ponieważ binning jest w pełni wektorowy, nie ma pętli w kodzie.

def setup_data(n):
    import random
    digits = "0123456789"
    return dict(text = ''.join(random.choice(digits) for i in range(n)))

def f_np(text):
    # Get the data into NumPy
    import numpy as np
    a = np.frombuffer(bytes(text, 'utf8'), dtype=np.uint8) - ord('0')
    # Rolling triplets
    a3 = np.lib.stride_tricks.as_strided(a, (3, a.size-2), 2*a.strides)

    bins = np.zeros((10, 10, 10), dtype=int)
    # Next line performs O(n) binning
    np.add.at(bins, tuple(a3), 1)
    # Filtering is left as an exercise
    return bins.ravel()

def f_py(text):
    counts = [0] * 1000
    for idx in range(len(text)-2):
        counts[int(text[idx:idx+3])] += 1
    return counts

import numpy as np
import types
from timeit import timeit
for n in (10, 1000, 1000000):
    data = setup_data(n)
    ref = f_np(**data)
    print(f'n = {n}')
    for name, func in list(globals().items()):
        if not name.startswith('f_') or not isinstance(func, types.FunctionType):
            continue
        try:
            assert np.all(ref == func(**data))
            print("{:16s}{:16.8f} ms".format(name[2:], timeit(
                'f(**data)', globals={'f':func, 'data':data}, number=10)*100))
        except:
            print("{:16s} apparently crashed".format(name[2:])) 

Nic dziwnego, że NumPy jest nieco szybszy niż proste rozwiązanie Pythona z @ Daniela na dużych zbiorach danych. Przykładowe wyniki:

# n = 10
# np                    0.03481400 ms
# py                    0.00669330 ms
# n = 1000
# np                    0.11215360 ms
# py                    0.34836530 ms
# n = 1000000
# np                   82.46765980 ms
# py                  360.51235450 ms 
4 comments
Peter Cordes 12/02/2017
Prawdopodobnie znacznie szybciej, aby spłaszczyć ciąg znaków, zamiast mieć zagnieżdżone pojemniki, chyba że NumPy kończy implementację jako matrycy 3D z wydajnym indeksowaniem. Która wersja @ Daniela była przeciwna; ten, który uruchamia wyszukiwanie ciągów dla każdej liczby całkowitej lub tej z histogramem?
1 Paul Panzer 12/02/2017
@PeterCordes Wątpię. ndarray s, typ core numpy, to wydajne przechowywanie, manipulowanie i indeksowanie wielowymiarowych tablic liczb. Czasami możesz zgolić kilka% spłaszczając, ale w tym przypadku wykonanie 100 x [0] + 10 x [1] + x [2] ręcznie nie przyniesie Ci zbyt wiele. Użyłem tego, który @Daniel powiedział, był szybszy, możesz sam sprawdzić kod testu.
Peter Cordes 12/02/2017
Naprawdę nie znam NumPy (lub Python w ogóle, głównie robię C i dostrajanie wydajności dla x86), ale myślę, że macie jedną tablicę 3D, prawda? Myślałem z twojego angielskiego tekstu (który najwyraźniej nawet nie czytałem uważnie), że miałeś zagnieżdżone obiekty Pythona i indeksowałeś je oddzielnie. Ale tak nie jest, więc nvm mój pierwszy komentarz.
Peter Cordes 12/02/2017
Wydaje mi się, że używana wersja Pythona to praktycznie ta sama implementacja histogramu, z której korzystały jeszcze wyższe odpowiedzi głosowane, ale jeśli różne sposoby pisania w Pythonie mają wpływ na prędkość.

pho7 11/30/2017.

Chciałbym rozwiązać problem w następujący sposób:

def find_numbers(str_num):
    final_dict = {}
    buffer = {}
    for idx in range(len(str_num) - 3):
        num = int(str_num[idx:idx + 3])
        if num not in buffer:
            buffer[num] = 0
        buffer[num] += 1
        if buffer[num] > 1:
            final_dict[num] = buffer[num]
    return final_dict 

Zastosowany do przykładowego ciągu znaków, daje:

>>> find_numbers("123412345123456")
{345: 2, 234: 3, 123: 3} 

To rozwiązanie działa w O (n), ponieważ n jest długością podanego łańcucha i jest, jak sądzę, najlepszym z możliwych.

2 comments
Eric Duminil 11/30/2017
Możesz po prostu użyć Counter . Nie potrzebujesz final_dict i nie musisz go aktualizować w każdej iteracji.
pho7 11/30/2017
To prawda, nie myślałem o używaniu go.-.-

Cort Ammon 12/01/2017.

Jak wspomniano w innej odpowiedzi, nie możesz zrobić tego algorytmu w stałym czasie, ponieważ musisz spojrzeć na co najmniej n cyfr. Czas liniowy jest najszybszy, jaki możesz uzyskać.

Jednak algorytm można wykonać w przestrzeni O (1). Musisz tylko przechowywać liczby z każdej 3-cyfrowej liczby, więc potrzebujesz tablicy 1000 wpisów. Następnie możesz przesłać strumieniowo liczbę.

Domyślam się, że albo ankieter przeprowadził pomyłkę, kiedy dali ci rozwiązanie, albo źle zrozumiałeś "stały czas", kiedy powiedzieli "stała przestrzeń".

2 comments
Peter Cordes 12/02/2017
Jak zauważyli inni, podejście histogramu to O(10**d) dodatkowa przestrzeń, gdzie d to liczba cyfr dziesiętnych, których szukasz.
gnasher729 12/02/2017
Podejście słownikowe byłoby O (min (10 ^ d, n)) dla n cyfr. Na przykład, jeśli masz n = 10 ^ 9 cyfr i chcesz znaleźć rzadkie 15-cyfrowe sekwencje, które występują więcej niż jeden raz.

Abhishek Arora 11/30/2017.

Według mojego zrozumienia, nie możesz mieć rozwiązania w stałym czasie. To zajmie co najmniej jedno przejście ponad liczbę milionów cyfr (przy założeniu, że jest to ciąg znaków). Możesz wykonać trzycyfrową iterację toczenia po cyfrach o długości miliona długości i zwiększyć wartość klawisza skrótu o 1, jeśli już istnieje, lub utworzyć nowy klucz hash (zainicjalizowany przez wartość 1), jeśli już nie istnieje słownik.

Kod będzie wyglądał mniej więcej tak:

def calc_repeating_digits(number):

    hash = {}

    for i in range(len(str(number))-2):

        current_three_digits = number[i:i+3]
        if current_three_digits in hash.keys():
            hash[current_three_digits] += 1

        else:
            hash[current_three_digits] = 1

    return hash 

Możesz filtrować do kluczy o wartości pozycji większej niż 1.


Turksarama 12/01/2017.

Oto moja odpowiedź:

from timeit import timeit
from collections import Counter
import types
import random

def setup_data(n):
    digits = "0123456789"
    return dict(text = ''.join(random.choice(digits) for i in range(n)))


def f_counter(text):
    c = Counter()
    for i in range(len(text)-2):
        ss = text[i:i+3]
        c.update([ss])
    return (i for i in c.items() if i[1] > 1)

def f_dict(text):
    d = {}
    for i in range(len(text)-2):
        ss = text[i:i+3]
        if ss not in d:
            d[ss] = 0
        d[ss] += 1
    return ((i, d[i]) for i in d if d[i] > 1)

def f_array(text):
    a = [[[0 for _ in range(10)] for _ in range(10)] for _ in range(10)]
    for n in range(len(text)-2):
        i, j, k = (int(ss) for ss in text[n:n+3])
        a[i][j][k] += 1
    for i, b in enumerate(a):
        for j, c in enumerate(b):
            for k, d in enumerate(c):
                if d > 1: yield (f'{i}{j}{k}', d)


for n in (1E1, 1E3, 1E6):
    n = int(n)
    data = setup_data(n)
    print(f'n = {n}')
    results = {}
    for name, func in list(globals().items()):
        if not name.startswith('f_') or not isinstance(func, types.FunctionType):
            continue
        print("{:16s}{:16.8f} ms".format(name[2:], timeit(
            'results[name] = f(**data)', globals={'f':func, 'data':data, 'results':results, 'name':name}, number=10)*100))
    for r in results:
        print('{:10}: {}'.format(r, sorted(list(results[r]))[:5])) 

Metoda wyszukiwania tablicy jest bardzo szybka (nawet szybsza niż metoda numma @ paul-panzer!). Oczywiście, oszukuje, ponieważ nie jest technicznie zakończone po zakończeniu, ponieważ zwraca generator. Nie musi też sprawdzać każdej iteracji, jeśli wartość już istnieje, co może bardzo pomóc.

n = 10
counter               0.10595780 ms
dict                  0.01070654 ms
array                 0.00135370 ms
f_counter : []
f_dict    : []
f_array   : []
n = 1000
counter               2.89462101 ms
dict                  0.40434612 ms
array                 0.00073838 ms
f_counter : [('008', 2), ('009', 3), ('010', 2), ('016', 2), ('017', 2)]
f_dict    : [('008', 2), ('009', 3), ('010', 2), ('016', 2), ('017', 2)]
f_array   : [('008', 2), ('009', 3), ('010', 2), ('016', 2), ('017', 2)]
n = 1000000
counter            2849.00500992 ms
dict                438.44007806 ms
array                 0.00135370 ms
f_counter : [('000', 1058), ('001', 943), ('002', 1030), ('003', 982), ('004', 1042)]
f_dict    : [('000', 1058), ('001', 943), ('002', 1030), ('003', 982), ('004', 1042)]
f_array   : [('000', 1058), ('001', 943), ('002', 1030), ('003', 982), ('004', 1042)] 
3 comments
1 Eric Duminil 12/01/2017
Więc co dokładnie porównujesz? Czy nie powinieneś zwrócić list zamiast nieużywanych generatorów?
Eric Duminil 12/01/2017
Counters nie są używane w ten sposób. Użyte prawidłowo, stają się najszybszą opcją z twoim przykładem. Jeśli używasz timeit z timeit listą generatora, twoja metoda staje się wolniejsza niż Counter lub dict . Zobacz tutaj .
Eric Duminil 12/01/2017
Wreszcie, twoja f_array może być szybsza, jeśli najpierw konwertujesz każdy znak na int: ints = [int(c) for c in text] a następnie użyj i, j, k = ints[n:n+3] .

Gourav Mittal 12/05/2017.
inputStr = '123456123138276237284287434628736482376487234682734682736487263482736487236482634'

count = {}
for i in range(len(inputStr) - 2):
    subNum = int(inputStr[i:i+3])
    if subNum not in count:
        count[subNum] = 1
    else:
        count[subNum] += 1

print count 
1 comments
ezzzCash 12/05/2017
Dziękuję za odpowiedź, ale jest ona zbyt podobna do algorytmu podanego przez @abhishek arora 5-6 dni temu. Również oryginalne pytanie nie wymagało algorytmu, ale raczej inne pytanie (na które już udzielono odpowiedzi wiele razy)

HighResolutionMusic.com - Download Hi-Res Songs

1 BLACKPINK

Kiss And Make Up flac

BLACKPINK. 2018. Writer: Soke;Kny Factory;Billboard;Chelcee Grimes;Teddy Park;Marc Vincent;Dua Lipa.
2 Martin Garrix

Access flac

Martin Garrix. 2018. Writer: Martin Garrix.
3 Martin Garrix

Yottabyte flac

Martin Garrix. 2018. Writer: Martin Garrix.
4 Dyro

Latency flac

Dyro. 2018. Writer: Martin Garrix;Dyro.
5 Martin Garrix

Waiting For Tomorrow flac

Martin Garrix. 2018. Writer: Pierce Fulton;Mike Shinoda;Martijn Garritsen;Brad Delson.
6 Alan Walker

Diamond Heart flac

Alan Walker. 2018. Writer: Alan Walker;Sophia Somajo;Mood Melodies;James Njie;Thomas Troelsen;Kristoffer Haugan;Edvard Normann;Anders Froen;Gunnar Greve;Yann Bargain;Victor Verpillat;Fredrik Borch Olsen.
7 Bradley Cooper

Shallow flac

Bradley Cooper. 2018. Writer: Andrew Wyatt;Anthony Rossomando;Mark Ronson;Lady Gaga.
8 Cardi B

Taki Taki flac

Cardi B. 2018. Writer: Bava;Juan Vasquez;Vicente Saavedra;Jordan Thorpe;DJ Snake;Ozuna;Cardi B;Selena Gomez.
9 Halsey

Without Me flac

Halsey. 2018. Writer: Halsey;Delacey;Louis Bell;Amy Allen;Justin Timberlake;Timbaland;Scott Storch.
10 Sia

I'm Still Here flac

Sia. 2018. Writer: Sia.
11 Lady Gaga

I'll Never Love Again flac

Lady Gaga. 2018. Writer: Benjamin Rice;Lady Gaga.
12 Blinders

Breach (Walk Alone) flac

Blinders. 2018. Writer: Dewain Whitmore;Ilsey Juber;Blinders;Martin Garrix.
13 Dewain Whitmore

Burn Out flac

Dewain Whitmore. 2018. Writer: Dewain Whitmore;Ilsey Juber;Emilio Behr;Martijn Garritsen.
14 Bradley Cooper

Always Remember Us This Way flac

Bradley Cooper. 2018. Writer: Lady Gaga;Dave Cobb.
15 Avril Lavigne

Head Above Water flac

Avril Lavigne. 2018. Writer: Stephan Moccio;Travis Clark;Avril Lavigne.
16 Mako

Rise flac

Mako. 2018. Writer: Riot Music Team;Mako;Justin Tranter.
17 ZAYN

Fingers flac

ZAYN. 2018. Writer: Zayn Malik;Alex Oriet;David Phelan.
18 Billie Eilish

When The Party's Over flac

Billie Eilish. 2018. Writer: Billie Eilish;FINNEAS.
19 Kelsea Ballerini

This Feeling flac

Kelsea Ballerini. 2018. Writer: Andrew Taggart;Alex Pall;Emily Warren.
20 Zara Larsson

Ruin My Life flac

Zara Larsson. 2018. Writer: Delacey;Michael Pollack;Stefan Johnson;Jordan Johnson;Sermstyle;Jackson Foote.

Related questions

Hot questions

Language

Popular Tags