xrange not hashable - why not?

[Gerrit Holl]

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.

 

[Sean Ross]

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]

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]

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

 

[=?ISO-8859-1?Q?=22Martin_v=2E_L=F6wis=22?=]

why is an xrange object not hashable?

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

Regards,
Martin

 

[Josiah Carlson]

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

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