2009-11-13 17 views
44

Ich bin neu in Python, und ich bin vertraut mit Implementierungen von Multimaps in otherlanguages. Ist eine solche Datenstruktur in Python integriert oder in einer häufig verwendeten Bibliothek verfügbar?Gibt es in Python eine Multimap-Implementierung?

Um zu zeigen, was ich mit „multimap“ bedeuten:

a = multidict() 
a[1] = 'a' 
a[1] = 'b' 
a[2] = 'c' 

print(a[1]) # prints: ['a', 'b'] 
print(a[2]) # prints: ['c'] 
+2

@ccfenix, fügte ich ein Beispiel von dem, was ich denke, dass Sie wollten. Wenn dies falsch ist, bearbeiten Sie das Beispiel, um das Beispiel zu korrigieren. Ein Beispiel hilft Menschen, Ihre Frage zu beantworten. Sie müssen wissen, wonach Sie suchen. – steveha

+0

yah, genau was ich will, danke steveha! –

+0

http://code.activestate.com/recipes/576835-multimap-associate-multiple-values-to-a-key/ scheint die Syntax zu implementieren, nach der Sie suchen – Chozabu

Antwort

85

So etwas ist in der Standardbibliothek nicht vorhanden. Sie können ein verwenden defaultdict aber:

>>> from collections import defaultdict 
>>> md = defaultdict(list) 
>>> md[1].append('a') 
>>> md[1].append('b') 
>>> md[2].append('c') 
>>> md[1] 
['a', 'b'] 
>>> md[2] 
['c'] 

(statt list Sie können set verwenden, in welchem ​​Fall Sie .add statt .append nennen würde.)


Als Neben : sieh dir diese zwei Zeilen an, die du geschrieben hast:

a[1] = 'a' 
a[1] = 'b' 

Das scheint t o Geben Sie an, dass der Ausdruck a[1] zwei verschiedenen Werten entsprechen soll. Dies ist bei Dictionaries nicht möglich, da ihre Schlüssel eindeutig sind und jeder von ihnen einem einzelnen Wert zugeordnet ist. Was Sie können tun, ist jedoch alle Werte in der Liste mit einem bestimmten Schlüssel, eins nach dem anderen zu extrahieren. Sie können dafür iter gefolgt von aufeinanderfolgenden Aufrufen an next verwenden. Oder Sie können einfach zwei Schleifen verwenden:

>>> for k, v in md.items(): 
...  for w in v: 
...   print("md[%d] = '%s'" % (k, w)) 
... 
md[1] = 'a' 
md[1] = 'b' 
md[2] = 'c' 
-3

Ich verstehe nicht eindeutig die Semantik von Ihrem Beispiel

a[1] = 'a' 
a[1] = 'b' #?? 

Ist zweite Linie a[1] = 'b' sollte das Element an [1] ersetzen. Wenn ja, dann müssen Sie Wörterbuch verwenden. Wenn nicht, müssen Sie das Wörterbuch der Listen verwenden (wie bereits vorgeschlagen)

+4

Lesen Sie, was eine Multi-Map ist: http://www.cplusplus.com/reference/stl/multimap/ – Casebash

1

Derzeit gibt es in den Python-Standard-Bibliotheken keine Multi-Map.

WebOb hat eine MultiDict Klasse, die verwendet wird, um HTML-Formularwerte darzustellen, und es wird von einigen Python Web-Frameworks verwendet, so dass die Implementierung kampferprobt ist.

Werkzeug hat auch eine MultiDict Klasse, und aus dem gleichen Grund.

1

Der Standard Weg, dies in Python zu schreiben, ist mit einem Diktat, dessen Elemente jeweils eine list oder set sind. Als stephan202 says können Sie dies mit einem Standarddict etwas automatisieren, müssen es aber nicht.

Mit anderen Worten würde ich Ihren Code

a = dict() 
a[1] = ['a', 'b'] 
a[2] = ['c'] 

print(a[1]) # prints: ['a', 'b'] 
print(a[2]) # prints: ['c'] 
+0

Warum die Downvotes? Weil es nicht wie ein Diktat aussieht? Ich denke, 'a [1] =' b''als Anhängen zu behandeln, anstatt' a [1] 'zu ersetzen, ist verwirrender als hilfreich. – poolie

+2

Ich habe nicht downvote, aber ich denke, Ihr Vorschlag fügt nichts zur Diskussion hinzu, was die negative Antwort erklären könnte. Sie können sicherlich ein Diktat von Schlüsseln zu Wertelisten verwenden, aber diese manuelle Implementierung ist lästig, wiederholend und etwas fehleranfällig. Eine Multimap, wie [Guavas Multimap] (http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/ArrayListMultimap.html) für Java, ist nichts anderes als eine Liste von Listen , aber es ist enorm praktisch, genau weil es diese Implementierung verbirgt. Ihr Vorschlag ist korrekt, aber es fehlt jede Annehmlichkeit. – dimo414

+3

Der Punkt, den ich versuchte zu machen, was nicht von den anderen gemacht wird, ist: Die Verwendung einer Multimap ist nicht Pythonic. Der idiomatische Weg ist ein Diktat von Sätzen. – poolie

2

Stephan202 hat die richtige Antwort, übersetzen defaultdict verwenden.Aber wenn Sie etwas mit der Schnittstelle von C++ STL multimap und viel schlechtere Leistung möchten, können Sie dies tun:

multimap = [] 
multimap.append((3,'a')) 
multimap.append((2,'x')) 
multimap.append((3,'b')) 
multimap.sort() 

Nun, wenn Sie durch multimap laufen, werden Sie Paare bekommen, wie Sie es in einem std::multimap. Leider bedeutet das, dass Ihr Schleifencode so hässlich wie C++ aussieht.

def multimap_iter(multimap,minkey,maxkey=None): 
    maxkey = minkey if (maxkey is None) else maxkey 
    for k,v in multimap: 
    if k<minkey: continue 
    if k>maxkey: break 
    yield k,v 

# this will print 'a','b' 
for k,v in multimap_iter(multimap,3,3): 
    print v 

Zusammengefasst ist defaultdict wirklich cool und nutzt die Leistung von Python und Sie sollten sie nutzen.

2

oder Unterklasse dict:

class Multimap(dict): 
    def __setitem__(self, key, value): 
     if key not in self: 
      dict.__setitem__(self, key, [value]) # call super method to avoid recursion 
     else 
      self[key].append(value) 
+1

Dies wird sich jedoch nicht wie ein Diktat verhalten. http://stackoverflow.com/questions/3387691/python-how-to-perfectly-override-a-dict – johncip

9

Gerade für zukünftige Besucher. Momentan gibt es eine Python-Implementierung von Multimap. Es ist verfügbar über pypi

+0

"Die definierende Qualität dieses Projekts im Vergleich zu anderen ist, dass Werte, die durch denselben Schlüssel zugeordnet werden, nicht zusammen angeordnet sind." Wie ist das anders als 'defaultdict (set)' '? – Shuklaswag

Verwandte Themen