Find numbers in python bisect range

Question

I have a list of integers, and I want to write a function that returns a subset of numbers within a range. Something like a function name NumbersWithinRange (list, spacing) ...

Ie

list = [4,2,1,7,9,4,3,6,8,97,7,65,3,2,2,78,23,1,3,4,5,67,8,100] interval = [4,20] results = NumbersWithinRange(list, interval) # [4,4,6,8,7,8] 

Perhaps I forgot to write another number in the results, but what an idea ...

The list can be 10/20 million long, and the range is usually a few 100.

Any suggestions on how to do this efficiently with python - I thought to use bisect.

Thanks.

Answer 1

I would use numpy for this, especially if the list is long. For instance:

 In [101]: list = np.array([4,2,1,7,9,4,3,6,8,97,7,65,3,2,2,78,23,1,3,4,5,67,8,100]) In [102]: list Out[102]: array([ 4, 2, 1, 7, 9, 4, 3, 6, 8, 97, 7, 65, 3, 2, 2, 78, 23, 1, 3, 4, 5, 67, 8, 100]) In [103]: good = np.where((list > 4) & (list < 20)) In [104]: list[good] Out[104]: array([7, 9, 6, 8, 7, 5, 8]) # %timeit says that numpy is MUCH faster than any list comprehension: # create an array 10**6 random ints b/w 0 and 100 In [129]: arr = np.random.randint(0,100,1000000) In [130]: interval = xrange(4,21) In [126]: %timeit r = [x for x in arr if x in interval] 1 loops, best of 3: 14.2 s per loop In [136]: %timeit good = np.where((list > 4) & (list < 20)) ; new_list = list[good] 100 loops, best of 3: 10.8 ms per loop In [134]: %timeit r = [x for x in arr if 4 < x < 20] 1 loops, best of 3: 2.22 s per loop In [142]: %timeit filtered = [i for i in ifilter(lambda x: 4 < x < 20, arr)] 1 loops, best of 3: 2.56 s per loop 

Answer 2

Pure Python The Python sortedcontainers module has a SortedList type that can help you. It automatically saves the list in sorted order and passed the test for tens of millions of items. The sorted list type has a bisect function that you can use.

 from sortedcontainers import SortedList data = SortedList(...) def NumbersWithinRange(items, lower, upper): start = items.bisect(lower) end = items.bisect_right(upper) return items[start:end] subset = NumbersWithinRange(data, 4, 20) 

Pagination and indexing will be much faster than crawling the entire list. The module of sorted containers is very fast and has a page comparing performance against standards against alternative implementations.

Answer 3

If the list is not sorted, you need to scan the entire list:

 lst = [ 4,2,1,...] interval=[4,20] results = [ x for x in lst if interval[0] <= x <= interval[1] ] 

If the list is sorted, you can use bisect to find the left and right indexes that linked your range.

 left = bisect.bisect_left(lst, interval[0]) right = bisect.bisect_right(lst, interval[1]) results = lst[left+1:right] 

Since scanning the list is O (n) and sorting is O (n lg n), it is probably not worth sorting the list simply using bisect if you do not plan to make many range changes.

Answer 4

I think this should be quite effective:

 >>> nums = [4,2,1,7,9,4,3,6,8,97,7,65,3,2,2,78,23,1,3,4,5,67,8,100] >>> r = [x for x in nums if 4 <= x <21] >>> r [4, 7, 9, 4, 6, 8, 7, 4, 5, 8] 

Edit:

After superb observation by J.F. Sebastian, the code changed.

Answer 5

Using Iterators

 >>> from itertools import ifilter >>> A = [4,2,1,7,9,4,3,6,8,97,7,65,3,2,2,78,23,1,3,4,5,67,8,100] >>> [i for i in ifilter(lambda x: 4 < x < 20, A)] [7, 9, 6, 8, 7, 5, 8] 

Answer 6

Create a list similar to what you described:

 import random l = [random.randint(-100000,100000) for i in xrange(1000000)] 

Now check out some possible solutions:

 interval=range(400,800) def v2(): """ return a list """ return [i for i in l if i in interval] def v3(): """ return a generator """ return list((i for i in l if i in interval)) def v4(): def te(x): return x in interval return filter(te,l) def v5(): return [i for i in ifilter(lambda x: x in interval, l)] print len(v2()),len(v3()), len(v4()), len(v5()) cmpthese.cmpthese([v2,v3,v4,v5],micro=True, c=2) 

Will print this:

  rate/sec usec/pass v5 v4 v2 v3 v5 0 6929225.922 -- -0.4% -1.0% -1.6% v4 0 6903028.488 0.4% -- -0.6% -1.2% v2 0 6861472.487 1.0% 0.6% -- -0.6% v3 0 6817855.477 1.6% 1.2% 0.6% -- 

HOWEVER, see what happens if interval is a collection instead of a list:

 interval=set(range(400,800)) cmpthese.cmpthese([v2,v3,v4,v5],micro=True, c=2) rate/sec usec/pass v5 v4 v3 v2 v5 5 201332.569 -- -20.6% -62.9% -64.6% v4 6 159871.578 25.9% -- -53.2% -55.4% v3 13 74769.974 169.3% 113.8% -- -4.7% v2 14 71270.943 182.5% 124.3% 4.9% -- 

Now compare with numpy:

 na=np.array(l) def v7(): """ assume you have to convert from list => numpy array and return a list """ arr=np.array(l) tgt = np.where((arr >= 400) & (arr < 800)) return [arr[x] for x in tgt][0].tolist() def v8(): """ start with a numpy list but return a python list """ tgt = np.where((na >= 400) & (na < 800)) return na[tgt].tolist() def v9(): """ numpy all the way through """ tgt = np.where((na >= 400) & (na < 800)) return [na[x] for x in tgt][0] # or return na[tgt] if you prefer that syntax... cmpthese.cmpthese([v2,v3,v4,v5, v7, v8,v9],micro=True, c=2) rate/sec usec/pass v5 v4 v7 v3 v2 v8 v9 v5 5 185431.957 -- -17.4% -24.7% -63.3% -63.4% -93.6% -93.6% v4 7 153095.007 21.1% -- -8.8% -55.6% -55.7% -92.3% -92.3% v7 7 139570.475 32.9% 9.7% -- -51.3% -51.4% -91.5% -91.5% v3 15 67983.985 172.8% 125.2% 105.3% -- -0.2% -82.6% -82.6% v2 15 67861.438 173.3% 125.6% 105.7% 0.2% -- -82.5% -82.5% v8 84 11850.476 1464.8% 1191.9% 1077.8% 473.7% 472.6% -- -0.0% v9 84 11847.973 1465.1% 1192.2% 1078.0% 473.8% 472.8% 0.0% -- 

Clearly, numpy is faster than pure python if you can work with numpy to the end. Otherwise, use the interval set to speed things up a bit ...

Answer 7

I think you are looking for something like this.

 b=[i for i in a if 4<=i<90] print sorted(set(b)) [4, 5, 6, 7, 8, 9, 23, 65, 67, 78] 

Answer 8

If your data set is not too rare, you can use "baskets" to store and retrieve data. For instance:

 a = [4,2,1,7,9,4,3,6,8,97,7,65,3,2,2,78,23,1,3,4,5,67,8,100] # Initalize a list of 0 [0, 0, ...] # This is assuming that the minimum possible value is 0 bins = [0 for _ in range(max(a) + 1)] # Update the bins with the frequency of each number for i in a: bins[i] += 1 def NumbersWithinRange(data, interval): result = [] for i in range(interval[0], interval[1] + 1): freq = data[i] if freq > 0: result += [i] * freq return result 

This works for this test:

 print(NumbersWithinRange(bins, [4, 20])) # [4, 4, 4, 5, 6, 7, 7, 8, 8, 9] 

For simplicity, I omitted some bounds checking in functions.

Again, this may work better in terms of space and time use, but it depends a lot on your particular data set. The less sparse data, the better.