快速检查数字列表中的数字是否在给定范围内的方法

Question

我可以这样列出一组字典：

list1 = [{'some_id': 1, 'lower_range': 3, 'upper_range': 7},
         {'some_id': 2, 'lower_range': 8, 'upper_range': 12},
         {'some_id': 3, 'lower_range': 13, 'upper_range': 16}]

第二个列表包含一些整数：

list2 = [{'value': 4, 'data': 'A'},
         {'value': 8, 'data': 'B'},
         {'value': 9, 'data': 'C'},
         {'value': 15, 'data': 'D'}]

我现在想要将'some_id'和'data'合并在一起，使得'value'在'lower_range'和'upper_range''之间，并生成新列表。也就是说，我希望输出结果为：

list3 = [{'some_id': 1, 'data': 'A'},
         {'some_id': 2, 'data': 'B'},
         {'some_id': 2, 'data': 'C'},
         {'some_id': 3, 'data': 'D'}]

有一种方法可以实现这个目标：

list3 = []
for i in list1:
    for j in list2:
        if (j['value'] >= i['lower_range'] and
            j['value'] <= i['upper_range']):
            list3.append({'some_id': i['some_id'], 'data': j['data']})

然而，这种方法似乎非常低效。有没有更快的方法？

- matnor

---

当list1中的范围重叠时，应该发生什么？ - Mr. T

list2 正确吗？目前这是一个包含字典的列表。 - set0gut1

每个人都会有一个匹配吗？还是零个/多个匹配是可能的？ - Reut Sharabani

@Reut Sharabani：不应该出现多个匹配项。而且很可能也不会出现零匹配项。 - matnor

list1和list2是否以任何方式进行了预处理？换句话说，这些数据值是否具有保证的属性？特别地，list1是否已排序，使得范围按递增顺序且没有重叠，并且list2是否也已排序，使得value的值递增？（例如，list2可以包含一个有序字典。）如果是这样，那么有一种简单快速的算法可以实现此目的。如果不是，则可以先对这些值进行排序。 - Rory Daulton

Answer 1

这段代码有些啰嗦，但应该会更高效一些（O(nlogn) < O(n^2)），因为它使用了排序（你也可以使用 list.sort 进行原地排序）：

#!/usr/bin/env python
from operator import itemgetter

list1 = [{'some_id': 1, 'lower_range': 3, 'upper_range': 7},
        {'some_id': 2, 'lower_range': 8, 'upper_range': 12},
        {'some_id': 3, 'lower_range': 13, 'upper_range': 16}]

list2 = [{'value': 4, 'data': 'A'},
        {'value': 8, 'data': 'B'},
        {'value': 9, 'data': 'C'},
        {'value': 15, 'data': 'D'}]

# sort before merging so we iterate less (O(nlogn))
list1 = sorted(list1, key=itemgetter('lower_range'))
list2 = sorted(list2, key=itemgetter('value'))


it1 = iter(list1)
it2 = iter(list2)

# merge lists that we know are sorted (simple merging algorithm - O(n))
try:
    curr_range = next(it1)
    curr_val = next(it2)
    list3 = []
    while True:
        rng = range(curr_range['lower_range'], curr_range['upper_range'] + 1)
        value = curr_val['value']
        if value in rng:
            # got a match, add it and check if there are more values
            list3.append({'some_id': curr_range['some_id'],
                          'data': curr_val['data']})
            curr_val = next(it2)
            continue
        if value < curr_range['lower_range']:
            # no match, skip to next value
            curr_val = next(it2)
            continue
        if value >= curr_range['upper_range']:
            # range too low for value, try next one
            curr_range = next(it1)
            continue
except StopIteration:
    pass
print(list3)

提供：

[{'data': 'A', 'some_id': 1},
 {'data': 'B', 'some_id': 2},
 {'data': 'C', 'some_id': 2},
 {'data': 'D', 'some_id': 3}]

- Reut Sharabani

---

你说得对！我在 OP 的代码中没有注意到那个。 - Reut Sharabani

如果你像这样写代码，它就可以变得更短：http://dpaste.com/0CMV249。 - Aran-Fey

这段代码比我在原始帖中的代码快了大约50倍。 - matnor

Answer 2

有一个特殊前提，即范围不重叠。因此，我们可以通过查找满足条件的具有最大下限的元素来找到候选者。

二分搜索可以将复杂度从 O(n*n) 降至 O(n log n)。在Python3中，我们可以使用bisect。

list1 = [{'some_id': 1, 'lower_range': 3, 'upper_range': 7},
         {'some_id': 2, 'lower_range': 8, 'upper_range': 12},
         {'some_id': 3, 'lower_range': 13, 'upper_range': 16}]

list2 = [{'value': 4, 'data': 'A'},
         {'value': 8, 'data': 'B'},
         {'value': 9, 'data': 'C'},
         {'value': 15, 'data': 'D'}]

list3 = []

list1.sort(key = lambda r: r['lower_range'])
lower_ranges = [r['lower_range'] for r in list1]

from bisect import bisect_right

for record in list2:
    position = bisect_right(lower_ranges, record['value']) - 1
    if (position < 0): continue
    candidate = list1[position]
    if (record['value'] <= candidate['upper_range']):
        list3.append({'some_id': candidate['some_id'], 'data': record['data']})

print(list3)

输出（手动缩进）

[{'some_id': 1, 'data': 'A'},
 {'some_id': 2, 'data': 'B'},
 {'some_id': 2, 'data': 'C'},
 {'some_id': 3, 'data': 'D'}]

- set0gut1

---

这是最快的解决方案，比Reut Sharabani的答案略快。 - matnor

Answer 3

您可以创建一个将值映射到ID的字典，例如{3: 1, 4: 1, 5: 1, ..., 8: 2, 9: 2, ...}，这样您就可以在常数O(1)时间内查找每个字典的ID：

# create a dict that maps values to ids
value_to_id_dict = {}
for dic in list1:
    id_ = dic['some_id']
    for value in range(dic['lower_range'], dic['upper_range']+1):
        value_to_id_dict[value] = id_

# look up each dict's id in the dict we just created
list3 = []
for dic in list2:
    new_dic = {'data': dic['data'],
               'some_id': value_to_id_dict[dic['value']]}
    list3.append(new_dic)

# result:
# [{'data': 'A', 'some_id': 1},
#  {'data': 'B', 'some_id': 2},
#  {'data': 'C', 'some_id': 2},
#  {'data': 'D', 'some_id': 3}]

- Aran-Fey

---

需要注意的是，这将为 {'lower_range': 0, 'upper_range': 1000000} 创建约 100000 条条目... - Reut Sharabani

没有看到那里的 +1 呢 :P 添加了一个近似值，这样我们就不会挑剔了 :D - Reut Sharabani

这段代码比我在原帖中写的代码快了大约25倍。 - matnor