Warum ist dieser o (n) Drei-Wege-Disjunktion Algorithmus langsamer als dann o (n^3) Version?

Question

O (n), weil die Liste Umwandeln einzustellen O (n) Zeit ist, Einsteigen Schnitt O (n) Zeit und Len ist O (n)

def disjoint3c(A, B, C): 
    """Return True if there is no element common to all three lists.""" 
    return len(set(A) & set(B) & set(C)) == 0 

oder in ähnlicher Weise, sollte klar O (N) ist,

def set_disjoint_medium (a, b, c): 
    a, b, c = set(a), set(b), set(c) 
    for elem in a: 
     if elem in b and elem in c: 
      return False 
    return True 

doch ist diese O (n^3) Code:

def set_disjoint_slowest (a, b, c): 
    for e1 in a: 
     for e2 in b: 
      for e3 in c: 
       if e1 == e2 == e3: 
        return False 
    return True 

läuft schneller

Zeit sehen, wo Algorithmus eins ist das n^3, und Algorithmus drei ist der O (n) gesetzt Code ... Algorithmus zwei ist eigentlich n^2, wo wir Algorithmus eins optimieren durch Prüfung auf Disjunktheit vor der dritten Schleife startet

Size Input (n): 10000 

Algorithm One: 0.014993906021118164 

Algorithm Two: 0.013481855392456055 

Algorithm Three: 0.01955580711364746 

Size Input (n): 100000 

Algorithm One: 0.15916991233825684 

Algorithm Two: 0.1279449462890625 

Algorithm Three: 0.18677806854248047 

Size Input (n): 1000000 

Algorithm One: 1.581618070602417 

Algorithm Two: 1.146049976348877 

Algorithm Three: 1.8179030418395996 

Answer 1

Die Kommentare machten Klarstellungen über die Big-Oh Notationen. Also werde ich einfach mit dem Testen des Codes beginnen.

Hier ist das Setup, mit dem ich die Geschwindigkeit des Codes getestet habe.

import random 

# Collapsed these because already known 
def disjoint3c(A, B, C): 
def set_disjoint_medium (a, b, c): 
def set_disjoint_slowest (a, b, c): 

a = [random.randrange(100) for i in xrange(10000)] 
b = [random.randrange(100) for i in xrange(10000)] 
c = [random.randrange(100) for i in xrange(10000)] 

# Ran timeit. 
# Results with timeit module. 
1-) 0.00635750419422 
2-) 0.0061145967287 
3-) 0.0487953200969 

nun die Ergebnisse, wie Sie sehen, die O(n^3) Lösung läuft -mal langsamer als die anderen Lösungen. Aber das ist immer noch schnell für einen solchen Algorithmus (noch schneller in Ihrem Test). Warum passiert das?

Da mittlere und langsamste Lösungen, die Sie verwendet haben, beendet die Ausführung des Codes , sobald ein gemeinsames Element erkannt wird. Die volle Komplexität des Codes wird also nicht realisiert. Es bricht, sobald es eine Antwort findet. Warum lief die langsamste Lösung fast so schnell wie die anderen in Ihrem Test? Wahrscheinlich, weil sie die Antwort näher am Anfang der Listen findet.

Um dies zu testen, könnten Sie die Listen wie folgt erstellen. Probieren Sie es selbst aus.

a = range(1000) 
b = range(1000, 2000) 
c = range(2000, 3000) 

nun der wirkliche Unterschied zwischen den Zeiten wird deutlich sein, weil die langsamste Lösung laufen muss, bis er alle Iterationen beendet, weil es kein gemeinsames Element ist.

So ist es eine Situation von Worst case und besten Fall Leistung.

kein Teil der Frage bearbeiten: Also, was ist, wenn Sie die Geschwindigkeit der Suche nach frühen gemeinsamen Vorkommen beibehalten möchten, aber auch nicht wollen, Komplexität zu erhöhen. Ich habe eine grobe Lösung dafür gefunden, vielleicht können erfahrene Benutzer einen schnelleren Code vorschlagen.

Was im Grunde in diesem Code getan wird, ist, vermeiden Sie die Umwandlung aller Listen zu Sätzen am Anfang. Durchlaufen Sie stattdessen alle Listen gleichzeitig, fügen Sie den Sätzen Elemente hinzu, und prüfen Sie auf häufig auftretende Ereignisse. So, jetzt, Sie behalten die Geschwindigkeit der Suche nach einer frühen Lösung, aber es ist immer noch langsam für den schlimmsten Fall, dass ich gezeigt habe.

Für die Geschwindigkeiten läuft diese 3-4 mal langsamer als Ihre ersten beiden Lösungen im schlimmsten Fall.Aber läuft 4-10 Mal schneller als diese Lösungen in randomisierten Listen.

Hinweis: Die Tatsache, dass Sie alle gemeinsamen Elemente in drei Listen (in der ersten Lösung) finden, bedeutet ohne Frage, dass es eine schnellere Lösung durch die Theorie gibt. Weil Sie nur wissen müssen wenn gibt es sogar ein einziges gemeinsames Element, und dieses Wissen ist genug.

Answer 2

Die O-Notation ignoriert alle konstanten Faktoren. So wird es nur für unendlich Datensätze antworten. Für jede endliche Menge ist es nur eine Faustregel.

Mit interpretierten Sprachen wie Python und R können konstante Faktoren ziemlich groß sein. Sie müssen viele Objekte erstellen und sammeln, die alle O (1), aber nicht frei sind. Daher ist es leider üblich, 100-fache Leistungsunterschiede von praktisch gleichwertigem Code zu sehen.

, zweitens der erste Algorithmus berechnet alle gemeinsame Elemente, während die anderen auf der ersten scheitern. Wenn Sie Benchmark algX(a,a,a) (ja, alle drei Sätze identisch sein), dann wird es viel mehr Arbeit als die anderen tun!

Ich wäre nicht überrascht, einen sortierten O (n log n) -Algorithmus sehr wettbewerbsfähig zu sehen (weil die Sortierung normalerweise unglaublich gut optimiert ist). Für Integer verwende ich numpy Arrays, und indem man den Python-Interpreter so weit wie möglich vermeidet, kann man sehr schnell werden. Während Numpys in1d und intersect Ihnen wahrscheinlich einen O (n^2) oder O (n^3) Algorithmus geben, können sie am Ende schneller sein, solange Ihre Sätze normalerweise disjunkt sind.

Beachten Sie auch, dass in Ihrem Fall die Sätze nicht unbedingt paarweise disjunkt sein müssen ... algX(set(),a,a)==True.