Biorąc pod uwagę ciąg miliona liczb, zwraca wszystkie powtarzające się liczby 3-cyfrowe


137

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

Prawie schrzaniłem problem z pierwszym wywiadem ...

Pytanie: Biorąc pod uwagę ciąg miliona liczb (na przykład Pi), napisz funkcję / program, który zwraca wszystkie powtarzające się liczby 3-cyfrowe i liczbę powtórzeń większą niż 1

Na przykład: jeśli ciąg to 123412345123456:, funkcja / program zwróci:

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

Nie dali mi rozwiązania po tym, jak oblałem rozmowę kwalifikacyjną, ale powiedzieli mi, że złożoność czasowa rozwiązania była stała wynosząca 1000, ponieważ wszystkie możliwe wyniki mieszczą się w przedziale:

000 -> 999

Teraz, kiedy o tym myślę, myślę, że nie można wymyślić algorytmu stałego czasu. Czy to jest?


68
Jeśli uważają, że rozwiązaniem jest stała 1000, to sprawia, że ​​myślę, że zbudowaliby wszystkie trzycyfrowe liczby, a następnie wyszukałyby je wyrażeniem regularnym. Bardzo często ludzie myślą, że operacje, których w rzeczywistości nie napisali / nie widzieli, są „bezpłatne”. Jestem prawie pewien, że byłoby to liniowe do długości struny.
mypetlion

54
Nitpickly, jeśli rozmiar wejściowy jest stały, każdy algorytm jest stały w czasie ;-)
Paŭlo Ebermann

34
stała 1000 co ? (dodatki? słonie?)
ilkkachu

31
Cóż, jeśli długość łańcucha jest stała (1 M), a długość podciągu / liczby jest stała (3), to technicznie każde rozwiązanie jest stałe w czasie…
Kevin

8
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 rzeczywisty test. Aby sprawdzić, czy możesz im udowodnić, dlaczego nie jest to możliwe, i pokazać im poprawną minimalną złożoność czasową.
James

Odpowiedzi:


168

Wyszedłeś lekko, prawdopodobnie nie chcesz pracować dla funduszu hedgingowego, w którym kwanty nie rozumieją podstawowych algorytmów :-)

Nie ma sposobu na przetworzenie struktury danych o dowolnej wielkości w programieO(1) jeśli tak jak w tym przypadku, każdy element trzeba odwiedzić co najmniej raz. Najlepiej można liczyć to O(n)w tym przypadku, gdzie njest długością łańcucha.

Chociaż, na marginesie, nominalny O(n) algorytm będzie mieć O(1)za stałej wielkości wejściowych tak, technicznie, mogą być tutaj poprawne. Jednak zwykle nie jest to sposób, w jaki ludzie używają analizy złożoności.

Wydaje mi się, że mogłeś zrobić na nich wrażenie na wiele sposobów.

Po pierwsze, informując ich, że tak nie można tego zrobić O(1), chyba że użyjesz powyższego rozumowania „podejrzanego”.

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:

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

chociaż możesz oczywiście zmienić format wyjściowy na dowolny.

I wreszcie, mówiąc im, że prawie na pewno nie ma problemu z plikiemO(n) rozwiązaniem, ponieważ powyższy kod dostarcza wyniki dla jednomilionowego ciągu w znacznie mniej niż pół sekundy. Wydaje się, że skaluje się również dość liniowo, ponieważ ciąg 10 000 000 znaków zajmuje 3,5 sekundy, a 100 000 000 - 36 sekund.

A jeśli potrzebują czegoś więcej, istnieją sposoby na zrównoleglenie tego rodzaju rzeczy, które mogą znacznie przyspieszyć ten proces.

Oczywiście nie w obrębie jednego interpretera Pythona, ze względu na GIL, ale możesz podzielić ciąg na coś podobnego (nakładanie się vvjest wymagane, aby umożliwić prawidłowe przetwarzanie obszarów granicznych):

    vv
123412  vv
    123451
        5123456

Możesz je wyhodować, aby oddzielić pracowników, a następnie połączyć wyniki.

Dzielenie danych wejściowych i łączenie danych wyjściowych prawdopodobnie zatopi wszelkie oszczędności małymi ciągami (a być może nawet milionami cyfr), ale w przypadku znacznie większych zestawów danych może to mieć znaczenie. Oczywiście obowiązuje tutaj moja zwykła mantra „mierzyć, nie zgaduj” .


Ta mantra odnosi się również do innych możliwości, takich jak całkowite obejście Pythona i użycie innego języka, który może być szybszy.

Na przykład, następujący kod C, działa na tym samym sprzęcie, co wcześniej kodu Pythona, obsługuje 100 mln cyfr w 0,6 sekundy, z grubsza taką samą ilość czasu jak kod Python przetworzonego jednego miliona. Innymi słowy, znacznie szybciej:

#include <stdio.h>
#include <string.h>

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;
}

19
Ten „stały rozmiar danych wejściowych” naprawdę brzmi jak kiepski żart, którego nie zrozumiał ani ankieter, ani rozmówca. Każdy algorytm staje O(1)się njest stałe lub ograniczone.
Eric Duminil

5
Jeśli potrzebują czegoś więcej, może nie powinni używać Pythona, przynajmniej dla określonego algorytmu.
Sebastian Redl

3
@ezzzCash Ponieważ mogą zachodzić na siebie punkty, w których ciąg jest „przerywany” podczas próby podejścia równoległego. Ponieważ szukasz 3-cyfrowych grup, -2 umożliwia sprawdzenie obu równoległych grup, aby nie przegapić potencjalnie prawidłowego dopasowania.
code_dredd

5
@ezzzCash To nie brak wiedzy z zakresu programowania równoległego. 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 przegapić prawidłowe 3-cyfrowe dopasowanie na „granicy”, na końcu string1i na początku string2. W związku z tym musisz sprawdzić dopasowania między string1[N/2-2]i string2[2](używając indeksu zaczynającego się od zera) itd. To jest idea.
code_dredd

1
Przy dłuższych sekwencjach cyfr byłoby coś do zyskania dzięki optymalizacji konwersji na liczbę całkowitą za pomocą przesuwanego okna, które pozwala upuścić najwyższą cyfrę i dodać nową. (Narzut w Pythonie prawdopodobnie by to zabił, więc miałby zastosowanie tylko do C lub innych implementacji niskiego poziomu). val -= 100 * (d[i]-'0');aby usunąć wiodącą cyfrę. val = 10*val + d[i+2]-'0'aby zgromadzić nową najmniej znaczącą cyfrę (zwykłe parsowanie ciąg-> liczb całkowitych). val % 100jest prawdopodobnie okropne, ale tylko wtedy, gdy 100jest stałą czasu kompilacji, więc nie używa prawdziwego podziału sprzętowego.
Peter Cordes

78

Stały czas nie jest możliwy. Wszystkie 1 milion cyfr należy sprawdzić co najmniej raz, tak więc jest to złożoność czasowa O (n), gdzie n = 1 milion w tym przypadku.

Aby uzyskać proste rozwiązanie O (n), utwórz tablicę o rozmiarze 1000, która reprezentuje liczbę wystąpień każdej możliwej 3-cyfrowej liczby. Zwiększaj o 1 cyfrę naraz, pierwszy indeks == 0, ostatni indeks == 999997 i tablicę inkrementów [3-cyfrowy numer], aby utworzyć histogram (liczba wystąpień dla każdego możliwego 3-cyfrowego numeru). Następnie wyślij zawartość tablicy z liczbą> 1.


26
@ezzzCash - tak, słownik by działał, ale nie jest potrzebny. Wszystkie możliwe „klucze” są znane z góry, ograniczone do zakresu od 0 do 999. Różnica w narzutach to czas potrzebny do uzyskania dostępu opartego na kluczu przy użyciu 3 ciągów znaków jako kluczy, w porównaniu z czasem potrzebnym do konwersji 3 ciąg cyfr do indeksu, a następnie użycie indeksu w celu uzyskania dostępu do tablicy.
rcgldr

4
Jeśli chcesz sztuczek numerycznych, możesz również zdecydować się na BCD i zapisać trzy cyfry w 12 bitach. I dekoduj cyfry ASCII, maskując niskie 4 bity. Ale ten x-'0'wzorzec nie jest prawidłowy w Pythonie, jest to C-izm (gdzie znaki są liczbami całkowitymi).
Yann Vernier

5
@LorenPechtel: Wyszukiwanie w słowniku w Pythonie jest naprawdę szybkie. To prawda, dostęp do tablicy jest jeszcze szybszy, więc gdybyśmy od początku mieli do czynienia z liczbami całkowitymi, miałbyś rację. Jednak w tym przypadku mamy ciągi o 3 długościach, które najpierw musimy przekonwertować na liczby całkowite, jeśli chcemy ich używać z tablicami. Okazuje się, że w przeciwieństwie do tego, czego można by się początkowo spodziewać, przeszukiwanie słownika jest w rzeczywistości szybsze niż konwersja liczb całkowitych + dostęp do tablicy. W tym przypadku rozwiązanie macierzy jest w rzeczywistości o 50% wolniejsze.
Aleksi Torhamo

2
Myślę, że można by argumentować, że jeśli liczba wejściowa ma zawsze dokładnie 1 milion cyfr, to algorytmem jest O (1), ze stałym współczynnikiem 1 miliona.
tobias_k

2
@AleksiTorhamo - Jeśli celem jest porównanie względnych prędkości implementacji algorytmu, wolałbym tradycyjny język, taki jak C lub C ++, ponieważ Python jest znacznie wolniejszy i wydaje się mieć narzuty unikalne dla Pythona w porównaniu z innymi językami.
rcgldr

14

Milion to niewiele, jak na odpowiedź, której udzielę poniżej. Spodziewając się tylko, że musisz być w stanie uruchomić rozwiązanie w wywiadzie, bez przerwy, a następnie Poniższe 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ł możliwości korzystania ze standardowych kolekcji bibliotek.

Wersja z równoległym wykonaniem

Napisałem na ten temat wpis na blogu z dokładniejszym wyjaśnieniem.


Działa dobrze i wydaje się być najszybszym, nie tępym rozwiązaniem.
Eric Duminil

3
@EricDuminil, myślę, że nie powinieneś martwić się o szybkie czasy tutaj, kiedy większość podanych rozwiązań nie opóźni cię zbytnio. O wiele lepiej pokazać, że dobrze znasz bibliotekę standardową Pythona i myślę, że możesz napisać łatwy do utrzymania kod w sytuacji rozmowy kwalifikacyjnej. (Chyba że ankieter podkreślił znaczenie czasu, po czym należy zapytać o rzeczywiste terminy przed oceną, co będzie dalej).
Paddy3118

1
Zgadzamy się w 100%. Chociaż nie jestem pewien, czy jakakolwiek odpowiedź jest w ogóle odpowiednia, jeśli ankieter naprawdę uważa, że ​​jest to możliwe O(1).
Eric Duminil

1
Jeśli ankieter podkreślił, że jest to krytyczne czasowo, to po profilowaniu w celu potwierdzenia, że ​​jest to limit, być może nadszedł czas, aby napisać moduł C, aby rozwiązać to wąskie gardło. Mam skrypt, który odnotował 84-krotną poprawę w stosunku do kodu Pythona po przełączeniu się na moduł AC.
TemporalWolf

Cześć @TemporalWolf, przeczytałem to, co powiedziałeś, a potem pomyślałem, że innym, szybszym i skalowalnym rozwiązaniem może być zmiana go na algorytm równoległy, aby można go było uruchomić w wielu procesach na farmie obliczeniowej / w chmurze. Musisz podzielić ciąg na n sekcji; zachodzenie na ostatnie 3 znaki każdej sekcji z następną sekcją. Każda sekcja może być następnie niezależnie skanowana w poszukiwaniu trójek, trójki zsumowane, a trzy znaki na końcu wszystkich sekcji oprócz ostatniej mogą zostać odjęte, tak jakby zostały policzone podwójnie. Mam kod i prawdopodobnie
zamienię

13

Prostym rozwiązaniem O (n) byłoby policzenie 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)

Spowoduje to przeszukanie wszystkich 1 miliona cyfr 1000 razy.

Przechodzenie 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)

Timing pokazuje, że iteracja tylko raz po indeksie jest dwa razy szybsza niż przy użyciu count.


37
Czy obowiązuje zniżka na czarny piątek text.count()?
Eric Duminil

3
@EricDuminil Masz rację, ale ponieważ text.countjest to zrobione w szybkim języku kompilowanym (np. C), w przeciwieństwie do powolnego interpretowanego zapętlania na poziomie Pythona, tak, jest to zniżka.
John 1024

Liczenie każdej liczby osobno jest bardzo nieefektywne, ale jest to stały czas, więc nadal O (n).
Loren Pechtel

11
Zaproponowana opcja, która używa, countjest nieprawidłowa, ponieważ nie będzie liczyć nakładających się wzorców. Zauważ, że '111'.count('11') == 1kiedy byśmy się tego spodziewali 2.
Cireo

2
Ponadto, Twój „proste O(n)rozwiązanie” jest w rzeczywistości O(10**d * n)z dliczby poszukiwanych cyfr i nłącznej długości łańcucha. Drugi to O(n)czas i O(10**d + n)przestrzeń.
Eric Duminil

10

Oto implementacja NumPy algorytmu „konsensusu” O (n): przejdź przez wszystkie trojaczki i bin na bieżąco. Kategoryzacja jest wykonywana po napotkaniu, powiedzmy "385", dodaniu jednego do przedziału [3, 8, 5], co jest operacją O (1). Pojemniki ułożone są w 10x10x10sześcian. Ponieważ binowanie jest w pełni wektoryzowane, w kodzie nie ma pętli.

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ż czyste rozwiązanie Pythona @ Daniela w przypadku dużych zbiorów danych. Przykładowe dane wyjściowe:

# 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

Prawdopodobnie znacznie szybciej spłaszczyć ciąg cyfr zamiast zagnieżdżonych pojemników, chyba że NumPy zaimplementuje go jako macierz 3D z wydajnym indeksowaniem. Z którą wersją @ Daniel's miałeś czas; ten, który wyszukuje ciąg znaków dla każdej liczby całkowitej, czy ten z histogramem?
Peter Cordes

2
@PeterCordes Wątpię w to. ndarrays, podstawowy typ numpy, dotyczą wydajnego przechowywania, manipulowania i indeksowania wielowymiarowych tablic liczb. Czasami możesz zgolić kilka% przez spłaszczenie, ale w tym przypadku ręczne wykonanie 100 x [0] + 10 x [1] + x [2] nie da wiele. Użyłem tego, który @Daniel powiedział, że jest szybszy, możesz sam sprawdzić kod testu.
Paul Panzer

Naprawdę nie znam NumPy (lub ogólnie Pythona; głównie zajmuję się C i tuningiem wydajności assemblera dla x86), ale myślę, że masz jedną tablicę 3D, prawda? Myślałem na podstawie twojego tekstu w języku angielskim (którego najwyraźniej nawet nie przeczytałem uważnie), że masz faktycznie zagnieżdżone obiekty Pythona i indeksujesz je oddzielnie. Ale tak nie jest, więc nvm mój pierwszy komentarz.
Peter Cordes

Myślę, że czysta wersja Pythona, której użyłeś, jest prawie taką samą implementacją histogramu, jak używane były jeszcze wyższe głosowane odpowiedzi, ale jeśli różne sposoby pisania jej w Pythonie mają duży wpływ na szybkość.
Peter Cordes

3

Rozwiązałbym 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 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 ciągu i jest, jak sądzę, najlepszym, jakie można uzyskać.


Możesz po prostu użyć pliku Counter. Nie potrzebujesz final_dicti nie musisz aktualizować go przy każdej iteracji.
Eric Duminil

2

Jak rozumiem, nie możesz mieć rozwiązania w stałym czasie. Potrzeba co najmniej jednego przejścia przez milion cyfr (zakładając, że jest to ciąg). Możesz mieć 3-cyfrową kroczącą iterację po cyfrach liczby o milionie długości i zwiększyć wartość klucza skrótu o 1, jeśli już istnieje, lub utworzyć nowy klucz skrótu (zainicjowany przez wartość 1), jeśli nie istnieje już w 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ć w dół do kluczy, które mają wartość elementu większą niż 1.


2

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

Jednakże, algorytm może być wykonane w O (1) przestrzeń . Musisz tylko zapisać liczbę każdej 3-cyfrowej liczby, więc potrzebujesz tablicy zawierającej 1000 wpisów. Następnie możesz przesyłać strumieniowo numer w formacie.

Domyślam się, że albo ankieter źle wypowiedział się, kiedy podał ci rozwiązanie, albo źle usłyszałeś „stały czas”, kiedy powiedział „stała przestrzeń”.


Jak zauważyli inni, podejście histogramowe to O(10**d)dodatkowa spacja, gdzie djest liczba cyfr dziesiętnych, których szukasz.
Peter Cordes

1
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ż raz.
gnasher729

1

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 tablic jest bardzo szybka (nawet szybsza niż metoda numpy @ paul-panzer!). Oczywiście oszukuje, ponieważ nie jest technicznie zakończony po zakończeniu, ponieważ zwraca generator. Nie musi też sprawdzać każdej iteracji, czy 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)]

1
Więc co dokładnie porównujesz? Nie powinieneś zwracać list zamiast nieużywanych generatorów?
Eric Duminil

Countersnie są używane w ten sposób. Użyte prawidłowo, na twoim przykładzie stają się najszybszą opcją. Jeśli używasz timeitz listą zamiast generatora, twoja metoda będzie wolniejsza niż Counterlub dict. Zobacz tutaj .
Eric Duminil

Wreszcie, możesz f_arraybyć szybszy, jeśli najpierw przekonwertujesz każdy znak na int: ints = [int(c) for c in text]a następnie użyjesz i, j, k = ints[n:n+3].
Eric Duminil


1

Oto moje rozwiązanie:

from collections import defaultdict
string = "103264685134845354863"
d = defaultdict(int)
for elt in range(len(string)-2):
    d[string[elt:elt+3]] += 1
d = {key: d[key] for key in d.keys() if d[key] > 1}

Przy odrobinie kreatywności w pętli for (i dodatkowej liście wyszukiwania z na przykład True / False / None) powinieneś być w stanie pozbyć się ostatniej linii, ponieważ chcesz utworzyć tylko klucze w dict, które odwiedziliśmy raz do tego momentu . Mam nadzieję, że to pomoże :)


Zobacz odpowiedź pho7 . I komentarze. Spróbuj dowiedzieć się, dlaczego nie ma wielu głosów.
siwobrody

0

-Opowiadanie z perspektywy C. -Możesz otrzymać int 3-d tablicę wyników [10] [10] [10]; -Przejdź z 0-tej lokalizacji do n-4-tej lokalizacji, gdzie n to rozmiar tablicy ciągów. -W każdej lokalizacji sprawdź bieżącą, następną i następną. -Increment the cntr as resutls [current] [next] [next's next] ++; -Drukuj wartości

results[1][2][3]
results[2][3][4]
results[3][4][5]
results[4][5][6]
results[5][6][7]
results[6][7][8]
results[7][8][9]

-To jest O (n) czas, nie ma porównań. -Możesz tutaj uruchomić kilka równoległych rzeczy, dzieląc tablicę i obliczając dopasowania wokół partycji.


-1
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

Dziękuję za odpowiedź, ale jest ona zbyt podobna do algorytmu podanego przez @abhishek arora 5-6 dni temu. Również pierwotne pytanie nie dotyczyło algorytmu, ale raczej inne pytanie (na które udzielono już wielu odpowiedzi)
Data
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.