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']]]
Bereiche in 'b 'werden immer kontinuierlich sein? –
ja sie sind, und 'a' wird von _name_ nicht durch das erste Feld des Elements – fady
bisect kann einige Hilfe hier sein – dansalmo