在给定区间列表的情况下，对列表中元素进行分组

Question

我有两个元素列表，看起来像这样

a=[['10', 'name_1'],['50','name_2'],['40','name_3'], ..., ['80', 'name_N']]
b=[(10,40),(40,60),(60,90),(90,100)]

a 包含一组数据，b 定义了一些区间，我的目标是创建一个列表 c，其中包含与 b 中的区间数量相同的列表。每个在 c 中的列表包含所有满足条件 x[0] 在该区间中的 x 元素。例如：

c=[
[['10', 'name_1']],
[['50','name_2'],['40','name_3']],
[...,['80', 'name_N']]
]

- fady

---

b 中的范围总是连续的吗？ - Ashwini Chaudhary

是的，它们是有序的，并且 a 是按名称而不是元素的第一个字段排序的。 - fady

二分法可能会对这里有所帮助。 - dansalmo

Answer 1

c = []
for r in b:
    l = []
    rn = range(*r)
    for element in a:
        if int(element[0]) in rn:
            l.append(element)
    c.append(l)

如果您的间隔非常大，请考虑使用xrange而不是range。实际上，如果您的间隔甚至是适度大的，请考虑以下内容。

c = []
for r in b:
    l = []
    for element in a:
        if r[0] <= int(element[0]) < r[1]:
            l.append(element)
    c.append(l)

- Blair

---

我觉得这样做非常低效，因为我一直在检查已经分配的元素。 - fady

Answer 2

你可以在这里使用 collections.defaultdict 和 bisect 模块：

由于范围是连续的，因此最好先将列表 b 转换为类似于以下内容的形式：

[10, 40, 60, 90, 100]

这样的好处是我们现在可以使用bisect模块来查找列表中项所适合的索引。例如，50将位于40和60之间，因此bisect.bisect_right将在这种情况下返回2。现在我们可以使用这个2作为键并将列表存储为它的值。这样我们就可以根据从bisect.bisect_right返回的索引对这些项进行分组。

L_b = 2* len(b)
L_a = len(a)
L_b1 = len(b1)

总体复杂度将为：max ( L_b log L_b , L_a log L_b1 )

>>> import bisect
>>> from collections import defaultdict
>>> b=[(10,40),(40,60),(60,90),(90,100)]
>>> b1 = sorted( set(z for x in b for z in x))
>>> b1
[10, 40, 60, 90, 100]
>>> dic = defaultdict(list)
for x,y in a:
    #Now  find the index where the value from the list can fit in the 
    #b1 list, bisect uses binary search so this is an O(log n ) step.
    # use this returned index as key and append the list to that key.
    ind = bisect.bisect_right(b1,int(x))
    dic[ind].append([x,y])
...     
>>> dic.values()
[[['10', 'name_1']], [['50', 'name_2'], ['40', 'name_3']], [['80', 'name_N']]]

由于字典没有任何特定顺序，因此使用排序来获得排序输出：

>>> [dic[k] for k in sorted(dic)]
[[['10', 'name_1']], [['50', 'name_2'], ['40', 'name_3']], [['80', 'name_N']]]

- Ashwini Chaudhary

---

谢谢您的建议，我目前正在使用您的答案，因为它给了我更多的灵活性，使用 bisect 真的很有帮助。 - fady

Answer 3

你可以这样做：

>>> a=[['10', 'name_1'],['50','name_2'],['40','name_3'], ['80', 'name_N']]
>>> b=[(10,40),(40,60),(60,90),(90,100)]
>>> c=[]
>>> for t in b:
...    f=list(filter(lambda l: t[0]<=int(l[0])<t[1],a))
...    if f: c.append(f)
... 
>>> c
[[['10', 'name_1']], [['50', 'name_2'], ['40', 'name_3']], [['80', 'name_N']]]

- dawg

---

似乎不需要使用 list()。 - dansalmo

对于 Python 2，你是正确的。但对于 Python 3，在解释器中你只会得到 [<filter object at 0x1084a5710>, <filter object at 0x1084a5750>, ...] 而无法看到结果... - dawg

Answer 4

或者你可以这样做：

>>> a=[['10', 'name_1'],['50','name_2'],['40','name_3'], ['80', 'name_N']]
>>> b=[(10,40),(40,60),(60,90),(90,100)]
>>> filter(None, [filter(lambda l: t[0]<=int(l[0])<t[1], a) for t in b])
[[['10', 'name_1']], [['50', 'name_2'], ['40', 'name_3']], [['80', 'name_N']]]

- dansalmo