第一个Python列表索引大于第二个列表中的元素

栏目: 十大 · 发布时间: 2021-04-13

简介  这篇文章主要介绍了第一个Python列表索引大于第二个列表中的元素以及相关的经验技巧,文章约2510字,浏览量131,点赞数2,值得参考!

此问题与此相关:First Python list index greater than x?

我有一个(排序的)浮点数列表,我想找到一个超出第二个列表的每个值的第一个索引

例如

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

如果m是浮点数,我会用这个:

 bisect.bisect_left(l,m)

但是对于m是列表的情况,这将失败,并且我只能考虑采用列表理解:

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

给出:

 [1, 2]

可以,但是我怀疑这对于大型列表来说很慢。有没有一种方法可以有效地做到这一点(因为只需要遍历列表中的一个)?

答案

[好,bisect_left很可能是O(logN)运算(二进制搜索),因此您的整体运算将是O(KlogN) where N relates to size of l, and K relates to size of m

同样对第二个列表m进行了排序,只需在两个列表中同时运行索引,就可以将此操作作为O(N)操作。

但是,如果您的评论是“我怀疑这很慢”,您的第一步应该总是是用最大的预期数据集测试最简单的解决方案”。如果可行,就停在这里!仅当它不足时,您才开始考虑优化。

例如,考虑以下程序:

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)

这将创建一个包含1,000,000个元素的大海捞针和一个包含10,000个元素的针头清单,然后使用您的bisect ing清单理解力来完成工作。使用time在我(不是特别肮脏)的桌面上运行该命令会显示:

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

并且这includes用来构建列表,对大列表进行排序并打印出结果所花费的时间。


使用timeit摆脱所有设置时间可以通过:

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))

一千次迭代的输出为12.27,这意味着您每秒可以执行约75次而不会费力。

另一答案

您必须记住找到的最后一个值,以将其用作下一个二进制搜索的起点,因此,必须使用for循环来代替列表理解:

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

这应该比简单的理解要快。

另一答案

您可以使用:

indices = []

i = 0
for e in m:
    i = bisect.bisect_left(l[i:],e)
    indice.append(i)

以上就是本文的全部内容,希望对大家的学习有所帮助,版权归原作者或者来源机构所有,感谢作者,如果未能解决你的问题,请参考以下文章。

Python数据类型之列表(示例代码)

python 第二章 列表,if循环(示例代码)

day6——Python数据类型(示例代码)

python中的列表list

python中列表类型常用操作(示例代码)