在Python中使用列表和字典进行数值比较来优化循环效率

Question

我有一个列表，其中的数字是一个整数：candidates = [1, 2 ,3, 4 , 5, 16, 20]。此列表可以包含100万个以上的项目。

我有一个字典number_ranges，它的关键字是一个整数，列表是一个值，其中包含具有最小和最大范围的对象。这本词典现在由大约500k个关键字组成。

{
    {5: [{"start": 0, "end": 9}]},
    {16: [{"start": 15, "end": 20}, {"start": 16, "end": 18}]}
}

我现在正在遍历这个列表：

for candidate in candidates:
    number = search_in_range(candidate, number_ranges)

其中，我检查在number_ranges的范围内是否有多个candidates匹配，如果匹配，则返回将在以后使用的键。

def search_in_range(candidate, number_ranges):
    for number_range_key in number_ranges:
        for number in number_ranges[number_range_key]:
            if int(number['start']) <= candidate <= int(number['end']):
                return {"key": number_range_key, "candidate": candidate}

当我运行这个程序时，我发现处理列表中的1000个数字大约需要40秒。这意味着如果我有一百万个数字，我需要超过11个小时来处理。

('2018-12-19 16:22:47', 'Read', 1000)
('2018-12-19 16:23:30', 'Read', 2000)
('2018-12-19 16:24:10', 'Read', 3000)
('2018-12-19 16:24:46', 'Read', 4000)
('2018-12-19 16:25:26', 'Read', 5000)
('2018-12-19 16:25:59', 'Read', 6000)
('2018-12-19 16:26:39', 'Read', 7000)
('2018-12-19 16:27:28', 'Read', 8000)
('2018-12-19 16:28:15', 'Read', 9000)
('2018-12-19 16:28:57', 'Read', 10000)

预期的输出是从number_ranges返回在范围内匹配的键和用于查找该键的candidate号，即函数search_in_range中的return {"key": number_range_key, "candidate": candidate}。

在Python中有什么推荐的方法来优化这个算法？

Answer 1

您的候选字典列表已排序，因此执行相反的操作:在number_ranges中循环字典，并使用bisect对匹配的候选项进行二进制搜索。这将平均降低从O(n*m)到O(n*logm*k)的n字典、m候选和k匹配候选的复杂度。

(注意:我将number_ranges的格式从每个只有一个元素的dict set更改为只有一个dict，这更有意义。)

candidates = [1, 2, 3, 4, 5, 16, 20]
number_ranges = {
    5: [{"start": 0, "end": 9}],
    16: [{"start": 15, "end": 20}, {"start": 16, "end": 18}]
}

import bisect

for key, values in number_ranges.items():
    for value in values:
        start, end = value["start"], value["end"]
        lower = bisect.bisect_left(candidates, start)
        upper = bisect.bisect_right(candidates, end)
        for cand in range(lower, upper):
            res = {"key": key, "candidate": candidates[cand]}
            print(value, res)

输出：

{'start': 0, 'end': 9} {'key': 5, 'candidate': 1}
{'start': 0, 'end': 9} {'key': 5, 'candidate': 2}
{'start': 0, 'end': 9} {'key': 5, 'candidate': 3}
{'start': 0, 'end': 9} {'key': 5, 'candidate': 4}
{'start': 0, 'end': 9} {'key': 5, 'candidate': 5}
{'start': 15, 'end': 20} {'key': 16, 'candidate': 16}
{'start': 15, 'end': 20} {'key': 16, 'candidate': 20}
{'start': 16, 'end': 18} {'key': 16, 'candidate': 16}

如果candidates实际上没有排序，或者如果您希望按候选而不是字典对结果进行排序，则可以将其作为预处理或后处理步骤进行排序。

Answer 2

稍微重新组织一下，你的代码就会变成一个经典的区间树问题。

看一下这个包https://pypi.org/project/intervaltree/

与普通区间树的唯一不同之处在于，您有一些涵盖多个区间的项目，但是将它们分为多个区间非常容易，例如{16.1：{"start"：15，"end"：20}，16.2：{"start"：16，"end"：18}}

通过使用intervaltree包，可以创建一个平衡的二进制搜索树，这比使用嵌套for循环效率高得多。这个解决方案是O(logn)，用于搜索每个候选者，而for循环是O(n)。如果有1MM+候选者，intervaltree包将比公认的嵌套for循环答案快得多。

Answer 3

尽管这个问题有一个公认的答案，但为了其他人的缘故，我想补充说，这种类型的场景确实证明了创建反向查找的合理性。随着候选列表的增加，这是一个令人头疼的问题，这将节省大量的实际时间。字典查找是O(1)，如果您需要执行多个查找，您也应该考虑创建一个反向映射。

number_ranges = [
    {5: [{"start": 0, "end": 9}]},
    {16: [{"start": 15, "end": 20}, {"start": 16, "end": 18}]}
]

from collections import defaultdict

reversed_number_ranges = defaultdict(set) #returns an empty set, avoiding key errors.


for number in number_ranges:
    for k,v in number.items(): 
        ranges = set() #create a set of values which fall within range
        for range_dict in v:
            ranges.update(range(range_dict["start"], range_dict["end"] + 1)) #assuming "end" is included. remove the +1 for right exclusive.
        for i in ranges:
            reversed_number_ranges[i].add(k) #add the key for each location in a range.


candidates = [1, 2 ,3, 4 , 5, 16, 20]

for candidate in candidates:
    print(candidate, reversed_number_ranges[candidate])

输出：

1 {5}
2 {5}
3 {5}
4 {5}
5 {5}
16 {16}
20 {16}