Raggruppamento di elemento in una lista data una lista di intervalli

Question

Ho due elenchi di elementi che sembrano

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

a contiene una serie di dati, e b definisce alcuni intervalli, il mio obiettivo è quello di creare una lista c con un numero pari agli intervalli in b. Ogni elenco in c contiene tutti gli elementi x in un valore per cui x[0] è contenuto nell'intervallo. Es:

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

Answer 1

È possibile utilizzare collections.defaultdict e bisect modulo qui:

Come gli intervalli sono continue quindi sarebbe meglio per convertire l'elenco b in qualcosa come questa:

[10, 40, 60, 90, 100] 

Il vantaggio di questo è che ora possiamo usare il modulo bisect per trovare l'indice in cui inserire gli elementi di un elenco. Ad esempio 50 verrà tra 40 e 60 quindi bisect.bisect_right restituirà 2 in questo caso. No, possiamo usare questo 2 come chiave e memorizzare l'elenco come valore. In questo modo possiamo raggruppare gli articoli in base all'indice restituito da bisect.bisect_right.

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

La complessità generale sarà: 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']]] 

Come dicts non hanno alcun uso specifico ordinamento di ottenere un output ordinato:

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

Se gli intervalli sono estremamente grandi, è consigliabile utilizzare xrange invece di range. In realtà, se i tuoi intervalli sono anche moderatamente grandi, considera quanto segue.

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

si potrebbe fare this:

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

Oppure si potrebbe fare questo:

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