1

This question is linked to this: First Python list index greater than x?

I have a (sorted) list of floats, and I want to find the first index that exceeds each value of a second list

e.g. 

 l=[0.2,0.3,0.7,0.9]
 m=[0.25,0.6]

if m were a float I would use this:

 bisect.bisect_left(l,m)

But for the case where m is a list this fails, and I can only think to employ a list comprehension:

[bisect.bisect_left(l,i) for i in m]

which gives:

 [1, 2]

which works, but I want to speed it up for large lists in my real example by avoiding the list comprehension as my tests showed this was the "bottleneck" operation (I earlier stated I suspected it was too slow). Is there a way to efficiently do this using a vectorized function in e.g. numpy or an improved algorithm (as only one traverse of the list is required)?

ClimateUnboxed
  • 7,106
  • 3
  • 41
  • 86
  • what would the final output look like and is the second list sorted as well? – Ryan Schaefer Mar 22 '20 at 23:44
  • second list is also sorted in my application, added output and apologies for a comma error – ClimateUnboxed Mar 22 '20 at 23:50
  • "I suspect this is slow for large lists". Why? Is there a particular algorithmic enhancement you have in mind? – Karl Knechtel Mar 23 '20 at 00:03
  • @KarlKnechtel because it uses binary search on the whole `l` list, but since the lists are sorted, we can easily narrow the search area by remembering the last found index, see my answer below. – lenik Mar 23 '20 at 00:09
  • @KarlKnechtel - I'm not that experienced with efficient python, but in my earlier problem here https://stackoverflow.com/questions/59147730/calculate-difference-between-all-combinations-of-entries-in-a-vector-in-python when I found a solution using list comprehension then it was 100 times slower than using built ins, plus it seemed that a more efficient solution could be found using a single sweep. I tried unsuccessfully to find a suitable function/algorithm in numpy, hence the question. – ClimateUnboxed Mar 23 '20 at 08:04
  • ? List comprehensions are built-in; numpy is *not*. And of course you will see poor performance trying to use built-in tools on numpy data, because the built-ins can't take advantage of any of the numpy optimizations - that's why numpy exists. That's completely different from the issue here. – Karl Knechtel Mar 23 '20 at 14:31
  • Yes, excuse me for not using the correct terminology, I mean a standard function (also in a package) that allows one to perform this in a vectorized way for speed. It turns out that np.searchsorted was the function I was looking for and it is indeed a lot faster. Thanks again for all your help. – ClimateUnboxed Mar 26 '20 at 14:09

3 Answers3

4

Well, there's a good chance that bisect_left is an O(logN) operation (binary search) so your overall operation would be O(KlogN) where N relates to size of l, and K relates to size of m.

Were the second list m sorted as well, you could make this an O(N) operation simply by running an index through both lists concurrently.

But, re your "I suspect this is slow" comment, your first move should always be to test the easiest solution with the largest expected data set. If that's workable, stop right there! Only if it's deficient do you start thinking about optimisation.

For example, consider the following program:

import random
import bisect
haystack = []
for _ in range(1000000):
    haystack.append(random.random())
haystack.sort()
needles = []
for _ in range(10000):
    needles.append(random.random())
result = [bisect.bisect_left(haystack, needle) for needle in needles]
print(result)

This creates a 1,000,000-element haystack and a 10,000-element needle list then uses your bisect-ing list comprehension to do the work. Running that on my (not particularly grunty) desktop with time shows:

real    0m0.738s  # < 3/4 of a second elapsed
user    0m0.578s
sys     0m0.109s

And this includes the time taken to construct the lists, sort the big one, and print out the results.

Using timeit to get rid of all that setup time can be done with:

import timeit
import random
import bisect
haystack = []
for _ in range(1000000):
    haystack.append(random.random())
haystack.sort()
needles = []
for _ in range(10000):
    needles.append(random.random())
print(timeit.timeit('[bisect.bisect_left(haystack, needle) for needle in needles]', setup = 'from __main__ import bisect, haystack, needles', number = 1000))

The output of that is 12.27 for the thousand iterations, which means you could do it about 75 times per second without breaking a sweat.

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
  • Further to that: The overall operation would be K log(N); which is to say, it depends on how the size of `m` compares to the size of `l`. In cases where the `l` is large but `m` is small, it would be better to binary-search each element from `m`, rather than doing the kind of iteration you describe. – Karl Knechtel Mar 23 '20 at 00:04
1

You have to remember the last value found to use it as a starting point for the next binary search, so instead of the list comprehension you have to use a for loop:

result = [bisect.bisect_left(l,m[0]),]
for i in m[1:] :
    result.append( bisect.bisect_left(l,i,result[-1]))

This should work faster than a simple comprehension.

lenik
  • 23,228
  • 4
  • 34
  • 43
1

So I found there is a numpy function to perform this task, np.searchsorted. which is much faster than the use of list comprehensions.

result=np.searchsorted(searchlist,newindices)

These are the timings for the various solutions:

1. Standard List comprehension:

this was my first attempt at a solution

python3 -m timeit -s "import numpy as np" -s "import bisect" -s "h=np.sort(np.random.uniform(size=10000))" -s "n=np.sort(np.random.uniform(size=1000))" "r=[bisect.bisect_left(h,i) for i in n]"

200 loops, best of 5: 1.61 msec per loop

2. Shortened search in for loop

This was the solution kindly provided by @lenik

python3 -m timeit -s "import numpy as np" -s "import bisect" -s "h=np.sort(np.random.uniform(size=10000))" -s "n=np.sort(np.random.uniform(size=1000))" "r=[bisect.bisect_left(h,n[0])]" "for i in n[1:]:" "    r.append(bisect.bisect_left(h,i,r[-1]))"

200 loops, best of 5: 1.6 msec per loop

Hardly different from the list comprehension which I was somewhat surprised about...

3. Numpy searchsorted

python3 -m timeit -s "import numpy as np" -s "import bisect" -s "h=np.sort(np.random.uniform(size=10000))" -s "n=np.sort(np.random.uniform(size=1000))" "r=np.searchsorted(h,n)"

10000 loops, best of 5: 33.6 usec per loop

Approximately 50 times faster than the list comprehension based solutions for this example, so hands down the fastest.

ClimateUnboxed
  • 7,106
  • 3
  • 41
  • 86