Laufzeit Python / C

[Maple99]

Hi,
ich würde gerne mal wissen was ihr zu dem Verhalten meint. Ich habe eine Listenstruktur (einfach verkettet) in C geschrieben (eine Klasse), die Ints aufnimmt. Diese habe ich dann 1:1 (soweit möglich) in Python nachgebaut. Ich war mir natürlich im Klaren darüber das die Python-Geschichte langsamer sein wird, allerdings bin ich doch etwas geschockt. Das Anhängen(hinten) in der C-Struktur läuft in exponentieller (quadratischer) Zeit zur Länge. Bei 3000 mal Anhängen ist die C-Struktur ca. 20 x schneller als das Python-Konstrukt. Erhöhe ich jetzt aber immer weiter die Anhängeanzahl steigt die Zeit, die Python benötigt, nicht quadratisch, sondern wesentlich mit höherem Exponenten. In C bleibt es O^2.
Ich zweifle gerade etwas an den Zahlen, aber vielleicht ist es auch einfach schon zu spät. Kann jemand vielleicht die Zahlen nachvollziehen und vielleicht auch erklären?

Gruß

Jonny

[hendrikS]

Als ich das gelesen habe, habe ich mich gefragt was Du da in Python nachgebaut hast? Verkettete Listen sind doch der Haus und Hof Datentyp in Python. Die muß man nicht nachbauen.
Die Geschwindigkeitsunterschiede zwischen C und Python variieren ziemlich stark. Manchmal habe ich das Gefühl es ist vielleicht 7 oder 8 und manchmal 20.

[pillmuncher]

Verkettete Listen sind doch der Haus und Hof Datentyp in Python.

list heißt zwar list, ist aber ein dynamisches Array.

Gruß,
Mick.

[pillmuncher]

Ich habe eine Listenstruktur (einfach verkettet) in C geschrieben (eine Klasse), die Ints aufnimmt. Diese habe ich dann 1:1 (soweit möglich) in Python nachgebaut. Ich war mir natürlich im Klaren darüber das die Python-Geschichte langsamer sein wird, allerdings bin ich doch etwas geschockt. ...

Ich nicht. Bei solcherlei micro-benchmarking wird Python immer verlieren. Python glänzt dafür an anderer Stelle mit Geschwindigkeit, zB. beim Schreiben von Code. Programmierzeit ist teurer als Maschinenzeit. Da die Zeit, die es braucht, um ein Programm zu schreiben, im wesentlichen proportional zur Größe des Programms ist (in lines of code), und da man im Vergleich zu Python in C 5-20x soviel locs braucht, um dasselbe zu erreichen, ist ein solches C-Programm auch 5-20x so teuer wie ein vergleichbares Python-Programm, vorausgesetzt der Python-Programmierer verdient dasselbe wie der C-Programmierer. Es gibt Anwendungsbereiche wo diese Ausgabe sinnvoll ist, aber in den meisten Fällen ist sie es nicht. Ein hinreichend komplexes Programm vorausgesetzt, könnte man für dasselbe Geld vermutlich einen ganzen Rechnerpark hinstellen, dann könnte man auch mit einer "langsamen" Python-Lösung bequem leben.

Idiomatisches Python ist auch gar nicht langsam. Die meisten Operationen auf list-Objekten sind O(1), und man braucht im täglichen Python-Geschäft kaum verkettete Listen. Man müsste daher eher dynamische Arrays in C und Python vergleichen. Da wäre der Unterschied vermutlich kleiner.

Außerdem kann man auf höherer Ebene optimieren, wenn man higher level programmiert. Generatoren fallen mir da ein, die Datenstrukturen erst gar nicht komplett aufbauen. Damit kann man zB. generate-and-test-Prozeduren effizient implementieren, ohne sich um das Abspeichern und Wiederherstellen komplexer Datenstrukturen kümmern zu müssen, was in C nicht nur einiges an Programmieraufwand benötigen würde, sondern sich, problembedingt, wohl dem Zeitbedarf in Python annähern würde.

Gruß,
Mick.

[Darii]

Ich zweifle gerade etwas an den Zahlen, aber vielleicht ist es auch einfach schon zu spät. Kann jemand vielleicht die Zahlen nachvollziehen und vielleicht auch erklären?

Ohne deine konkrete Implementierung in C und Python zu kennen: Nein.

[jbs]

Ich denke Maple99 wollte wissen, warum die Zeit nicht quadratisch ansteigt und nicht wo die Vorteile von Python liegen, oder sehe ich da etwas falsch?

[Defnull]

Warum läuft das Anhängen an eine Liste (verkettet oder nicht) überhaupt in quadratischer Zeit? Wofür? Anhängen an Listen ist O(1) bis O(n) je nach dem ob noch Platz im Speicher ist oder Neuer allokiert werden muss.

[Maple99]

Warum läuft das Anhängen an eine Liste (verkettet oder nicht) überhaupt in quadratischer Zeit?

Moin,
du hast Recht. Die Komplexität ist natürlich O(n) für das Anhängen an verketteten Listen. O(1) habe ich natürlich nur wenn ich vorne anhänge.
Was ich beobachtet hatte ich das sich wenn ich 1000 Element einfüge im Vergleich zu 10000 sich die Zeit, die der gesamte Anhängevorgang benötigt, sich verhundertfacht und nicht verzehnfacht.
Mir ist duchaus bewusst das es in Python schon Listen gibt. Es ging einzig und allein darum einen Vergleich zwischen Datenstrukturen, die man sich in Python neu baut und welchen, die man selbstverständlich dann mit mehr Aufwand in C erstellt.
Diesen Vergleich wird C natürlich immer gewinnen. Ich war nur etwas erstaunt das es so deutlich ausgeht und das ich, wenn ich die C-Datenstruktur nehme, die Laufzeit bei größeren Einfügevorgängen deutlich moderater steigt als bei der Python-Struktur.

Gruß

Jonny

[hendrikS]

... wenn ich die C-Datenstruktur nehme, die Laufzeit bei größeren Einfügevorgängen deutlich moderater steigt als bei der Python-Struktur.

Es hängt sicherlich auch davon ab wie die Listen implementiert sind. Wie pillmuncher festgestellt hat, sind die Listen in Python keine richtig verketteten Listen. Dann könnte ich mir zumindest vorstellen, dass del, insert und remove Operationen laufzeitproblematisch sind. Aber so genau weiss ich es nicht. Müsste man mal testen. Poste doch mal Deinen Code oder Schnipsel.

[BlackJack]

@Maple99: Ein wenig Quelltext wäre vielleicht wirklich nicht schlecht, damit wir wissen, was hier überhaupt verglichen wird.

Vom Lesen Deiner Beiträge bekomme ich zum Beispiel den Eindruck, dass Du Dir mindestens in der C-Implementierung keinen Zeiger auf das letzte Element behältst und *einmal* Anhängen tatsächlich O(n) Zeit benötigt, mit n = Länge der Liste!? Dann wäre die die Laufzeit für das Einfügen von k Elementen tatsächlich O(k²), also quadratisch. Aber dann wäre der Vergleich auch für die Tonne, weil man so was, äh, *Ungünstiges*, hoffentlich nie in echten Programmen machen würde.

[Darii]

Diesen Vergleich wird C natürlich immer gewinnen. Ich war nur etwas erstaunt das es so deutlich ausgeht und das ich, wenn ich die C-Datenstruktur nehme, die Laufzeit bei größeren Einfügevorgängen deutlich moderater steigt als bei der Python-Struktur.

Bin erstaunt, dass du immer noch keinen Code gepostet hast.