Группировка элементов в списке имеется список интервалов

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 в a, для которых x[0] содержится в интервале. Пример:

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

Answer 1

Вы можете использовать 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']]] 

Как dicts не имеет какого-либо конкретного использования порядка сортировки, чтобы получить отсортированный вывод:

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

Answer 2

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) 

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']]] 

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']]]