Warum halbiert langsamer als Sortierung

Question

Ich weiß, dass Halbakt binäre Suche verwendet, um Listen sortiert zu halten. Allerdings habe ich einen Timing-Test gemacht, dass die Werte gelesen und sortiert werden. Aber im Gegensatz zu meinem Wissen, die Werte zu behalten und sie dann zu sortieren, gewinnt das Timing durch einen hohen Unterschied. Könnten mehr erfahrene Benutzer dieses Verhalten erklären? Hier ist der Code, den ich verwende, um die Timings zu testen.

import timeit 

setup = """ 
import random 
import bisect 
a = range(100000) 
random.shuffle(a) 
""" 

p1 = """ 
b = [] 
for i in a: 
    b.append(i) 
b.sort() 
""" 

p2 = """ 
b = [] 
for i in a: 
    bisect.insort(b, i) 
""" 

print timeit.timeit(p1, setup=setup, number = 1) 
print timeit.timeit(p2, setup=setup, number = 1) 

# 0.0593081859178 
# 1.69218442959 
# Huge difference ! 35x faster. 

Im ersten Prozess nehme ich Werte one-by-one, anstatt nur a Sortierung ein Verhalten wie Datei-Lesen zu erhalten. Und es schlägt sehr schwer.

Answer 1

Ihre algorithmische Komplexität schlechter im bisect Fall sein wird ...

Im bisect Fall haben Sie N Operationen (jeweils bei durchschnittlich Kosten von log(N) die Einfügemarke zu finden und dann einem zusätzlicher O(N) Schritt den Artikel einfügen). Gesamtkomplexität: O(N^2).

Mit sort haben Sie einen einzigen Nlog(N) Schritt (plus NO(1) Schritte, um die Liste an erster Stelle zu bauen). Gesamtkomplexität: O(Nlog(N))

Beachten Sie auch, dass sort in sehr stark optimierten C-Code implementiert ist (bisect ist nicht ganz so optimiert, da es verschiedene Vergleichsfunktionen viel häufiger ... Aufruf endet)

Answer 2

Sortierung eine Liste dauert etwa O(N*log(N)) Zeit. Das Anhängen von N Elementen an eine Liste dauert O(N). Diese Dinge nacheinander zu tun dauert etwa O(N*log(N)) Zeit.

Eine Liste zu zweit dauert O(log(n)) Zeit. Das Einfügen eines Elements in eine Liste dauert O(N). Wenn Sie beide Male innerhalb einer for-Schleife arbeiten, dauert die Zeit O(N * (N + log(n))) == O(N^2).

O(N^2) ist schlechter als O(N*log(N)), so dass Ihre p1 schneller ist als Ihre p2.

Answer 3

Um den Zeitunterschied zu verstehen, schauen wir uns an, was Sie da eigentlich machen.

In Ihrem ersten Beispiel nehmen Sie eine leere Liste und fügen Sie Elemente an, und sortieren sie am Ende.

Anhängen an Listen ist wirklich billig, es hat eine amortized time complexity von O (1). Es kann keine wirklich konstante Zeit sein, da die zugrunde liegende Datenstruktur, ein einfaches Array, eventuell erweitert werden muss, wenn die Liste wächst. Dies wird gelegentlich durchgeführt, wodurch ein neues Array zugewiesen und die Daten kopiert werden. Das ist ein bisschen teurer. Aber im Allgemeinen we still say this is O(1).

Als nächstes kommt die Sortierung. Python verwendet Timsort, was sehr effizient ist. Dies ist O (n log n) im Durchschnitt und im schlimmsten Fall. Insgesamt erhalten wir konstante Zeit nach O(n log n), so dass die Sortierung das einzige ist, was hier zählt. Insgesamt ist das ziemlich einfach und sehr schnell.

Das zweite Beispiel verwendet bisect.insort. Dies verwendet eine Liste und binäre Suche, um sicherzustellen, dass die Liste immer sortiert ist.

Im Wesentlichen wird bei jeder Einfügung die binäre Suche verwendet, um die korrekte Position zum Einfügen des neuen Werts zu finden, und dann werden alle Elemente korrekt verschoben, um Platz für diesen Index für den neuen Wert zu schaffen. Binäre Suche ist billig, O (log n) im Durchschnitt, das ist also kein Problem. Alleine zu wechseln ist auch nicht so schwierig. Im schlimmsten Fall müssen wir alle Elemente um einen Index nach rechts verschieben, also erhalten wir O (n) (das ist im Grunde die insert operation on lists).

Also würden wir im schlimmsten Fall lineare Zeit bekommen. Wir tun dies jedoch auf jeder einzelnen Iteration. Wenn wir n Elemente einfügen, haben wir jedesmal O (n). Dies führt zu einer quadratischen Komplexität O (n²). Das ist ein Problem und wird das Ganze letztendlich verlangsamen.

Was sagt uns das? Sorted inserting in eine Liste, um ein sortiertes Ergebnis zu bekommen, ist nicht wirklich performant. Wir können das bisect-Modul verwenden, um eine bereits sortierte Liste geordnet zu halten, wenn wir nur ein paar Operationen durchführen, aber wenn wir tatsächlich unsortierte Daten haben, ist es einfacher, die Daten als Ganzes zu sortieren.

Answer 4

Einfüge- und Löschvorgänge in einer Datenstruktur können manchmal überraschend teuer sein, insbesondere wenn die Verteilung der eingehenden Datenwerte zufällig ist. Hingegen, Sortieren kann unerwartet schnell sein.

Eine wichtige Überlegung ist, ob oder nicht Sie können alle Werte akkumulieren, dann sortieren sie einmal, dann verwenden Sie das sortierte Ergebnis "alle gleichzeitig." Wenn Sie können, ist das Sortieren fast immer merklich schneller.

Wenn Sie den alten Science-Fiction-Film (zurück, wenn Computer genannt wurden „Riesen-Köpfe“ und ein Film immer hatte Band-Laufwerke Spinnen) erinnern, das ist die Art von Verarbeitung, die sie angeblich tun: Anwendung sortierte Updates zu auch sortierte Master-Bänder, um eine neue noch sortierten Master zu produzieren. Random-Access wurde nicht benötigt. (Was eine gute Sache war, weil wir es damals wirklich nicht konnten.) Es ist immer noch eine effiziente Möglichkeit, große Datenmengen zu verarbeiten.