Home Original page

if number is 1-2, 4 or 6-8 or 12-28, 30, 32...

Cliff Wells logiplexsoftware at earthlink.net
Tue Jun 11 20:15:53 EDT 2002 
On Tue, 11 Jun 2002 16:44:08 GMT
Terry Reedy wrote:

> 
> > "Gustaf Liljegren" <gustafl at algonet.se>
> wants elegant function matching int to any of multiple numbers and
> ranges
> 
> My very-pseudo code had parity error at end.  Real Python code:
> 
> import bisect
> 
> # noncontiguous and sorted numbers and ranges: 1, 3, 10-300, 2999,
> 12345-98765
> # expanded to (lo, hi+1) ranges and flattened to list - exercise for
> OP
> rangenums = (1,2, 3,4, 10,301, 2999,3000, 12345,98766)
> 
> for i in (0,1,2, 3,4, 10,20, 300,301, 90000,98765,98766,100000):
>   print bisect.bisect(rangenums, i) %2,
> 
> 0 1 0 1 0 1 1 1 0 1 1 0 0
> >>>

Hm. I haven't used bisect() before:


from bisect import bisect
from time import time
from random import random, randrange, shuffle

class Ranges:
    def __init__(self, ranges):
        self.ranges = []
        self.breakpoints = []
        for r in ranges:
            try:
                s, e = r
            except TypeError:
                s, e = r, r
            self.ranges.append((s, e))
        self.ranges.sort()
        self.breakpoints = map(lambda r: r[0], self.ranges)

    def has(self, n):
        s, e = self.ranges[bisect(self.breakpoints, n) - 1]
        return s <= n <= e

def isin(n, ranges):
    for r in ranges:
        try: 
            s, e = r
            if s <= n <= e:
                return 1
        except TypeError:
            if n == r:
                return 1
    return 0

def createRanges(n):
    # create a list of non-overlapping sequences and ints, there's probably a
faster way...
    ranges = []
    s = 0
    for i in range(n):
        l = int(random() * 1000) + 1
        e = s + l
        s = randrange(s, e)
        if int(random() * 10) % 2:
            ranges.append((s, e))
        else:
            ranges.append(s)
        s = e
        e += l
        
    shuffle(ranges)
    return ranges


# ------------
ranges = createRanges(10000)

print "Initialize Range:",
t1 = time()
r = Ranges(ranges)
print time() - t1

t2 = time()
print "Range():",
for i in range(0, 100, 3):
    r.has(i)
t = time()
print t - t2, "total", t - t1

t = time()
print "isin():",
for i in range(0, 100, 3):
    isin(i, ranges)
print time() - t


####################################
Initialize Range: 0.331060051918
Range(): 0.00136804580688 total 0.33601808548
isin(): 4.98800003529

Clearly faster although it does use a bit more memory...

-- 
Cliff Wells, Software Engineer
Logiplex Corporation (www.logiplex.net)
(503) 978-6726 x308  (800) 735-0555 x308
More information about the Python-list mailing list