kategorisierten Daten generieren aus der Liste in O (n) gesetzt

Question

Ich versuche, einen Datensatz mit folgenden Struktur aus einer Liste von Elementen mit Eigenschaften prop1 und prop2 zu generieren:

result[p1][p2] => list of item with prop1=p1 and prop2=p2

ich in der Lage gewesen, zu tun es in O (n2) mit:

result = { 
    item.prop1: { 
     item.prop2: [ 
      i 
      for i in item_list 
      if i.prop1 == item.prop1 and i.prop2 == item.prop2 
     ] 
    } 
    for item in item_list 
} 

aber habe es nicht in weniger Zeit zu tun in der Lage, einen Weg zu finden. Ist es möglich, dies in O (n) zu erreichen?

Answer 1

Sie sollten nur einmal über die Elemente iterieren haben:

from collections import defaultdict 

result = defaultdict(lambda: defaultdict(list)) 
for item in item_list: 
    result[item.prop1][item.prop2].append(item) 

Answer 2

Eine Lösung mit einem dict (im Gegensatz zu einem defaultdict gegen):

result = {} 
for item in item_list: 
    result.setdefault(item.prop1, {}).setdefault(item.prop2, []).append(item)