FAQ

[Python] xrange not hashable - why not?

Gerrit Holl
Jan 25, 2004 at 2:47 pm
Hi,

why is an xrange object not hashable?
I was trying to do something like:

comments = {
xrange(0, 4): "Few",
xrange(4, 10): "Several",
xrange(10, 100): "A lot",
xrange(100, sys.maxint): "Can't count them"}
for (k, v) in comments.items():
if n in k:
commentaar = v
break

Because:
- I found it easier to extend than:
if 0 <= n < 4: return "few"
elif ... # etc
- And better readable than:
if k[0] <= n < k[1]: # using tuples
- And much more memory efficient than tuple(...) (especially the
last one ;-)

It would not be difficult to let xrange have a hash:

hash((self.start, self.step, self.stop))

would be sufficient, I think.

Hmm, start, step and stop appear to have disappeared in Python 2.3...
certainly makes it somewhat more difficult. I shouldn't even to containment
testing according to PEP 260, and Python 2.3.3 should warn me not to
do... it doesn't, however.

So, should I use one of the alternatives after all? Or does someone have
something better to offer?

yours,
Gerrit.
reply

Search Discussions

14 responses

  • Sean Ross at Jan 25, 2004 at 4:08 pm
    "Gerrit Holl" <gerrit at nl.linux.org> wrote in message
    news:mailman.764.1075042048.12720.python-list at python.org...
    Hi,

    why is an xrange object not hashable?

    I don't know the answer for this.

    I was trying to do something like:

    comments = {
    xrange(0, 4): "Few",
    xrange(4, 10): "Several",
    xrange(10, 100): "A lot",
    xrange(100, sys.maxint): "Can't count them"}
    for (k, v) in comments.items():
    if n in k:
    commentaar = v
    break
    There's a bit of an efficiency issue with using 'n in k' for something like
    xrange(100, sys.maxint),
    since you have to walk through the items in that range to see if n is in
    there, and that's a large range.
    Perhaps this would help:

    class bounds:
    def __init__(self, start, stop, step=1):
    self.start = start
    self.stop = stop
    self.step = step
    def is_step(self, other):
    q, r = divmod(other-self.start, self.step)
    return r == 0
    def __contains__(self, other):
    return self.start <= other < self.stop and self.is_step(other)
    def __hash__(self):
    return id(self)
    def __repr__(self):
    return "bounds(start=%s, stop=%s, step=%s)"%\
    (self.start, self.stop, self.step)

    import sys
    import random

    comments = {
    bounds(0, 4): "Few",
    bounds(4, 10): "Several",
    bounds(10, 100): "A lot",
    bounds(100, sys.maxint): "Can't count them"}

    n = random.randint(0, sys.maxint)
    print n

    for k, v in comments.iteritems():
    print k
    if n in k:
    print v
    break
    else:
    print n, "out of bounds"

    HTH,
    Sean
  • Sean Ross at Jan 25, 2004 at 4:19 pm
    "Sean Ross" <sross at connectmail.carleton.ca> wrote in message
    news:FSRQb.95$qU3.31981 at news20.bellglobal.com...
    There's a bit of an efficiency issue with using 'n in k' for something like
    xrange(100, sys.maxint),
    since you have to walk through the items in that range to see if n is in
    there, and that's a large range.
    Hmm, I don't think what I said there is correct, please disregard.

    Sorry for any confusion,
    Sean
  • Irmen de Jong at Jan 25, 2004 at 4:45 pm

    Sean Ross wrote:

    xrange(100, sys.maxint),
    since you have to walk through the items in that range to see if n is in
    there, and that's a large range.

    Hmm, I don't think what I said there is correct, please disregard.

    I think you're right though:

    90000000 in xrange(1,sys.maxint) takes a long time to complete....

    --Irmen
  • Martin v. Löwis at Jan 25, 2004 at 6:27 pm

    Gerrit Holl wrote:
    why is an xrange object not hashable?
    Because they don't have a notion of equality
    beyond identity.

    Regards,
    Martin
  • Josiah Carlson at Jan 25, 2004 at 6:42 pm

    why is an xrange object not hashable?
    I was trying to do something like:
    Could be a hold-over from xrange trying to have all of the features of a
    list returned by range; lists are unhashable because they are mutable.
    comments = {
    xrange(0, 4): "Few",
    xrange(4, 10): "Several",
    xrange(10, 100): "A lot",
    xrange(100, sys.maxint): "Can't count them"}
    for (k, v) in comments.items():
    if n in k:
    commentaar = v
    break
    It would not be difficult to let xrange have a hash:

    hash((self.start, self.step, self.stop))
    I don't believe anyone ever said it was. *wink*

    Hmm, start, step and stop appear to have disappeared in Python 2.3...
    I don't know about that:
    Python 2.3.2 (#49, Oct 2 2003, 20:02:00) [MSC v.1200 32 bit (Intel)] on
    win32
    Type "help", "copyright", "credits" or "license" for more information.
    help(xrange)
    Help on class xrange in module __builtin__:

    class xrange(object)
    xrange([start,] stop[, step]) -> xrange object
    So, should I use one of the alternatives after all? Or does someone have
    something better to offer?
    Honestly it is one of those things that are easily remedied by a
    custom-built class. Like the below:

    class HashableXRange:
    def __init__(self, s1, s2=None, s3=None):
    if s2 is None:
    s1, s2, s3 = 0, s1, 1
    elif s3 is None:
    s3 = 1
    self.start = s1
    self.stop = s2
    self.step = s3
    def __hash__(self):
    return hash((self.start, self.stop, self.step))
    def __cmp__(self, other):
    if isinstance(other, self.__class__):
    return cmp(self.start, other.start) or\
    cmp(self.stop, other.stop) or\
    -cmp(self.step, other.step)
    return cmp(self.start, other)
    def __iter__(self):
    return iter(xrange(self.start, self.stop, self.step))
    def __contains__(self, object):
    if self.start <= object < self.stop:
    if (object-self.start) % self.step == 0:
    return 1
    return 0

    I included the __cmp__ function in order to give it a richer set of
    behavior. One thing to note about hashes is that they are not required
    to be unique. As such, the hashing algorithm is not the absolute best
    algorithm ever. It is pretty good, but it is not guaranteed that
    hash((a,b,c)) != hash((d,e,f)) for different sets of three objects.
    Better to be safe than sorry.

    I would have subclassed xrange, but Python 2.3 doesn't like that.
    Apparently there is no subclassing for xranges.

    - Josiah
  • Peter Otten at Jan 25, 2004 at 7:12 pm

    Gerrit Holl wrote:

    I was trying to do something like:

    comments = {
    xrange(0, 4): "Few",
    xrange(4, 10): "Several",
    xrange(10, 100): "A lot",
    xrange(100, sys.maxint): "Can't count them"}
    for (k, v) in comments.items():
    if n in k:
    commentaar = v
    break [...]
    So, should I use one of the alternatives after all? Or does someone have
    something better to offer?
    I think you want bisect():

    import bisect

    ranges = [
    (0, "Few"),
    (4, "Several"),
    (10, "A lot"),
    (100, "Can't count them")
    ]

    def makelookup(r):
    bounds = [i[0] for i in r][1:]
    names = [i[1] for i in r]
    def find(value):
    return names[bisect.bisect(bounds, value)]
    return find

    lookup = makelookup(ranges)

    # use it
    last = ""
    for i in range(-100, 1000):
    if last != lookup(i):
    last = lookup(i)
    print i, last

    Note that names needs one more entry than bounds. I "fixed" that by
    discarding the first bounds item.

    Peter
  • Hans Nowak at Jan 26, 2004 at 12:06 am

    Gerrit Holl wrote:
    Hi,

    why is an xrange object not hashable?
    I was trying to do something like:

    comments = {
    xrange(0, 4): "Few",
    xrange(4, 10): "Several",
    xrange(10, 100): "A lot",
    xrange(100, sys.maxint): "Can't count them"}
    for (k, v) in comments.items():
    if n in k:
    commentaar = v
    break
    So far, everybody who replied seems to agree or assumes that xrange indeed
    isn't hashable. However:

    Python 2.3.3 (#51, Dec 18 2003, 20:22:39) [MSC v.1200 32 bit (Intel)] on win32
    Type "help", "copyright", "credits" or "license" for more information.
    import sys
    comments = {
    ... xrange(0, 4): "Few",
    ... xrange(4, 10): "Several",
    ... xrange(10, 100): "A lot",
    ... xrange(100, sys.maxint): "Can't count them"}
    comments
    {xrange(4): 'Few', xrange(4, 10): 'Several', xrange(100, 2147483647): "Can't
    count them", xrange(10, 100): 'A lot'}

    Sure enough, that dict works. Let's try something else then:
    a = xrange(10)
    b = xrange(20)
    hash(a), hash(b)
    (7774576, 7775104)

    It seems that xrange objects do have a hash value. The other part of the code
    works as well:
    n = 3
    for k, v in comments.items():
    ... if n in k:
    ... commentaar = v
    ... break
    ...
    commentaar
    'Few'

    I don't really see what the problem is...?

    --
    Hans (hans at zephyrfalcon.org)
    http://zephyrfalcon.org/
  • Jeff Epler at Jan 26, 2004 at 12:11 am

    On Sun, Jan 25, 2004 at 07:06:31PM -0500, Hans Nowak wrote:
    So far, everybody who replied seems to agree or assumes that xrange indeed
    isn't hashable. However:
    [...]

    It wasn't in older versions:
    $ python
    Python 2.2.2 (#1, Feb 24 2003, 19:13:11)
    [GCC 3.2.2 20030222 (Red Hat Linux 3.2.2-4)] on linux2
    Type "help", "copyright", "credits" or "license" for more information.
    hash(xrange(0))
    Traceback (most recent call last):
    File "<stdin>", line 1, in ?
    TypeError: unhashable type

    Jeff
  • Hans Nowak at Jan 26, 2004 at 12:28 am

    Jeff Epler wrote:
    On Sun, Jan 25, 2004 at 07:06:31PM -0500, Hans Nowak wrote:

    So far, everybody who replied seems to agree or assumes that xrange indeed
    isn't hashable. However:
    [...]

    It wasn't in older versions:
    $ python
    Python 2.2.2 (#1, Feb 24 2003, 19:13:11)
    [GCC 3.2.2 20030222 (Red Hat Linux 3.2.2-4)] on linux2
    Type "help", "copyright", "credits" or "license" for more information.
    hash(xrange(0))
    Traceback (most recent call last):
    File "<stdin>", line 1, in ?
    TypeError: unhashable type
    Huh. This is really weird:

    (C:\) $ python22
    Python 2.2.2 (#37, Oct 14 2002, 17:02:34) [MSC 32 bit (Intel)] on win32
    Type "help", "copyright", "credits" or "license" for more information.
    hash(xrange)
    503376880

    (C:\) $ \Python21\python.exe
    Python 2.1 (#15, Apr 16 2001, 18:25:49) [MSC 32 bit (Intel)] on win32
    Type "copyright", "credits" or "license" for more information.
    hash(xrange)
    504420928

    (C:\) $ \python152\python.exe
    Python 1.5.2 (#0, Apr 13 1999, 10:51:12) [MSC 32 bit (Intel)] on win32
    Copyright 1991-1995 Stichting Mathematisch Centrum, Amsterdam
    hash(xrange)
    504409536

    ...?!

    Maybe it's platform-specific?

    Confused-ly y'rs,

    --
    Hans (hans at zephyrfalcon.org)
    http://zephyrfalcon.org/
  • Hans Nowak at Jan 26, 2004 at 12:34 am

    I wrote:

    Huh. This is really weird:

    (C:\) $ python22
    Python 2.2.2 (#37, Oct 14 2002, 17:02:34) [MSC 32 bit (Intel)] on win32
    Type "help", "copyright", "credits" or "license" for more information.
    hash(xrange)
    503376880
    Um, duh...
    hash(xrange(0))
    Traceback (most recent call last):
    File "<stdin>", line 1, in ?
    TypeError: unhashable type

    --
    Hans (hans at zephyrfalcon.org)
    http://zephyrfalcon.org/
  • Martin v. Löwis at Jan 26, 2004 at 6:11 am

    Hans Nowak wrote:

    (C:\) $ python22
    Python 2.2.2 (#37, Oct 14 2002, 17:02:34) [MSC 32 bit (Intel)] on win32
    Type "help", "copyright", "credits" or "license" for more information.
    hash(xrange)
    503376880
    You shouldn't hash the xrange function, but instance of the xrange type.

    Regards,
    Martin
  • Andrew MacIntyre at Jan 26, 2004 at 12:17 am

    On Sun, 25 Jan 2004, Gerrit Holl wrote:

    why is an xrange object not hashable?
    xrange() returns an iterator. iterators seem universally unhashable,
    probably because they can't be deemed "concrete", though I can't find
    anything in the 2.3.3 docs about this - perhaps the relevant PEPs might.
    I was trying to do something like:

    comments = {
    xrange(0, 4): "Few",
    xrange(4, 10): "Several",
    xrange(10, 100): "A lot",
    xrange(100, sys.maxint): "Can't count them"}
    for (k, v) in comments.items():
    if n in k:
    commentaar = v
    break
    Even if it worked, there's a nasty performance trap in the sys.maxint
    case: if the sys.maxint case is the first returned by the items() method
    call and n < 100, the "in" will evaluate the sys.maxint xrange iterator.

    Without more info, I don't see why a dictionary is that useful in this
    case, so I would actually write the above as:

    comments = (((0, 4), "Few"),
    ((4, 10), "Several"),
    ((10, 100), "A lot"))
    commentaar= "Can't count them"
    for (k, v) in comments:
    if n in xrange(*k):
    commentaar = v
    break

    --
    Andrew I MacIntyre "These thoughts are mine alone..."
    E-mail: andymac at bullseye.apana.org.au (pref) | Snail: PO Box 370
    andymac at pcug.org.au (alt) | Belconnen ACT 2616
    Web: http://www.andymac.org/ | Australia
  • Andrew MacIntyre at Jan 26, 2004 at 12:50 am

    On Mon, 26 Jan 2004, Andrew MacIntyre wrote:
    On Sun, 25 Jan 2004, Gerrit Holl wrote:

    why is an xrange object not hashable?
    xrange() returns an iterator. iterators seem universally unhashable,
    probably because they can't be deemed "concrete", though I can't find
    anything in the 2.3.3 docs about this - perhaps the relevant PEPs might.
    Hmmm... part fact, part BS on my part.

    Prior to 2.3, xrange() returned an object that implemented lazy item
    access, which didn't have explicit hash support.

    With 2.3, xrange() began returning an iterator, which is hashable (as
    others have pointed out).

    --
    Andrew I MacIntyre "These thoughts are mine alone..."
    E-mail: andymac at bullseye.apana.org.au (pref) | Snail: PO Box 370
    andymac at pcug.org.au (alt) | Belconnen ACT 2616
    Web: http://www.andymac.org/ | Australia
  • Isaac To at Jan 26, 2004 at 2:14 am

    "Andrew" == Andrew MacIntyre <andymac at bullseye.apana.org.au> writes:
    why is an xrange object not hashable?
    Andrew> xrange() returns an iterator. iterators seem universally
    Andrew> unhashable, probably because they can't be deemed "concrete",
    Andrew> though I can't find anything in the 2.3.3 docs about this -
    Andrew> perhaps the relevant PEPs might.

    xrange's are hashable in Python 2.3.
    I was trying to do something like:
    >>
    comments = { xrange(0, 4): "Few", xrange(4, 10): "Several",
    xrange(10, 100): "A lot", xrange(100, sys.maxint): "Can't count
    them"} for (k, v) in comments.items(): if n in k: commentaar = v
    break
    Andrew> Even if it worked, there's a nasty performance trap in the
    Andrew> sys.maxint case: if the sys.maxint case is the first returned by
    Andrew> the items() method call and n < 100, the "in" will evaluate the
    Andrew> sys.maxint xrange iterator.

    I used to think that the code won't work at all. I think xrange works like
    generators. If that is the case, the state stored within the xrange in the
    dict will cause the whole thing to fail if the same range is used the second
    time. E.g.,
    def yrange(x,y):
    ... ret = x
    ... while ret < y:
    ... yield ret
    ... ret += 1
    ...
    for a in yrange(1,5):
    ... print a
    ...
    1
    2
    3
    4
    comments = {
    ... yrange(0, 4): "Few",
    ... yrange(4,10): "Several",
    ... yrange(10,100): "A lot",
    ... yrange(100, sys.maxint): "Can't count them"}
    for (k,v) in comments.items():
    ... if 1 in k:
    ... print v
    ... break
    ...
    Few
    for (k,v) in comments.items():
    ... if 1 in k:
    ... print v
    ... break
    ... (type interrupt here after waiting for some time)
    Traceback (most recent call last):
    File "<stdin>", line 2, in ?
    File "<stdin>", line 5, in yrange
    KeyboardInterrupt

    But for xrange this is not the case:
    comments = {
    ... xrange(0, 4): "Few",
    ... xrange(4, 10): "Several",
    ... xrange(10, 100): "A lot",
    ... xrange(100, sys.maxint): "Can't count them"}
    for (k,v) in comments.items():
    ... if 1 in k:
    ... print v
    ... break
    ...
    Few
    for (k,v) in comments.items():
    ... if 1 in k:
    ... print v
    ... break
    ...
    Few

    So xrange is not just an iterator. On the other hand, things like 1000000
    in xrange(1,sys.maxint) really needs a long time to compute. That makes me
    wonder how xrange's are actually implemented.

    Regards,
    Isaac.

Related Discussions