2013-06-27 7 views
5

Ich habe zwei Listen von Elementen, dieGruppierung von Elemente in einer Liste gegeben eine Liste von Intervallen

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

a aussehen enthält eine Reihe von Daten und b definiert einige Intervalle, mein Ziel ist es, eine Liste zu erstellen, c mit so vielen Listen wie die Intervalle in b. Jede Liste in c enthält alle x Elemente in einer, für die x[0] im Intervall enthalten ist. Ex:

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

Bereiche in 'b 'werden immer kontinuierlich sein? –

+0

ja sie sind, und 'a' wird von _name_ nicht durch das erste Feld des Elements – fady

+0

bisect kann einige Hilfe hier sein – dansalmo

Antwort

1

können Sie verwenden collections.defaultdict und bisect Modul hier:

Da die Bereiche kontinuierlich sind, so dass es besser wäre, die Liste b in so etwas wie dieses erste zu konvertieren:

[10, 40, 60, 90, 100] 

Der Vorteil Dies ist, dass wir jetzt bisect Modul verwenden können, um den Index zu finden, wo die Elemente aus einer Liste passen können. Zum Beispiel 50 wird zwischen 40 und 60 kommen, so bisect.bisect_right wird 2 zurückgeben in diesem Fall. Nein, wir können diese 2 als Schlüssel verwenden und speichern die Liste als Wert. Auf diese Weise können wir diese Elemente basierend auf dem von bisect.bisect_right zurückgegebenen Index gruppieren.

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

Die Gesamtkomplexität sein wird: 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']]] 

Als dicts haben keine bestimmte Reihenfolge eine sortierte Ausgabe erhalten Verwendung Sortierung:

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

Vielen Dank für den Vorschlag, ich benutze derzeit Ihre Antwort, da es mir mehr Flexibilität gibt, ist die Verwendung von Halbierung wirklich hilfreich. – fady

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) 

Wenn Ihre Intervalle extrem groß sind, sollten xrange statt range verwenden. Wenn Ihre Intervalle sogar moderat sind, sollten Sie Folgendes berücksichtigen.

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

Ich finde dies wirklich ineffizient in Bezug auf die Zeit, wie ich überprüfte Elemente, die bereits zugewiesen wurden . – fady

0

Sie tun können dies:

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

'list()' scheint nicht benötigt zu werden. – dansalmo

+0

Für Python 2 haben Sie Recht. Für Python 3 im Interpreter ist es oder Sie erhalten nur '[, , ...]' und können die Ergebnisse nicht sehen ... – dawg

0

Oder Sie könnten dies tun:

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