Was macht "5 in xrange(20)"?

[mutetella]

Hallo,

ich schreibe gerade an einem date(s)picker, über den sich nicht nur ein bestimmtes Datum, sondern auch mehrere Datumskombinationen zusammenstellen lassen.
Möglich kann demnach z. B. sein:

Code: Alles auswählen

In [218]: [[y, m, d] for y in [2010] for m in [6,7] for d in [27,28]]
Out[218]: [[2010, 6, 27], [2010, 6, 28], [2010, 7, 27], [2010, 7, 28]]

Wenn allerdings für 'y', 'm', und/oder 'd' nicht mindestens 1 Wert ausgewählt wurde, werden defaultvalues

Code: Alles auswählen

y = xrange(1,10000)
m = xrange(1,13)
d = xrange(1,32)

angenommen.

Nachdem ich nun nicht weiß, wie xrange intern arbeitet, stehe ich vor der Frage, was wohl (vor allem bei 'y') effektiver ist, wenn ich mit dem 'in'-operator arbeite. Wird bei

Code: Alles auswählen

2010 in xrange(1,10000)

eine Liste erstellt und darin nach 2010 gesucht oder wird geprüft, ob

Code: Alles auswählen

1 < 2010 < 10000

ist?

mutetella

[deets]

letzteres.

[BlackJack]

Wobei das IMHO ein Implementierungsdetail ist.

[sma]

Ein `2010 in xrange(1, 10000)` entspricht einem `1 <= 2010 < 10000`. Man beachte das `<=`. Da das von xrange() erzeugte Objekt offenbar kein __contains__ implementiert, würde ich ebenfalls vermuten, dass die Vergleiche effizienter sind. Unter Python 3.x implement ein range() dann __contains__, da ist es dann vermutlich egal.

Stefan

[mutetella]

Wobei ich inzwischen fast glaube, dass zumindest dann, wenn 'step' angegeben ist, intern wohl jedes Element angeschaut wird. Alles andere wäre zu umständlich.
Ob 'xrange' allerdings abhängig von 'step' vorgeht oder der Einfachheit halber ganz stupide immer eine Liste bemüht, wäre ja mal interessant zu wissen...

@BlackJack:
Ich verstehe nicht wirklich... Gerade dieses Detail interessiert mich ja... Oder willst Du auf etwas anderes hinaus...?

mutetella

[BlackJack]

@mutetella: Ich wollte darauf hinaus, dass man die Frage nur für eine bestimmte Python-Implementierung beantworten kann. Zumindest bei einer Antwort müsste man also die Python-Implementierung und -Version dazu sagen. CPython, IronPython, Jython, und PyPy können da jeweils etwas anderes machen. Und das vielleicht auch noch abhängig von der Version. Im schlimmsten Fall ist `__contains__()` gar nicht implementiert, dann fällt der ``in``-Operator auf ``x in iter(obj)`` zurück. *Schlechter* als das sollte es allerdings nicht sein, es sei denn jemand hat eine ”dümmere” `__contains__()`-Methode implementiert.

Auch bei Angabe des Schritts sollte es effizienter gehen als alles durchzuprobieren.

[sma]

In Python 3 wird nur bei nicht-int und nicht-bool iteriert: http://hg.python.org/cpython/file/44a02 ... ect.c#l602

Stefan

[mutetella]

Dafür bin ich schlichtweg zu dumm...

Wie schaut ein Vergleich/eine Formel aus, mit der ich einen Wert innerhalb eines xrange-Objekts mit 'step' ermitteln (oder nicht) kann? Eine Schleife kann's ja nicht sein, sonst kann man ja gleich das xrange aufbröseln. Oder?

mutetella

[BlackJack]

@mutetella: Steht doch in dem von sma verlinkten Quelltext. Wenn der linke Operand eine Zahl (oder ein `bool`) ist, dann wird `range_contains_long()` aufgerufen: http://hg.python.org/cpython/file/44a02 ... ect.c#l551

Ganz grob wird da erst geprüft ob der Operand innerhalb von start und stop liegt und dann noch ob ``(operand - start % step) == 0`` gilt.

[deets]

Wobei das IMHO ein Implementierungsdetail ist.

Ermja, so wie jede Eigenschaft aller moeglichen builtins. Natuerlich kann irgendwer ein DebilPython implementieren, welches in O(n!) listen sortiert und so weiter. Aber wenn wir hier fuer alles die Implementation + Version in der dritten Nachkommastelle angeben, dann wird's muehsam.

Und gerade xrange ist ja nun aus Effizienzgruenden implementiert worden, wer das also naiv nachimplementiert in welcher anderen Implementation auch immer hat gepennt.

[BlackJack]

@deets: Die Effizienzgründe sehe ich bei `xrange` hautpsächlich beim Speicherverbrauch — es wird nicht extra eine Liste angelegt. Das jemand, zumindest in der Anfangsphase, einfach gar kein `__contains__()` dafür implementiert, würde mich nicht überraschen. Speichereffizient bleibt es ja.

Und unter Python 2.7 hat ein `xrange`-Exemplar kein `__contains__()`! Ist CPython ≤ 3.0 dann DebilPython!? Entweder ist da eine Sonderbehandlung beim Ausführen des ``in``-Operators im Interpreter, oder es ist dort nicht wirklich effizienter gelöst als ``in`` auf Listen.

[deets]

@BlackJack

Ich bin ehrlich gesagt davon ausgegangen, dass es in CPython von vornherein so implementiert war. Darum habe ich deinen Kommentar als spitzfindig empfunden.

[snafu]

Man könnte auch einfach mal einen Blick in die Doku zu range() werfen.

Changed in version 3.2: Implement the Sequence ABC. Support slicing and negative indices. Test integers for membership in constant time instead of iterating through all items.

Da es dokumentiert ist, kann man IMHO davon ausgehen, dass dies für alle Varianten, die Python 3.2 implementieren wollen, gültig ist.

Die Kritk, dass der Zweck des hier nötigen Codes trotzdem klarer wird, wenn man es direkt als Vergleich schreibt, bleibt natürlich trotzdem bestehen. Zumal ich mich momentan nicht auf 3.2 als "Standard-Version" des installierten Interpreters verlassen würde. Da der TE `xrange()` benutzt, kann er sowieso nur Python 2.x meinen.

Und wenn man schon so viel Wert auf Optimierungen legen will/muss, dann würde man den teuren Funktionsaufruf von `range()` doch ohnehin vermeiden wollen, solange dies nicht wirklich erforderlich ist, um das gewünschte Resultat zu erhalten. Weil mehr als Vergleichen kann `range()` letztlich auch nicht.

[mutetella]

Steht doch in dem von sma verlinkten Quelltext.

Als die damals 12jährige Baiba Skride nach Ihrem Violinkonzert gefragt wurde, ob das nicht sehr schwer sei, was sie da gespielt habe, antwortete sie nur: "Wenn man es kann ist es ganz einfach."
Danke für Deine Erklärung. Herauszufinden, dass man ein Vorkommen über '(operand - start % step) == 0' prüfen kann, hätte mich Stunden gekostet...

Die Kritk, dass der Zweck des hier nötigen Codes trotzdem klarer wird, wenn man es direkt als Vergleich schreibt, bleibt natürlich trotzdem bestehen.

[schlauchstehend]Welchen Code meinst Du?[/schlauchstehend]

Ja, ich arbeite hier mit Python 2.6

mutetella

[snafu]

@mutella: Na, du hast doch eingangs folgendes geschrieben:

Code: Alles auswählen

2010 in xrange(1,10000)

Darauf bezog ich mich.