Werte aus einer Liste zusammenfassen

[Sirius3]

@Xeike: es ging snafu darum, den schnellsten Code zu finden, und ein Vergleich ist nunmal schneller als ein Funktionsaufruf.

[snafu]

@xeike: Abgesehen von der schlechten Laufzeit deiner `.remove()`-Methode: Was passiert wohl, wenn jemand die Listenelemente über Indexzugriff via `del` löscht (`del posliste[42]`)? Oder wenn man Elemente mit `.extend()` anfügen möchte? Ingesamt wird das in einer total komplexen Implementierung enden, wenn man alles, was `list` kann, in einer eigenen Klasse umsetzen möchte. Wieder mal ein schönes Beispiel, warum es meistens keine so gute Idee ist, von "fremden" Klassen zu erben - Mixins, abstrakte Klassen bzw generell welche, wo Vererbung explizit erlaubt / vorgesehen ist, mal ausgenommen.

[snafu]

Bezüglich `min(x, y)` vs. `if x < y:`: Ja, es ist lesbarer, leichter zu schreiben und im Grunde auch weniger fehleranfällig, wenn man eine fertige Funktion nimmt. Ich habe das nur so gemacht, weil 1 Million Vergleiche nunmal schneller sind, als 1 Million Funktionsaufrufe, wo der Vergleich dann auch nochmal gemacht werden muss. Gerade CPython glänzt nicht gerade dabei, wenn Funktionen *sehr häufig* aufgerufen werden müssen, da diesbezüglich keine Optimierung (z.B. durch Inlining) stattfindet und die zusätzliche Arbeit, die intern hinter Funktionsaufrufen steckt, in der Summe (also bei vielen Wiederholungen) eben spürbar ins Gewicht fallen kann. Wohlgemerkt, das bezieht sich jetzt nur auf Funktionsaufrufe in Schleifen, wo potenziell mit vielen Aufrufen gerechnet werden muss. Und den Fall haben wir hier IMHO.

[BlackJack]

@snafu: Echt? Das war eine Liste mit drei `Pos`-Objekten. Lass es ein paar mehr in der tatsächlichen Anwendung sein. Solange kein messbares Problem vorliegt, würde ich erst einmal mit einer einfacheren, kürzeren Variante arbeiten.

[snafu]

@BlackJack: Gut, man kann jetzt mit dem Argument kommen, dass es sich um verfrühte Optimierungen handelt. Falls man den Code nur für den internen Gebrauch schreibt und sicher ist, dass man es nur mit überschaubaren Mengen an Positionsobjekten zu tun bekommen wird, dann ist man mit `min()` / `max()` sicherlich besser beraten. Es kommt auf den konkreten Anwendungsfall an. Als allgemein zugängliche Bibliotheksfunktion würde ich persönlich das jedenfalls nicht so schreiben.

[BlackJack]

@snafu: Du würdest allgemeine Bibliotheksfunktionen immer so optimieren das sie mit Millionen von Objekten schnell (was auch immer das bedeutet) laufen, bezogen auf eine CPython-Implementierung? In dem Fall würde ich ja ein C-Modul vorschlagen, damit da nicht so furchtbar langsamer Python-Bytecode ausgeführt werden muss.

[xeike]

@xeike: Abgesehen von der schlechten Laufzeit deiner `.remove()`-Methode: Was passiert wohl, wenn jemand die Listenelemente über Indexzugriff via `del` löscht (`del posliste[42]`)? .... Wieder mal ein schönes Beispiel, warum es meistens keine so gute Idee ist, von "fremden" Klassen zu erben - Mixins, abstrakte Klassen bzw generell welche, wo Vererbung explizit erlaubt / vorgesehen ist, mal ausgenommen.

Selbstverständlich hat es unbestreitbare Nachteile. Allerdings hat diese Klasse eben auch den Vorteil, zusammen mit meinem ersten Versuch, dass ein Einfügen unmittelbar min und max updatet. Beschränken wir uns nur auf den Aufbau der Liste (ohne remove, del, slices, etc), dann ist diese Lösung verdammt gut in dem Sinne, dass O(1) beim Einfügen (jeweils) und Auslesen gegen O(n) beim Auslesen der anderen Varianten steht. Man erhält hier min und max ganz billlig. Die Listen muss man ja eh aufbauen.

Durch die Klasse bekommt man automatisch etwas Overhead. Mit folgendem Beispiel (gerne zum Rumspielen gedacht )
möchte ich das mal verdeutlichen. Den Fall, dass man den Aufbau der Liste mit hineinbaut, habe ich auch mal durchgespielt. Und da schneide ich trotz Verwendung einer Klasse nicht so schlecht ab, was die Laufzeit anbelangt:

Code: Alles auswählen

#!/usr/bin/env python3

from collections import namedtuple
from itertools import islice
import time

Pos = namedtuple('Pos', 'start, end')

def get_total(positions):
    if not positions:
        raise ValueError('need at least one position')
    min_start, max_end = positions[0].start, positions[0].end
    for pos in islice(positions, 1, len(positions)):
        if pos.start < min_start:
            min_start = pos.start
        if pos.end > max_end:
            max_end = pos.end
    return Pos(min_start, max_end)

def total_xe(liste):
    min, max = liste[0]
    for s1, s2  in liste:
        if s1 < min:
            min = s1
        if s2 > max:
            max = s2
    return Pos(min, max)

class PosListe:
    def __init__(self):
        self.pliste = []
        self.min = None
        self.max = None

    def append(self, pos):
        if self.min:
            self.min = min(pos.start, self.min)
            self.max = max(pos.end, self.max)
        else:
            self.min = pos.start
            self.max = pos.end

    def __str__(self):
        return '{0};{1}'.format(self.min, self.max)

if __name__ == '__main__':
    punkte = [Pos(a, b) for a in range(1000, 2000) for b in range(1000)]
    punkte2 = [Pos(a, b) for a in range(2000, 3000) for b in range(1000)]
    punkte3 = [Pos(a, b) for a in range(3000, 4000) for b in range(1000)]
    pL = PosListe()
    for p in punkte3:
        pL.append( p )

    # get_total()
    t1 = time.perf_counter()
    print(get_total(punkte))
    # total_xe
    t2 = time.perf_counter()
    print(total_xe(punkte2))
    # Mit Klasse
    t3 = time.perf_counter()
    print(pL)
    t4 = time.perf_counter()

    # Auswertung
    print(t2-t1)
    print(t3-t2)
    print(t4-t3)

Xe

[snafu]

@snafu: Du würdest allgemeine Bibliotheksfunktionen immer so optimieren das sie mit Millionen von Objekten schnell (was auch immer das bedeutet) laufen, bezogen auf eine CPython-Implementierung? In dem Fall würde ich ja ein C-Modul vorschlagen, damit da nicht so furchtbar langsamer Python-Bytecode ausgeführt werden muss.

Wenn ich durch etwas aufwändigeren Python-Code schon ein merklich besseres Laufzeitverhalten hinbekomme, dann muss ich nicht gleich zu C greifen. Falls eine Situation kommt, wo der optimierte Python-Code nicht mehr ausreicht, würde ich als nächste Stufe erstmal PyPy in Erwägung ziehen. Und erst wenn das nicht mehr ausreicht, dann C.

Du musst übrigens nicht gleich polemisch werden. Ich habe keinesfalls gesagt, dass ich "allgemeine Bibliotheksfunktionen immer so optimieren" würde, dass sie in jeder theoretisch denkbaren Situation die perfekte Laufzeit haben. Ich habe, so meine ich, ganz gut verdeutlicht, dass man solcherlei Optimierungen nur dann durchführen sollte, wenn man (realistischerweise) mit großen Eingabemengen rechnen muss. Der Unterschied ist jetzt nur, dass du hier offenbar keine großen Eingabemengen erwarten würdest - ich jedoch schon.

Ich wollte aber auch überhaupt niemanden "zwingen", meinen Ansatz von vornherein zu verwenden, falls das so rüberkam. Den Einwurf im Hinterkopf zu behalten, kann jedoch nicht schaden.

[snafu]

@xeike: Du misst bei den anderen Algos den kompletten Ablauf, während du für deine eigene Klasse lediglich die Zeit für die formatierte Ausgabe misst, wo die Klasseninstanz bereits alle nötigen Berechnungen vollzogen hat. Das ist eindeutig nicht vergleichbar.

[xeike]

@xeike: Du misst bei den anderen Algos den kompletten Ablauf, während du für deine eigene Klasse lediglich die Zeit für die formatierte Ausgabe misst, wo die Klasseninstanz bereits alle nötigen Berechnungen vollzogen hat. Das ist eindeutig nicht vergleichbar.

Ich messe bei allen Varianten die Zeit die es braucht, um (min, max) herauszubekommen, nachdem die Liste aufgebaut ist. Dass das bei der Klassenvariante eben nur ein simpler Aufruf ist, ist ja gerade der Trick an der Lösung. Dafür kostet mich der Klassen- und append()-Overhead mehr.

Übrigens scheint von den bisherigen Funktionslösungen total_xe() die schnellste zu sein, oder?

Xe

[Sirius3]

@xeike: Preisfrage: Warum ist »total_xe« doppelt so schnell wie »get_total«?

Im übrigen braucht das Aufbauen von »PosListe« 30mal so lange wie das nachträgliche durchgehen einer fertigen Liste. Es ist fast immer besser, sich die Arbeit erst dann zu machen, wenn sie tatsächlich gebraucht wird, anstatt an vielen Stellen ein stückchen der Arbeit zu erledigen.

[BlackJack]

@xeike: Nein das misst Du nicht, denn um min und max heraus zu bekommen musst Du auch den Code messen der das tatsächlich tut. Die Attribute füllen sich ja nicht auf magische Weise mit den Werten. Deine Messung ist so einfach nicht vergleichbar.

[xeike]

@xeike: Nein das misst Du nicht, denn um min und max heraus zu bekommen musst Du auch den Code messen der das tatsächlich tut. Die Attribute füllen sich ja nicht auf magische Weise mit den Werten. Deine Messung ist so einfach nicht vergleichbar.

Wenn ich eine sortierte Liste habe, sagen wir

Code: Alles auswählen

meine_liste = [1, 2, 3]

, dann kann ich mit

Code: Alles auswählen

meine_liste[0]

das kleinste Element herausbekommen. Dass diese Liste nebenbei sortiert ist, ist eine schöne Sache, aber die Laufzeit, die ich benötige, um das kleinste Element aus dieser Liste zu bestimmen ist eben die Laufzeit von

Code: Alles auswählen

meine_liste[0]

.

Ansonsten kann ich auch noch die Gesamtlaufzeit zum Aufbau der Liste, Sortieren und Minimumbestimmung zählen. Je nach dem, was ich angeben möchte, ist das ja auch ganz sinnvoll.

Tatsächlich komme ich gerade mit ein paar "Tricks" in meiner Gesamtlaufzeit (Aufbau der Liste,...,Minimumbestimmung) unter die Zeit der beiden anderen Varianten... was mich irgendwie stutzig macht.

Edit:

Code: Alles auswählen

class PosListe:
    def __init__(self):
        self.pliste = []
        self.min = float('inf')
        self.max = float('-inf')

    def append(self, pos):
        if pos.start < self.min:
            self.min = pos.start
        if pos.end > self.max:
            self.max = pos.end
        # Edit2: hinzugefügt *facepalm*
        self.pliste.append( pos )


    def get_min_point(self):
        return Pos(self.min, self.max)

    def __str__(self):
        return '{0};{1}'.format(self.min, self.max)

Mit dem float()-Aufruf erspare ich mir ein if...else im Aufbau der Liste.

Und gemessen mit:

Code: Alles auswählen

# Mit Klasse
    t3 = time.perf_counter()
    pL = PosListe()
    for a in range(3000, 4000):
        for b in range(1000):
            pL.append(Pos(a, b))
    print(pL.get_min_point())
    t4 = time.perf_counter()

Edit2:
... Weil ich in der Klasse in der Methode append() das eigentliche "append()" vergesse.... Danke fürs Schweigen und wo ist der Facepalm-Smilie Jetzt ist die Welt wieder in Ordnung.


Xe

[BlackJack]

@xeike: Mit dieser Argumentation bekommt man jedes Ergebnis, egal wie Rechenaufwändig es ist, in O(1) hin — wenn man einfach nur den Schritt das bereits berechnete Ergebnis auszulesen betrachtet. *Das* dann aber mit anderen Algorithmen zu vergleichen und dort die komplette Berechnung zu betrachten ist unredlich. Du vergleichst da Äpfel mit Birnen. Was Du angeben willst sind extrem zu Deinen Gunsten verzerrte Messwerte. Dann ist das natürlich sinnvoll das so zu machen. Für einen sinnvollen Laufzeitvergleich aber nicht.

Zur letzten Messergebnis: Gib mal den Inhalt Deiner `PosListe` aus, nach dem sie „aufgebaut” wurde.

[xeike]

Ja, ich habe meinen Fehler gesehen und korrigiert (Edit2).

Jetzt messe ich gerade nochmal mit einer deutlich größeren Liste nach... und erhalte Ergebnisse, die eher passen. Bei 2000*2000 Elementen bin ich mit der Klasse und der Gesamtlösung nur halb so gut. Mit größer werdender Liste weichen die Ergebnisse von get_total() und total_xe() (beide ohne min()- und max()-Funktion) immer weniger voneinander ab. Also, trotzdem, gar nicht so schlecht...

Man muss nur häufig genug min und max abfragen, damit sich die Klassenlösung lohnt

Xe