Fastest way to slice a list with upper bound not in the list

user_8228558 0
Viewed 100

Let's say that we have a huge sorted list with integers. What is the fastest way to slice this list using an upper bound that is not in the list?

For example, let's say that our list is:

l=list(range(0,1000000, 2))

(this is a simple example, the list could be of any length and with no specific interval, so it cannot be related with some range)

And we want to get a slice, with items smaller than limit=1001

What is the fastest way to achive that, ideally without checking all items of the list? A common way is to use a list comprehension, eg [i for i in l if i<limit], but this way we must check all items of l and compare them with limit. If the limit is in the list, we could use something like l[:l.index(limit)] but what if it's not in the list? Any idea?

list python
3 Answers

You can use bisect for this:

import bisect
print(l[:bisect.bisect_right(l, 1001)])
user_129522630

I just want to put some comparative timing out there for these two answers.

Given this benchmark:

import bisect 
import time 

def f1(l, tgt):
    return bisect.bisect_right(l, tgt)

def f2(l,tgt):
    slice_condition = lambda num: num >= tgt
    try:
        slice_idx = next(idx for idx, num in enumerate(l) if slice_condition(num))
    except StopIteration:
        slice_idx = len(l)
    return slice_idx 

def f3(l,tgt):
    return next((idx for idx, val in enumerate(l) if val>=tgt), len(l))


def cmpthese(funcs, args=(), cnt=10, rate=True, micro=True, deepcopy=True):
    from copy import deepcopy 
    """Generate a Perl style function benchmark"""                   
    def pprint_table(table):
        """Perl style table output"""
        def format_field(field, fmt='{:,.0f}'):
            if type(field) is str: return field
            if type(field) is tuple: return field[1].format(field[0])
            return fmt.format(field)     

        def get_max_col_w(table, index):
            return max([len(format_field(row[index])) for row in table])         

        col_paddings=[get_max_col_w(table, i) for i in range(len(table[0]))]
        for i,row in enumerate(table):
            # left col
            row_tab=[row[0].ljust(col_paddings[0])]
            # rest of the cols
            row_tab+=[format_field(row[j]).rjust(col_paddings[j]) for j in range(1,len(row))]
            print(' '.join(row_tab))                

    results={}
    for i in range(cnt):
        for f in funcs:
            if args:
                local_args=deepcopy(args)
                start=time.perf_counter_ns()
                f(*local_args)
                stop=time.perf_counter_ns()
            results.setdefault(f.__name__, []).append(stop-start)
    results={k:float(sum(v))/len(v) for k,v in results.items()}     
    fastest=sorted(results,key=results.get, reverse=True)
    table=[['']]
    if rate: table[0].append('rate/sec')
    if micro: table[0].append('\u03bcsec/pass')
    table[0].extend(fastest)
    for e in fastest:
        tmp=[e]
        if rate:
            tmp.append('{:,}'.format(int(round(float(cnt)*1000000.0/results[e]))))

        if micro:
            tmp.append('{:,.1f}'.format(results[e]/float(cnt)))

        for x in fastest:
            if x==e: tmp.append('--')
            else: tmp.append('{:.1%}'.format((results[x]-results[e])/results[e]))
        table.append(tmp) 

    pprint_table(table)                    

if __name__=='__main__':
    import sys
    print(sys.version)
    
    small=range(1_000)
    mid=range(100_000)
    large=range(1_000_000)
    cases=(
        ('small, found', small, len(small)//2),
        ('small, not found', small, len(small)),
        ('mid, found', mid, len(mid)//2),
        ('mid, not found', mid, len(mid)),
        ('large, found', large, len(large)//2),
        ('large, not found', large, len(large))
    )
    for txt, x, tgt in cases:
        print(f'\n{txt}:')
        l=list(x)
        args=(l,tgt)
            cmpthese([f1,f2,f3],args)

If you run it with small, mid sized and larger lists each with the case of 1) found in the middle or 2) scan all the way to the end, you can see that bisect is substantially faster. By orders of magnitude.

The benchmark prints on my computer:

3.9.1 (default, Jan 30 2021, 15:51:59) 
[Clang 12.0.0 (clang-1200.0.32.29)]

small, found:
   rate/sec μsec/pass      f2      f3     f1
f2      182   5,501.4      --  -59.2% -98.8%
f3      445   2,246.9  144.9%      -- -96.9%
f1   14,562      68.7 7911.4% 3172.0%     --

small, not found:
   rate/sec μsec/pass       f2      f3     f1
f2       90  11,053.2       --  -58.8% -99.5%
f3      220   4,555.5   142.6%      -- -98.7%
f1   17,349      57.6 19076.4% 7803.3%     --

mid, found:
   rate/sec μsec/pass        f2       f3     f1
f2        2 561,882.8        --   -57.2% -99.9%
f3        4 240,253.2    133.9%       -- -99.9%
f1    2,942     339.9 165184.0% 70573.1%     --

mid, not found:
   rate/sec   μsec/pass        f2        f3      f1
f2        1 1,119,041.1        --    -58.0% -100.0%
f3        2   469,960.8    138.1%        --  -99.9%
f1    3,804       262.9 425552.8% 178660.3%      --

large, found:
   rate/sec   μsec/pass        f2       f3     f1
f2        0 5,833,734.0        --   -55.3% -99.9%
f3        0 2,605,010.2    123.9%       -- -99.9%
f1      335     2,988.1 195135.5% 87080.9%     --

large, not found:
   rate/sec    μsec/pass        f2        f3      f1
f2        0 11,553,311.3        --    -54.4% -100.0%
f3        0  5,264,216.7    119.5%        -- -100.0%
f1      710      1,408.9 819923.5% 373540.2%      --
user_2986070

A quick and easy way to do it in O(n) (specifically, 2k where k is the index at which the list needs to be sliced) without relying on binary search would be to search for the index of the first element not meeting the condition, and slice up to that point, using an iterator:

slice_condition = lambda num: num >= limit
slice_idx = next((idx for idx, num in enumerate(l) if slice_condition(num)), len(l))
slice = l[:slice_idx]

Of course, binary search will find you the slice_idx in O(log(n)) time instead, but slicing is a linear operation anyway so the complexity of the whole unit is still O(n).

user_26488110
Related