Listen können rechnen O___O?

[BlackVivi]

Inspiriert von diesem Ruby-Beispiel:

Code: Alles auswählen

# Ruby weiß, was du
# meinst, sogar wenn du
# versuchst, einem Array
# Mathestunden zu geben.
cities  = %w[ London
              Oslo
              Paris
              Amsterdam
              Berlin ]
visited = %w[Berlin Oslo]
 
puts "Ich muss noch " +
     "die folgenden " +
     "Städte besuchen:",
     cities - visited

Code: Alles auswählen

class MathList(list):
    """Pythons Listen können zwar nicht von alleine subtrahieren..."""
    
    def __sub__(self, other):
        """Aber es ihnen beizubringen ist nicht schwer!"""
        return MathList(x for x in self if not x in other)
    
a = MathList(("foo", "bar", "foobar"))
print a
b = MathList(("bar", "foobar"))
print b
c = a - b
print c

Los, steinigt meinen unsauberen Quelltext! ^__^

(Übrigens is's nur ein Beispiel, wie schön man von builtins erben kann...)

[BlackJack]

Das liefert dann aber wieder eine Liste die nicht "abziehen" kann. Letztendlich ist das von der Laufzeit her schlecht (``in``-Test auf Listen) und es handelt sich um eine Mengenoperation. Also würde man in Python eher zu `set()` greifen und das kennt ``-``.

Code: Alles auswählen

In [401]: set(('foo', 'bar', 'foobar')) - set(('bar', 'foo'))
Out[401]: set(['foobar'])

[BlackVivi]

Das liefert dann aber wieder eine Liste die nicht "abziehen" kann. Letztendlich ist das von der Laufzeit her schlecht (``in``-Test auf Listen) und es handelt sich um eine Mengenoperation. Also würde man in Python eher zu `set()` greifen und das kennt ``-``.

Code: Alles auswählen

In [401]: set(('foo', 'bar', 'foobar')) - set(('bar', 'foo'))
Out[401]: set(['foobar'])

Manchmal muss man dich hassen >__<

(Nur Spaß ;_;)

[noise]

Das liefert dann aber wieder eine Liste die nicht "abziehen" kann.

Hab ich da was übersehen? In ``__sub__`` gibt er doch wider ein Objekt von Typ `MathList` zurück?

Letztendlich ist das von der Laufzeit her schlecht (``in``-Test auf Listen)

Ne, finde ich nicht. Im Rahmen des machbaren ist es sehr performant. Oder schon mal bei 1000 Objekten mit den in test Probleme gehabt?

Davon abgesehen, wie soll man das sonst realisieren? Letztendlich muss man ja über `self` iterieren und schauen ob die Objekte in `other` vorhanden sind, um bereits vorhanden auszuschließen. Nach mein Verständnis ist das eine Lineare Operation, die selbst im `set` intern nicht anders realisiert ist.

und es handelt sich um eine Mengenoperation.

In wiefern soll das eine Begründung sein? Davon abgesehen sind Sequenzen in Python eine Menge, eine Menge von Objekten.

Also würde man in Python eher zu `set()` greifen und das kennt ``-``.

Finde ich nicht, da bei einem `set` die Reihenfolge verloren geht Die möchte man ja unter Umständen behalten? Bei der Ruby-Lösung bleibt die Reihenfolge z.B: erhalten, was ich praktisch finde.

@BlackVivi:
Ich finde deine Lösung schön. Kurz, kompakt und knackig.

EDIT:

Manchmal muss man dich hassen >__<

(Nur Spaß ;_;)

Warum?

[BlackVivi]

Das liefert dann aber wieder eine Liste die nicht "abziehen" kann.

Hab ich da was übersehen? In ``__sub__`` gibt er doch wider ein Objekt von Typ `MathList` zurück?

Das hab ich vorhin geedit. Das war vorhin noch nicht so... da war'n [] drum ._.

EDIT:

Manchmal muss man dich hassen >__<

(Nur Spaß ;_;)

Warum?

Weil er jedesmal wenn ich einen Quelltext post irgendwas antwortet was viel toller ist. Bin eifersüchtig und so ._.

Aber war ja nur'n Spaß. Ich bewundere ihn viel mehr :3

Danke übrigens. Is' mir nur vorhin auf'r Arbeit so eingefallen, ich mag es von builtins zu erben

[noise]

Weil er jedesmal wenn ich einen Quelltext post irgendwas antwortet was viel toller ist.

Ach so. Naja, diesmal hat er sich aber IMO mit seinen Einwänden geirrt.

Zum set: Klar zu 90% ist einem die Reihenfolge einer Sequenz egal und da kann man auch ein set nutzen, aber es gibt und gab Situationen bei mir wo dem nicht so ist, und da ist definitiv deine Lösung die bessere.

Danke übrigens. Is' mir nur vorhin auf'r Arbeit so eingefallen, ich mag es von builtins zu erben

Ich auch

[Leonidas]

und es handelt sich um eine Mengenoperation.

In wiefern soll das eine Begründung sein? Davon abgesehen sind Sequenzen in Python eine Menge, eine Menge von Objekten.

Naja, in Mengen können identische Objekte nur ein mal vorkommen, in Sequenzen nicht. Somit ist eine Sequenz eigentlich keine Menge.

[birkenfeld]

Letztendlich ist das von der Laufzeit her schlecht (``in``-Test auf Listen)

Ne, finde ich nicht. Im Rahmen des machbaren ist es sehr performant. Oder schon mal bei 1000 Objekten mit den in test Probleme gehabt?

*seufz* Es ist egal, was du da findest, es ist objektiv so, dass die Variante mit Listen schlechteres Laufzeitverhalten als die mit Mengen hat.

Davon abgesehen, wie soll man das sonst realisieren? Letztendlich muss man ja über `self` iterieren und schauen ob die Objekte in `other` vorhanden sind, um bereits vorhanden auszuschließen. Nach mein Verständnis ist das eine Lineare Operation, die selbst im `set` intern nicht anders realisiert ist.

Das Iterieren ist linear, ja. Der Check "if x not in other" ist für Mengen konstant, für Listen allerdings wieder linear -- damit baust du einen quadratischen Algorithmus.

Finde ich nicht, da bei einem `set` die Reihenfolge verloren geht Wink Die möchte man ja unter Umständen behalten? Bei der Ruby-Lösung bleibt die Reihenfolge z.B: erhalten, was ich praktisch finde.

Der zweite Operand muss hierfür keine Liste sein.

Code: Alles auswählen

def minus(a, b):
    b = set(b)
    return [x for x in a if x not in b]

[noise]

@Leonidas:Von der Sicht betrachtet hast du selbstverständlich recht.

*seufz* Es ist egal, was du da findest, es ist objektiv so, dass die Variante mit Listen schlechteres Laufzeitverhalten als die mit Mengen hat.

Habe ich was anderes Behauptet? Ich hab nicht geschrieben das `list`\s eine besseres Laufzeitverhalten haben als `set`\s. Ich habe lediglich geschrieben das es IMHO trotz seines Arguments performant genug ist und die Iteration in beiden Fällen linear ist. Zu dem ``f x not in other`` test siehe unten.

Das Iterieren ist linear, ja. Der Check "if x not in other" ist für Mengen konstant, für Listen allerdings wieder linear -- damit baust du einen quadratischen Algorithmus.

Ups, stimmt, mein Fehler. Der ``if x not in other`` test ist auch linear, da in ``other`` jedes Element mit ``x`` verglichen wird bis eine Übereinstimung gefunden wurde. -- Das habe ich übersehen.

Das der ``in`` test von einem `set` Konstant ist wusste ich nicht. Ich hab gerade nochmal in der Dokumentation geschaut und da steht das für die Implementation des `set`\s ein `dict` benutzt wird, dessen lookup ja auch Konstant ist.

Der zweite Operand muss hierfür keine Liste sein.

Code: Alles auswählen

def minus(a, b):
    b = set(b)
    return [x for x in a if x not in b]

So, bis hier hin gebe ich dir absolut Recht, aber dieser Vorschlag grenz jetzt an Lächerlichkeit.


1. Gerade weil ein `set` ein `dict`für die Verbesserung des lookups nutzt, können nur imutables benutzt werden:

Code: Alles auswählen

>>> set([1, 2, 3])
set([1, 2, 3])
>>> set([1, 2, [3]])

Traceback (most recent call last):
  File "<pyshell#1>", line 1, in <module>
    set([1, 2, [3]])
TypeError: list objects are unhashable
>>> 

2. Wenn ich deinen Vorschlag richtig interpretiere willst du sagen, dass man bei jeden Code der ``if x in other`` benutzt, immer ``other`` erst in ein `set` umwandeln sollte. Dein Vorschlag kann ich nicht generell empfehlen weil dein Code bei imutablen Elementen nicht funktioniert.

In allen andere fällen wo man 100% ausschließen kann das ``other`` imutables beinhaltet, ist das natürlich okay. Aber, hmm, da frage ich mich ob man es nicht etwas mit der voreiligen Optimierung übertreibt? Siehe dazu auch 3.

3. http://en.wikipedia.org/wiki/Optimizati ... ce)#Quotes

The First Rule of Program Optimization: Don't do it. The Second Rule of Program Optimization (for experts only!): Don't do it yet.

[birkenfeld]

Das der ``in`` test von einem `set` Konstant ist wusste ich nicht. Ich hab gerade nochmal in der Dokumentation geschaut und da steht das für die Implementation des `set`\s ein `dict` benutzt wird, dessen lookup ja auch Konstant ist.

Inzwischen nicht mehr -- die Sets sind eigenständige Objekte. Nur der Lookupmechanismus funktioniert natürlich nach demselben Prinzip.

Der zweite Operand muss hierfür keine Liste sein.

Code: Alles auswählen

def minus(a, b):
    b = set(b)
    return [x for x in a if x not in b]

So, bis hier hin gebe ich dir absolut Recht, aber dieser Vorschlag grenz jetzt an Lächerlichkeit.[/quote]
Warum? Für große Datenmengen ist das durchaus angebracht.

1. Gerade weil ein `set` ein `dict`für die Verbesserung des lookups nutzt, können nur imutables benutzt werden:

Das stimmt, das hätte ich dazuschreiben müssen.

2. Wenn ich deinen Vorschlag richtig interpretiere willst du sagen, dass man bei jeden Code der ``if x in other`` benutzt, immer ``other`` erst in ein `set` umwandeln sollte. Dein Vorschlag kann ich nicht generell empfehlen weil dein Code bei imutablen Elementen nicht funktioniert.

Nein, das will ich nicht sagen. Wenn du den contains-Test nur einmal durchführst, ist das auch sinnlos. Wenn du allerdings einen contains-Test n-mal mit demselben Operanden durchführst, ist das eine Überlegung wert.

3. http://en.wikipedia.org/wiki/Optimizati ... ce)#Quotes

The First Rule of Program Optimization: Don't do it. The Second Rule of Program Optimization (for experts only!): Don't do it yet.

Einen Algorithmus in angemessener Komplexität zu schreiben, halte ich nicht für Optimierung, sondern gesunden Programmiererverstand.

[mitsuhiko]

Zusätzlich hat das nix mit immutable oder nicht zu tun. Auch mutables können hashable sein.