xrange für longs

Code-Stücke können hier veröffentlicht werden.
Milan
User
Beiträge: 1078
Registriert: Mittwoch 16. Oktober 2002, 20:52

Mittwoch 17. März 2004, 16:48

Hi. Ich hab einem meiner letzten scripte eine eigentlich absolute Ausnahme gehabt: ich hab ein Iterator für sehr große Zahlen gebraucht, wo xrange leider versagt (C-Datentypen dürfen halt nur eine gewisse Größe haben). Deswegen musste ich leider auf den Geschwindigkeitsvorteil verzichten und mir selbst was schreibseln:

für Pythonversionen >= 2.3 :

Code: Alles auswählen

def xlrange(start,stop=None,step=1):
    """xlrange([start=0,]stop[,step=1]) --> iterator object like xrange for longs"""
    if stop==None:
        stop=start
        start=0
    if step>0:
        while start<stop:
            yield start
            start+=step
    elif step<0:
        while start>stop:
            yield start
            start+=step
    else:
        raise ValueError, "xlrange() arg 3 (step) must not be zero"
für alle Pythonversionen von 2.2 :

Code: Alles auswählen

class xlrange:
    """xlrange([start=0,]stop[,step=1]) --> iterator object like xrange for longs"""
    def __init__(self,start,stop=None,step=1):
        if stop==None:
            stop=start
            start=0
        self.start,self.stop,self.step=start,stop,step
        if step>0:
            self.is_next=lambda :self.start<self.stop
        elif step<0:
            self.is_next=lambda :self.start>self.stop
        else:
            raise ValueError, "xlrange() arg 3 (step) must not be zero"
    def __iter__(self):
        return self
    def next(self):
        if self.is_next():
            i=self.start
            self.start+=self.step
            return i
        else:
            raise StopIteration
Milan
Zuletzt geändert von Milan am Mittwoch 15. Dezember 2004, 20:20, insgesamt 1-mal geändert.
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Mittwoch 15. Dezember 2004, 20:13

Hi Milan,

ich hab gerade dein xrange für Longs gebraucht, und dabei sind mir 2 Verbesserungen eingefallen:

1. Name statt myxrange - xlrange
2. Bei der Exception, wenn versucht wird ein xlrange-Objekt mit step = 0 zu erzeugen, könnte die Fehlermeldung xlrange() arg 3 must not be zero lauten, dann wärs gleich wie bei xrange.


Gruß

Dookie
[code]#!/usr/bin/env python
import this[/code]
Milan
User
Beiträge: 1078
Registriert: Mittwoch 16. Oktober 2002, 20:52

Mittwoch 15. Dezember 2004, 20:17

Hi. Angenommen :wink: Aber step lass ich trotzdem stehen, da stellt man sich eher was drunter vor als unter "arg 3", auch wenn das normale xrange da andere Wege geht... :roll:
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Donnerstag 16. Dezember 2004, 13:23

Das könnte man doch in die Python-dev posten, oder gleich als Patch einsenden. Ich finds sehr nützlich.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
jens
Moderator
Beiträge: 8461
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Donnerstag 16. Dezember 2004, 13:25

Milan hat geschrieben:ich hab ein Iterator für sehr große Zahlen gebraucht, wo xrange leider versagt (C-Datentypen dürfen halt nur eine gewisse Größe haben)
Ab wann trifft das eigentlich ein?
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Donnerstag 16. Dezember 2004, 14:06

Ich glaube ein int bleibt ein long int bis 2147483647, ab 2147483648 ist es ein long int (long).

Wie ich auf diese Zahl komme? Das ist 2**31 -1, bzw 2**31.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
jens
Moderator
Beiträge: 8461
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Donnerstag 16. Dezember 2004, 14:10

Nochwas zum tuning... Man könnte doch abfragen, ob der Bereich überhaupt im long int Betreich liegt und wenn nicht, wird einfach das normale xrange() benutzt...

Mal angenommen, man will einen Wertebereich zwischen 2147483647 und 2147483747 haben... (also 100-Schritte) könnte man dann nicht auch eigentlich xrange() benutzen, nur die Ergebnisse immer +2147483647 addieren? Wenn das überhaupt geht...

Also ich meine, das das direkt eingebaut wird. Somit kann man generell xlrange() benutzen, obwohl es nicht immer notwendig währe...
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Donnerstag 16. Dezember 2004, 14:33

Stimmt. Würd' ich gerne im standard Python sehen, am besten als ein xrange, dass auch mit longs zurechtkommt.

Wie/wo ist eigentlich xrange in Python implementiert? Wenn es in Python ist, was ich aber eher bezweifle ist es eine Sache von einem Patch ;)
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
jens
Moderator
Beiträge: 8461
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Donnerstag 16. Dezember 2004, 14:41

Hier steht's:
http://www.python.org/doc/lib/built-in- ... tml#l2h-77
Note: xrange() is intended to be simple and fast. Implementations may impose restrictions to achieve this. The C implementation of Python restricts all arguments to native C longs ("short" Python integers), and also requires that the number of elements fit in a native C long.
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Donnerstag 16. Dezember 2004, 14:56

Ich wollt grad noch ins CVS schaun, aber das will jetzt nicht.

Naja, man kann es immernoch als Python Version, xlrange, hinzufügen. Ich denke, dass da schon einiges an Interesse da wäre, vor allem wenn man es noch tunt. Wie wärs mit einem kleinen Benchmark (argh, ich kann immmernoch nicht komplett auf Python 2.4 updaten)?
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Donnerstag 16. Dezember 2004, 15:56

Hi,

nen benchmark kommt bald, ich hab auch noch etwas rumgespielt, xlrange in der jetzigen Form ist 8-10 mal langsamer als das builtin-xrange. Allerdings ist eine forschleife, mit xrange und addition des Zählers mit einem Longint noch eine spur langsamer. Bei den Demos die es für Python gibt, unter Debian mit apt-get install python2.x-Examples zu finden, sonst in den Sourcen zu Python. Sind auch Beispiele für range/xrange zu finden.


Gruß

Dookie
[code]#!/usr/bin/env python
import this[/code]
Benutzeravatar
jens
Moderator
Beiträge: 8461
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Donnerstag 16. Dezember 2004, 16:07

Was ist mit meine Vorschlägen: http://python.sandtner.org/viewtopic.php?p=13341

Blödsinn?
Milan
User
Beiträge: 1078
Registriert: Mittwoch 16. Oktober 2002, 20:52

Donnerstag 16. Dezember 2004, 16:31

Hi Jens. Da bis jetzt kein großer Bedarf danach war, hab ich gedacht das wäre überflüssig. Aber ja: es ist machbar und die Grenze von int zu longint wird durch sys.maxint definiert. Ich rate aber dringend davon ab, nur xlrange zu benutzen: Es ist ein in Python geschriebener Iterator, im Gegensatz zu xrange (logisch :D). Wenn nun die Ergebnisse von den xrange-Werten nocheinmal über yield zurückgegeben werden kostet das Zeit. Besser wäre es die beiden Iteratoren mit itertools.chain zusammenzufügen und beide Iteratoren über einen Decorater zu generieren. Das dürfte mehr Speed up bringen, als noch ein Abfragekonstrukt mit zusätzlichen yields in xlrange. Ich bastel nachher mal sowas.
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Donnerstag 16. Dezember 2004, 16:56

Hi jens,
Allerdings ist eine forschleife, mit xrange und addition des Zählers mit einem Longint noch eine spur langsamer.
war auf Deinen Vorschlag bezogen. Es müsste da ja auch zusätzlich noch die Addition der Ausgabe von xrange zu einem Longint hinzugezählt werden, bei xlrange ist aber nur eine Addition von step zu start nötig, ohne Umwandlung in ein Longint. Also Bei deinem Vorschlag kommt zur ausführungszeit von xrange noch die Zeit für die Addition pro Schleifendurchlauf dazu, bei xlrange nur die Addition.
in python2.4 könnte man das etwa so realisieren:

Code: Alles auswählen

start = 10000000000000
stop = 10000000100000
rstop = stop-start
for i in (start+x for x in xrange(0,rstop)):
    pass
der Generator (start+x for x in xrange(0,rstop)) könnte auch in einer entsprechenden Funktion zusammengestellt werden, mit den nötigen Änderungen für negative Stepwerte ...
Ich bastel da mal was und fügs in ein Benchmarkscript ein.


Gruß

Dookie
[code]#!/usr/bin/env python
import this[/code]
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Donnerstag 16. Dezember 2004, 18:14

Hier mal eine erste Version des Benchmarks:

Code: Alles auswählen

#!/usr/bin/env python2.4
# -*- coding: UTF-8 -*-
"""
    Modul:          xlrange_test
    Description:    Benchmark for xlrange
    Version:        0.1
    Copyright:      2004 by Milan & Dookie (Pythonforum)
    Created:        15. Dez. 2004
    Last modified:  16. Dez. 2004
    License:        free
    Requirements:   Python2.4
    Exports:        Classes and Functions to export
"""

def xlrange1(start,stop=None,step=1):
    """xlrange1([start=0,]stop[,step=1]) --> iterator object like xrange for longs"""
    if stop==None:
        stop=start
        start=0
    if step>0:
        while start<stop:
            yield start
            start+=step
    elif step<0:
        while start>stop:
            yield start
            start+=step
    else:
        raise ValueError, "xlrange() arg 3 (step) must not be zero"
        
def handleargs(arglist):
    """Take list of arguments and extract/create proper start, stop, and step
    values and return in a tuple found in Demos/"""
    try:
        if len(arglist) == 1:
            return 0, arglist[0], 1
        elif len(arglist) == 2:
            return arglist[0], arglist[1], 1
        elif len(arglist) == 3:
            if arglist[2] == 0:
                raise ValueError("xlrange() step argument must not be zero")
            return tuple([x for x in arglist])
        else:
            raise TypeError("xlrange() accepts 1-3 arguments, given", len(arglist))
    except TypeError:
        raise TypeError("xlrange() arguments must be numbers or strings "
        "representing numbers")

def xlrange2(*a):
    """xlrange2([start=0,]stop[,step=1]) --> iterator object like xrange for longs"""
    start, stop, step = tuple(long(x) for x in handleargs(a))
    value = start
    if step < 0:
        while value > stop:
            yield start
            value += step
    elif step > 0:
        while value < stop:
            yield start
            value += step

def xlrange3(*a):
    import sys
    start, stop, step = tuple(long(x) for x in handleargs(a))
    if step < 0:
        if start - stop > sys.maxint:
            return xlrange2(*a)
        elif abs(start) > sys.maxint or abs(stop) > sys.maxint:
            rstop = stop - start
            return (start + x for x in xrange(0, rstop, step))
    else:
        if stop - start > sys.maxint:
            return xlrange2(*a)
        elif abs(start) > sys.maxint or abs(stop) > sys.maxint:
            rstop = stop - start
            return (start + x for x in xrange(0, rstop, step))
    return xrange(*a)
    
if __name__ == "__main__":
    from timeit import Timer
    
    start = 10000000000
    r = 100000
    stop = start+r
    try:
        t = Timer("for i in xrange(%i, %i): pass" % (start, stop))
        print "%7.3f xrange(%i, %i)" % (t.timeit(10000000/r), start, stop)
    except OverflowError:
        pass
    t = Timer("for i in xlrange1(%i, %i): pass" % (start, stop),
              "from __main__ import xlrange1")
    print "%7.3f xlrange1(%i, %i)" % (t.timeit(10000000/r), start, stop)
    t = Timer("for i in xlrange2(%i, %i): pass" % (start, stop),
              "from __main__ import xlrange2")
    print "%7.3f xlrange2(%i, %i)" % (t.timeit(10000000/r), start, stop)
    t = Timer("for i in xlrange3(%i, %i): pass" % (start, stop),
              "from __main__ import xlrange3")
    print "%7.3f xlrange3(%i, %i)" % (t.timeit(10000000/r), start, stop)
xlrange1 ist die Ursprüngliche Verson von Milan, xlrange2 die für Longs optimierte Version von Dookie und xlrange3 basiert auf einer Idee von jens.


Gruß

Dookie
Zuletzt geändert von Dookie am Donnerstag 16. Dezember 2004, 20:10, insgesamt 1-mal geändert.
[code]#!/usr/bin/env python
import this[/code]
Antworten