[Python] xrange not hashable - why not?

"Gerrit Holl" <gerrit at nl.linux.org> wrote in message
news:mailman.764.1075042048.12720.python-list at python.org...

I don't know the answer for this.

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" <sross at connectmail.carleton.ca> wrote in message
news:FSRQb.95$qU3.31981 at news20.bellglobal.com...
Hmm, I don't think what I said there is correct, please disregard.

Sorry for any confusion,
Sean

I think you're right though:

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

--Irmen

Because they don't have a notion of equality
beyond identity.

Regards,
Martin

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.
I don't believe anyone ever said it was. *wink*

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 on class xrange in module __builtin__:

class xrange(object)
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

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

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.
... xrange(0, 4): "Few",
... xrange(4, 10): "Several",
... xrange(10, 100): "A lot",
... xrange(100, sys.maxint): "Can't count them"}
{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:
(7774576, 7775104)

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

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

[...]

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.
Traceback (most recent call last):
File "<stdin>", line 1, in ?
TypeError: unhashable type

Jeff

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.
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.
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
504409536

...?!

Maybe it's platform-specific?

Confused-ly y'rs,

Um, duh...
Traceback (most recent call last):
File "<stdin>", line 1, in ?
TypeError: unhashable type

You shouldn't hash the xrange function, but instance of the xrange type.

Regards,
Martin

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.
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

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> 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.
>>
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.,
... ret = x
... while ret < y:
... yield ret
... ret += 1
...
... print a
...
1
2
3
4
... yrange(0, 4): "Few",
... yrange(4,10): "Several",
... yrange(10,100): "A lot",
... yrange(100, sys.maxint): "Can't count them"}
... if 1 in k:
... print v
... break
...
Few
... 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:
... xrange(0, 4): "Few",
... xrange(4, 10): "Several",
... xrange(10, 100): "A lot",
... xrange(100, sys.maxint): "Can't count them"}
... if 1 in k:
... print v
... break
...
Few
... 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.