Python bisect模块的妙用

TL;DR 本文将介绍Python bisect模块在某些场景下的妙用,可以高效和优雅的改善原有使用if-else才能解决问题。

难题:查询整数所属的区间

应用开发过程中,经常出现一种情景,需要你查询一个整数落在哪一个范围内,比如根据消费金额确定优惠金额或者打折力度等。具体的例子有:消费满100元优惠10元,消费满200元优惠25元,等等。

常规解决方案及其缺点

通常情况下,都是使用switch/if-elif来解决的,范围比较少的情况,代码还属于比较简洁的,当范围的数量增加,代码就变的相当的不简洁了,正如下面的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
discount = None
if value < 100:
discount = 0
elif value < 200:
discount = 10
elif values < 300:
discount = 25
elif values < 400:
discount = 42
elif values < 500:
discount = 53
elif values < 600:
discount = 64
elif values < 700:
discount = 75
elif values < 800:
discount = 86
elif values < 900:
discount = 97
elif values < 1000:
discount = 108
else:
discount = 120

基于bisect的方案

bisect介绍

bisect是python的标准模块,是一个关于数组二分查找法的库,里面提供了在这里非常有用的三个函数bisect_left, bisect_right, bisect. 这三个参数都接受一个array和一个数字,返回将数字插入这个array后这个数字的位置(index),但并不真正执行插入操作。比如:

1
2
3
4
In[0]: import bisect
In[1]: bisect.bisect([1, 3, 5], 2)
Out[1]:
1

表示如果将2插入1 3 5中间,那么插进去之后的index则为返回值(本例,返回值为1),如果出现相同的值,bisect()函数选择将值插在后面也就是原有值的右侧:

1
2
3
4
In[0]: import bisect
In[1]: bisect.bisect([1, 3, 5], 3)
Out[1]:
2

bisect_left()函数选择将值插在前面也就是原有值的左侧:

1
2
3
4
In[0]: import bisect
In[1]: bisect.bisect_left([1, 3, 5], 3)
Out[1]:
1

另外bisect_right()函数是bisect()函数的别名,或者反之。

利用bisect查找整数范围

bisect函数是二分查找,既可以用来插入,当然也可以用来检索信息,比如查找值所属的区段/区间。

前面我们提到的那个函数就可以利用bisect做改写:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
mapping = {
0: 0,
1: 10,
2: 25,
3: 42,
4: 53,
5: 64,
6: 75,
7: 86,
8: 97,
9: 108,
10: 120,
}

i = bisect(range(100, 1001, 100), value)
discount = mapping[i]

这种方案在业务方案多变,查询范围特别多的情况下具备极大的可维护性和性能优势。