Geben Sie bei einer Zeichenfolge von einer Million Zahlen alle sich wiederholenden dreistelligen Zahlen zurück

137

Ich hatte vor einigen Monaten ein Interview mit einer Hedgefondsfirma in New York und leider habe ich das Praktikumsangebot als Daten- / Software-Ingenieur nicht erhalten. (Sie baten auch um die Lösung in Python.)

Ich habe das erste Interviewproblem ziemlich vermasselt ...

Frage: Schreiben Sie bei einer Zeichenfolge von einer Million Zahlen (z. B. Pi) eine Funktion / ein Programm, die alle sich wiederholenden dreistelligen Zahlen und die Anzahl der Wiederholungen größer als 1 zurückgibt

Beispiel: Wenn der String: 123412345123456wäre, würde die Funktion / das Programm Folgendes zurückgeben:

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

Sie gaben mir die Lösung nicht, nachdem ich das Interview nicht bestanden hatte, aber sie sagten mir, dass die zeitliche Komplexität für die Lösung konstant 1000 war, da alle möglichen Ergebnisse zwischen:

000 -> 999

Jetzt, wo ich darüber nachdenke, denke ich nicht, dass es möglich ist, einen Algorithmus mit konstanter Zeit zu entwickeln. Ist es?

its.david
quelle
68
Wenn sie denken, dass die Lösung eine Konstante von 1000 ist, dann denke ich, dass sie alle dreistelligen Zahlen erstellt und dann nach Regex gesucht hätten. Es ist sehr üblich, dass Leute denken, dass Operationen, die sie nicht geschrieben / gesehen haben, "kostenlos" sind. Ich bin mir ziemlich sicher, dass dies linear zur Länge der Zeichenfolge ist.
Mypetlion
54
Nitpickingly, wenn die Eingabegröße eine Konstante ist, ist jeder Algorithmus konstante Zeit ;-)
Paŭlo Ebermann
34
eine Konstante von 1000 was ? (Ergänzungen? Elefanten?)
Ilkkachu
31
Nun, wenn die Stringlänge konstant ist (1M) und die Teilstring- / Zahlenlänge konstant ist (3), dann ist technisch jede Lösung eine konstante Zeit…
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 Dies war wahrscheinlich der eigentliche Test. Um zu sehen, ob Sie ihnen beweisen können, warum dies nicht möglich ist, und um ihnen die richtige minimale Zeitkomplexität zu zeigen.
James

Antworten:

168

Sie sind leichtfertig ausgestiegen und möchten wahrscheinlich nicht für einen Hedgefonds arbeiten, bei dem die Quants grundlegende Algorithmen nicht verstehen :-)

Es gibt keine Möglichkeit, eine Datenstruktur beliebiger Größe zu verarbeiten, O(1)wenn Sie wie in diesem Fall jedes Element mindestens einmal besuchen müssen. Das Beste, auf das Sie hoffen können, ist O(n)in diesem Fall, wo ndie Länge der Zeichenfolge ist.

Obwohl, wie nebenbei bemerkt, ein nominaler O(n)Algorithmus wird sein O(1)für eine feste Eingangsgröße so, technisch gesehen , kann sie richtig hier gewesen. Normalerweise verwenden Menschen die Komplexitätsanalyse jedoch nicht so.

Mir scheint, Sie hätten sie auf verschiedene Weise beeindrucken können.

Indem Sie sie zunächst darüber informieren, dass dies nicht möglich ist, es O(1)sei denn, Sie verwenden die oben angegebene "verdächtige" Argumentation.

Zweitens, indem Sie Ihre Elite-Fähigkeiten unter Beweis stellen, indem Sie Pythonic-Code wie den folgenden bereitstellen:

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

Dies gibt aus:

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

Natürlich können Sie das Ausgabeformat nach Belieben ändern.

Und schließlich, wenn man ihnen sagt, dass es mit ziemlicher Sicherheit keine gibt Problem mit einer O(n)Lösung, da der obige Code in weniger als einer halben Sekunde Ergebnisse für eine einstellige Zeichenfolge liefert. Es scheint auch ziemlich linear zu skalieren, da eine Zeichenfolge mit 10.000.000 Zeichen 3,5 Sekunden und eine Zeichenfolge mit 100.000.000 Zeichen 36 Sekunden dauert.

Und wenn sie Besseres brauchen , gibt es Möglichkeiten, solche Dinge zu parallelisieren, die es erheblich beschleunigen können.

Natürlich nicht innerhalb eines einzelnen Python-Interpreters, aufgrund der GIL, aber Sie könnten die Zeichenfolge in so etwas aufteilen (eine Überlappung vvist erforderlich, um eine ordnungsgemäße Verarbeitung der Grenzbereiche zu ermöglichen):

    vv
123412  vv
    123451
        5123456

Sie können diese auf separate Mitarbeiter verteilen und die Ergebnisse anschließend kombinieren.

Die Aufteilung der Eingabe und die Kombination der Ausgabe überschwemmen wahrscheinlich jede Einsparung mit kleinen Zeichenfolgen (und möglicherweise sogar Zeichenfolgen mit Millionen Ziffern), aber bei viel größeren Datenmengen kann dies durchaus einen Unterschied bewirken. Hier gilt natürlich mein übliches Mantra "Messen, nicht raten" .


Dieses Mantra gilt auch für andere Möglichkeiten, z. B. die Umgehung von Python insgesamt und die Verwendung einer anderen Sprache, die möglicherweise schneller ist.

Der folgende C-Code, der auf derselben Hardware wie der frühere Python-Code ausgeführt wird, verarbeitet beispielsweise hundert Millionen Ziffern in 0,6 Sekunden, ungefähr so ​​lange, wie der Python-Code eine Million verarbeitet hat . Mit anderen Worten, viel schneller:

#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;
}
paxdiablo
quelle
19
Diese "feste Eingabegröße" klingt wirklich nach einem schlechten Witz, den entweder der Interviewer oder der Interviewte nicht verstanden haben. Jeder Algorithmus wird O(1)wird nfestgelegt oder begrenzt.
Eric Duminil
5
Wenn sie etwas Besseres brauchen, sollten sie Python vielleicht nicht verwenden, zumindest nicht für den spezifischen Algorithmus.
Sebastian Redl
3
@ezzzCash Da es bei den Versuchen, einen parallelen Ansatz zu versuchen, zu Überlappungen an den Punkten kommen kann, an denen die Zeichenfolge "aufgebrochen" wird. Da Sie nach dreistelligen Gruppen suchen, können Sie mit -2 für beide parallelen Gruppierungen keine potenziell gültige Übereinstimmung verpassen.
code_dredd
5
@ezzzCash Es fehlt nicht an parallelen Programmierkenntnissen. Betrachten Sie eine Länge N. Wenn Sie es an der Position in zwei Teile aufteilen N/2, müssen Sie dennoch berücksichtigen, dass Sie eine gültige dreistellige Übereinstimmung am "Rand" am Ende string1und am Anfang von verpassen könnten string2. Daher müssen Sie Übereinstimmungen zwischen string1[N/2-2]und string2[2](unter Verwendung eines auf Null basierenden Index) usw. überprüfen . Das ist die Idee.
code_dredd
1
Bei längeren Ziffernfolgen kann die Optimierung der Konvertierung in eine Ganzzahl mit einem Schiebefenster, mit dem Sie die höchste Ziffer löschen und eine neue Ziffer hinzufügen können, etwas bewirken. (Python-Overhead würde dies wahrscheinlich beenden, sodass es nur für C- oder andere Low-Level-Implementierungen gilt.) val -= 100 * (d[i]-'0');um die führende Ziffer fallen zu lassen. val = 10*val + d[i+2]-'0'um eine neue niedrigstwertige Ziffer zu akkumulieren (normales String-> Integer-Parsing). val % 100ist möglicherweise nicht schrecklich, aber nur, wenn 100es sich um eine Konstante zur Kompilierungszeit handelt, sodass keine echte HW-Teilung verwendet wird.
Peter Cordes
78

Konstante Zeit ist nicht möglich. Alle 1 Million Stellen müssen mindestens einmal betrachtet werden, so dass dies eine zeitliche Komplexität von O (n) ist, wobei in diesem Fall n = 1 Million ist.

Erstellen Sie für eine einfache O (n) -Lösung ein Array der Größe 1000, das die Anzahl der Vorkommen jeder möglichen dreistelligen Zahl darstellt. Stellen Sie jeweils 1 Stelle, den ersten Index == 0, den letzten Index == 999997 und das Inkrementarray [3-stellige Zahl] vor, um ein Histogramm zu erstellen (Anzahl der Vorkommen für jede mögliche 3-stellige Zahl). Geben Sie dann den Inhalt des Arrays mit einer Anzahl> 1 aus.

rcgldr
quelle
26
@ezzzCash - ja ein Wörterbuch würde funktionieren, aber es wird nicht benötigt. Alle möglichen "Schlüssel" sind im Voraus bekannt und auf den Bereich von 0 bis 999 begrenzt. Der Unterschied im Overhead besteht in der Zeit, die für einen schlüsselbasierten Zugriff mit 3 Zeichenfolgen als Schlüssel benötigt wird, im Vergleich zu der Zeit, die für die Konvertierung einer 3 benötigt wird Ziffernfolge zu einem Index und dann den Index verwenden, um auf das Array zuzugreifen.
rcgldr
4
Wenn Sie numerische Tricks möchten, können Sie sich auch für BCD entscheiden und die drei Ziffern in 12 Bit speichern. Und dekodieren Sie ASCII-Ziffern, indem Sie die niedrigen 4 Bits maskieren. Dieses x-'0'Muster ist in Python jedoch nicht gültig, es ist ein C-Ismus (wobei Zeichen Ganzzahlen sind).
Yann Vernier
5
@LorenPechtel: Wörterbuchsuchen in Python sind sehr schnell. Zugegeben, der Array-Zugriff ist noch schneller. Wenn wir uns also von Anfang an mit Ganzzahlen befassen, haben Sie Recht. In diesem Fall haben wir jedoch Zeichenfolgen mit 3 Längen, die wir zuerst in Ganzzahlen konvertieren müssen, wenn wir sie mit Arrays verwenden möchten. Es stellt sich heraus, dass die Wörterbuchsuche entgegen den Erwartungen zunächst schneller ist als die Ganzzahlkonvertierung + Arrayzugriff. Die Array-Lösung ist in diesem Fall tatsächlich 50% langsamer.
Aleksi Torhamo
2
Ich denke , man könnte argumentieren , dass , wenn die Eingangsnummer hat immer genau 1 Million Stellen, als Algorithmus ist O (1), mit einem konstanten Faktor von 1 Million.
tobias_k
2
@AleksiTorhamo - Wenn das Ziel darin besteht, die relativen Implementierungsgeschwindigkeiten für einen Algorithmus zu vergleichen, würde ich eine traditionelle Sprache wie C oder C ++ bevorzugen, da Python erheblich langsamer ist und im Vergleich zu anderen Sprachen einen für Python einzigartigen Overhead zu haben scheint.
rcgldr
14

Eine Million ist klein für die Antwort, die ich unten gebe. Erwarten Sie nur, dass Sie in der Lage sein müssen, die Lösung im Interview ohne Pause auszuführen. Dann funktioniert Folgendes in weniger als zwei Sekunden und liefert das erforderliche Ergebnis:

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)

Hoffentlich würde der Interviewer nach der Verwendung der Standardbibliothekssammlungen suchen. Gegenklasse.

Parallele Ausführungsversion

Ich habe einen Blog-Beitrag dazu mit mehr Erklärungen geschrieben.

Paddy3118
quelle
Es funktioniert gut und scheint die schnellste, nicht numpy Lösung zu sein.
Eric Duminil
3
@EricDuminil, ich denke nicht, dass Sie sich Sorgen machen sollten, wenn Sie die Fastet-Timings hier haben, wenn die meisten gegebenen Lösungen Sie nicht viel verzögern. Es ist weitaus besser zu zeigen, dass Sie die Python-Standardbibliothek gut verstehen und in einer Interview-Situation wartbaren Code schreiben können, denke ich. (Es sei denn, der Interviewer betonte die Zeitkritikalität, woraufhin Sie nach dem tatsächlichen Zeitpunkt fragen sollten, bevor Sie beurteilen, was als nächstes kommt.)
Paddy3118
1
Wir sind uns zu 100% einig. Obwohl ich nicht sicher bin, ob eine Antwort überhaupt relevant ist, wenn der Interviewer wirklich glaubt, dass dies möglich ist O(1).
Eric Duminil
1
Wenn der Interviewer betonte, dass dies zeitkritisch sei, kann es nach der Profilerstellung zur Bestätigung dieses Grenzwerts an der Zeit sein, ein C-Modul zu schreiben, um diesen Engpass zu beheben. Ich habe ein Skript, das eine 84-fache Verbesserung gegenüber Python-Code festgestellt hat, nachdem wir auf die Verwendung eines AC-Moduls umgestellt haben.
TemporalWolf
Hallo @TemporalWolf, ich habe gelesen, was Sie gesagt haben, und dann gedacht, dass eine andere, schnellere und skalierbare Lösung darin bestehen könnte, es in einen parallelen Algorithmus umzuwandeln, damit es auf vielen Prozessen in einer Rechenfarm / Cloud ausgeführt werden kann. Sie müssen die Zeichenfolge in n Abschnitte aufteilen. Überlappen der letzten 3 Zeichen jedes Abschnitts mit dem nächsten Abschnitt. Jeder Abschnitt kann dann unabhängig nach Tripeln gescannt, die Tripel summiert und die drei Zeichen am Ende aller bis auf den letzten Abschnitt abgezogen werden, da dies doppelt gezählt worden wäre. Ich habe den Code und werde ihn wahrscheinlich in einen Blog-Beitrag
verwandeln
13

Die einfache O (n) -Lösung wäre, jede dreistellige Zahl zu zählen:

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

Dies würde 1000 Mal alle 1 Million Ziffern durchsuchen.

Die Ziffern nur einmal durchlaufen:

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)

Das Timing zeigt, dass die Iteration nur einmal über den Index doppelt so schnell ist wie die Verwendung count.

Daniel
quelle
37
Gibt es einen Rabatt für schwarzen Freitag text.count()?
Eric Duminil
3
@EricDuminil Sie haben einen guten Punkt, aber da text.countdies in einer kompilierten Hochgeschwindigkeitssprache (z. B. C) erfolgt, im Gegensatz zu langsamen, auf Python-Ebene interpretierten Schleifen, gibt es einen Rabatt.
John1024
Es ist sehr ineffizient, jede Zahl einzeln zu zählen, aber es ist eine konstante Zeit, also immer noch O (n).
Loren Pechtel
11
Die von Ihnen vorgeschlagene Option countist falsch, da überlappende Muster nicht berücksichtigt werden. Beachten Sie, dass, '111'.count('11') == 1wenn wir es erwarten würden 2.
Cireo
2
Auch Ihre „einfache O(n)Lösung“ ist eigentlich O(10**d * n)mit dder Anzahl gesuchter Ziffern und nder Gesamtlänge des Strings. Der zweite ist O(n)Zeit und O(10**d + n)Raum.
Eric Duminil
10

Hier ist eine NumPy-Implementierung des "Consensus" O (n) -Algorithmus: Gehen Sie alle Triplets und Bin durch, während Sie gehen. Das Binning erfolgt, indem Sie auf "385" stoßen und eins zu bin [3, 8, 5] hinzufügen, was eine O (1) -Operation ist. Die Behälter sind in einem 10x10x10Würfel angeordnet . Da das Binning vollständig vektorisiert ist, enthält der Code keine Schleife.

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:]))

Es überrascht nicht, dass NumPy bei großen Datenmengen etwas schneller ist als die reine Python-Lösung von @ Daniel. Beispielausgabe:

# 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
Paul Panzer
quelle
Wahrscheinlich erheblich schneller, um die Ziffernfolge zu reduzieren, anstatt verschachtelte Bins zu haben, es sei denn, NumPy implementiert sie schließlich als 3D-Matrix mit effizienter Indizierung. Gegen welche Version von @ Daniel's hast du Zeit? derjenige, der eine Zeichenfolgensuche für jede Ganzzahl ausführt, oder derjenige mit einem Histogramm?
Peter Cordes
2
@ PeterCordes Ich bezweifle es. ndarrayBei s, dem Kerntyp, geht es um die effiziente Speicherung, Bearbeitung und Indizierung mehrdimensionaler Zahlenfelder. Manchmal können Sie sich durch Abflachen um einige Prozent rasieren, aber in diesem Fall bringt es Ihnen nicht viel, wenn Sie 100 x [0] + 10 x [1] + x [2] von Hand ausführen. Ich habe den verwendet, von dem @Daniel sagte, er sei schneller. Sie können den Benchmark-Code selbst überprüfen.
Paul Panzer
Ich kenne NumPy nicht wirklich (oder Python im Allgemeinen; meistens optimiere ich die C- und Assembly-Leistung für x86), aber ich denke, Sie haben ein einziges 3D-Array, oder? Ich dachte aus Ihrem englischen Text (den ich anscheinend nicht einmal sorgfältig gelesen habe), dass Sie tatsächlich verschachtelte Python-Objekte hatten und diese separat indizierten. Aber das ist nicht der Fall, also nvm mein erster Kommentar.
Peter Cordes
Ich denke, die reine Python-Version, die Sie verwendet haben, ist so ziemlich die gleiche Histogramm-Implementierung wie die noch höher bewerteten Antworten, aber wenn unterschiedliche Schreibweisen in Python die Geschwindigkeit stark beeinflussen.
Peter Cordes
3

Ich würde das Problem wie folgt lösen:

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

Auf Ihre Beispielzeichenfolge angewendet ergibt dies:

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

Diese Lösung läuft in O (n), wobei n die Länge der bereitgestellten Zeichenfolge ist, und ich denke, sie ist die beste, die Sie bekommen können.

pho7
quelle
Sie könnten einfach eine verwenden Counter. Sie benötigen keine final_dictund müssen diese nicht bei jeder Iteration aktualisieren.
Eric Duminil
2

Nach meinem Verständnis können Sie die Lösung nicht in einer konstanten Zeit haben. Es dauert mindestens einen Durchgang über die millionenstellige Zahl (vorausgesetzt, es handelt sich um eine Zeichenfolge). Sie können eine dreistellige fortlaufende Iteration über die Ziffern der Millionenlänge durchführen und den Wert des Hash-Schlüssels um 1 erhöhen, wenn er bereits vorhanden ist, oder einen neuen Hash-Schlüssel (initialisiert durch den Wert 1) erstellen, wenn er noch nicht vorhanden ist das Wörterbuch.

Der Code sieht ungefähr so ​​aus:

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

Sie können bis zu den Schlüsseln filtern, deren Elementwert größer als 1 ist.

Abhishek Arora
quelle
2

Wie in einer anderen Antwort erwähnt, können Sie diesen Algorithmus nicht in konstanter Zeit ausführen, da Sie mindestens n Ziffern betrachten müssen. Die lineare Zeit ist die schnellste, die Sie bekommen können.

Der Algorithmus kann jedoch im O (1) -Raum durchgeführt werden . Sie müssen nur die Anzahl jeder dreistelligen Nummer speichern, sodass Sie ein Array mit 1000 Einträgen benötigen. Sie können die Nummer dann streamen.

Ich vermute, dass entweder der Interviewer falsch geschrieben hat, als er Ihnen die Lösung gegeben hat, oder dass Sie "konstante Zeit" falsch gehört haben, als er "konstanter Raum" sagte.

Cort Ammon
quelle
Wie andere bereits betont haben, bietet der Histogrammansatz O(10**d)zusätzlichen Platz, wobei ddie Anzahl der Dezimalstellen angegeben wird , nach denen Sie suchen.
Peter Cordes
1
Der Wörterbuchansatz wäre O (min (10 ^ d, n)) für n Ziffern. Zum Beispiel, wenn Sie n = 10 ^ 9 Ziffern haben und die seltenen 15-stelligen Sequenzen finden möchten, die mehr als einmal vorkommen.
Gnasher729
1

Hier ist meine Antwort:

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

Die Array-Suchmethode ist sehr schnell (sogar schneller als die Numpy-Methode von @ paul-panzer!). Natürlich betrügt es, da es nach Abschluss nicht technisch fertig ist, weil es einen Generator zurückgibt. Es muss auch nicht jede Iteration überprüft werden, ob der Wert bereits vorhanden ist, was wahrscheinlich sehr hilfreich ist.

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)]
Turksarama
quelle
1
Also, was vergleichst du genau? Sollten Sie keine Listen anstelle nicht verwendeter Generatoren zurückgeben?
Eric Duminil
Counterswerden nicht so verwendet. Bei richtiger Anwendung werden sie mit Ihrem Beispiel zur schnellsten Option. Wenn Sie timeiteine Liste mit einem Generator verwenden, wird Ihre Methode langsamer als Counteroder dict. Siehe hier .
Eric Duminil
Schließlich f_arraykönnten Sie schneller sein, wenn Sie zuerst jedes Zeichen in ein int konvertieren ints = [int(c) for c in text]und dann verwenden i, j, k = ints[n:n+3].
Eric Duminil
1

Bild als Antwort:

BILD ALS ANTWORT

Sieht aus wie ein Schiebefenster.

天 杀 包子 神
quelle
1

Hier ist meine Lösung:

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}

Mit ein wenig Kreativität in der for-Schleife (und einer zusätzlichen Suchliste mit True / False / None zum Beispiel) sollten Sie in der Lage sein, die letzte Zeile loszuwerden, da Sie nur Schlüssel in Diktaten erstellen möchten, die wir bis zu diesem Zeitpunkt einmal besucht haben . Ich hoffe es hilft :)

econ
quelle
Siehe die Antwort von pho7 . Und Kommentare. Versuchen Sie herauszufinden, warum es nicht viele Stimmen gibt.
Graubart
0

- Erzählen aus der Perspektive von C. - Sie können int-3-d-Array-Ergebnisse erzielen [10] [10] [10]; -Gehen Sie von der 0. Position zur n-4. Position, wobei n die Größe des String-Arrays ist. -Überprüfen Sie an jedem Ort den aktuellen, den nächsten und den nächsten. -Inkrementiere den cntr als resutls [current] [next] [next's next] ++; -Drucken Sie die Werte von

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]

-Es ist O (n) Zeit, es gibt keine Vergleiche. -Sie können hier einige parallele Dinge ausführen, indem Sie das Array partitionieren und die Übereinstimmungen um die Partitionen berechnen.

Suresh
quelle
-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
Gourav Mittal
quelle
Vielen Dank für Ihre Antwort, aber es ist einem Algorithmus zu ähnlich, wie er vor 5-6 Tagen von @abhishek arora angegeben wurde. Auch die ursprüngliche Frage fragte nicht nach dem Algorithmus, sondern nach einer anderen Frage (die bereits mehrfach beantwortet wurde)
its.david