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
Laufzeit Python / C
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.
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
- User
- Beiträge: 1484
- Registriert: Samstag 21. März 2009, 22:59
- Wohnort: Pfaffenwinkel
list heißt zwar list, ist aber ein dynamisches Array.hendrikS hat geschrieben:Verkettete Listen sind doch der Haus und Hof Datentyp in Python.
Gruß,
Mick.
In specifications, Murphy's Law supersedes Ohm's.
- pillmuncher
- User
- Beiträge: 1484
- Registriert: Samstag 21. März 2009, 22:59
- Wohnort: Pfaffenwinkel
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.Maple99 hat geschrieben: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. ...
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.
In specifications, Murphy's Law supersedes Ohm's.
Ohne deine konkrete Implementierung in C und Python zu kennen: Nein.Maple99 hat geschrieben: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?
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?
[url=http://wiki.python-forum.de/PEP%208%20%28%C3%9Cbersetzung%29]PEP 8[/url] - Quak!
[url=http://tutorial.pocoo.org/index.html]Tutorial in Deutsch[/url]
[url=http://tutorial.pocoo.org/index.html]Tutorial in Deutsch[/url]
- Defnull
- User
- Beiträge: 778
- Registriert: Donnerstag 18. Juni 2009, 22:09
- Wohnort: Göttingen
- Kontaktdaten:
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.
Bottle: Micro Web Framework + Development Blog
Moin,Defnull hat geschrieben:Warum läuft das Anhängen an eine Liste (verkettet oder nicht) überhaupt in quadratischer Zeit?
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
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.Maple99 hat geschrieben:... wenn ich die C-Datenstruktur nehme, die Laufzeit bei größeren Einfügevorgängen deutlich moderater steigt als bei der Python-Struktur.
@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.
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.
Bin erstaunt, dass du immer noch keinen Code gepostet hast.Maple99 hat geschrieben: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.