Gibt es eine Multimap-Implementierung in Python?

74

Ich bin neu in Python und mit der Implementierung von Multimaps in anderen Sprachen vertraut . Ist in Python eine solche Datenstruktur integriert oder in einer häufig verwendeten Bibliothek verfügbar?

Um zu veranschaulichen, was ich mit "Multimap" meine:

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

print(a[1])  # prints: ['a', 'b']
print(a[2])  # prints: ['c']
James Bond
quelle
3
@ccfenix, ich habe ein Beispiel hinzugefügt, was ich denke, dass Sie wollten. Wenn dies falsch ist, bearbeiten Sie es bitte, um das Beispiel zu korrigieren. Ein Beispiel hilft Menschen, Ihre Frage zu beantworten. Sie müssen wissen, wonach Sie suchen.
Steveha
yah, genau das was ich will, danke steveha!
James Bond
code.activestate.com/recipes/… scheint die Syntax zu implementieren, nach der Sie
suchen
1
Die Verwendung a[1] = 'b'des Anhängens an eine [1] ist für Benutzer, die diesen Code lesen oder pflegen, verwirrend. Ich würde empfehlen, dies nicht in Python zu tun.
Poolie

Antworten:

123

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

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

(Anstelle von listmöchten Sie möglicherweise verwenden set, in welchem ​​Fall Sie .addanstelle von anrufen würden .append.)


Nebenbei : Sehen Sie sich diese beiden Zeilen an, die Sie geschrieben haben:

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

Dies scheint darauf hinzudeuten, dass der Ausdruck a[1]zwei unterschiedlichen Werten entsprechen soll. Dies ist bei Wörterbüchern nicht möglich, da ihre Schlüssel eindeutig sind und jeder von ihnen einem einzelnen Wert zugeordnet ist. Sie können jedoch nacheinander alle Werte in der Liste extrahieren, die einem bestimmten Schlüssel zugeordnet sind. Sie können dafür itergefolgt von aufeinanderfolgenden Aufrufen verwenden next. 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'
Stephan202
quelle
9

Nur für zukünftige Besucher. Derzeit gibt es eine Python-Implementierung von Multimap. Es ist über Pypi erhältlich

Michal
quelle
2
"Die entscheidende Qualität dieses Projekts im Vergleich zu anderen ist, dass Werte, die mit demselben Schlüssel zugeordnet wurden, nicht zusammen geordnet werden." Wie unterscheidet sich das von der Verwendung defaultdict(set)?
Shuklaswag
Auf Ihrem Link steht nicht "bestellt", sondern "gruppiert". Es handelt sich also nicht um eine Menge, da dasselbe Element zweimal eingefügt werden kann. Es verhält sich eher wie eine sortierte Liste, denke ich.
Eyal
4

Stephan202 hat die richtige Antwort, benutze defaultdict. Wenn Sie jedoch etwas mit der Schnittstelle von C ++ STL Multimap und einer viel schlechteren Leistung wünschen, können Sie dies tun:

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

Wenn Sie jetzt durchlaufen multimap, erhalten Sie Paare wie in einem std::multimap. Leider bedeutet dies, dass Ihr Schleifencode so hässlich aussieht wie C ++.

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

Zusammenfassend defaultdictist es wirklich cool und nutzt die Kraft von Python und Sie sollten es verwenden.

amwinter
quelle
4

Sie können eine Liste von Tupeln erstellen und diese dann sortieren, als wäre es eine Multimap.

listAsMultimap=[]

Fügen wir einige Elemente (Tupel) hinzu:

listAsMultimap.append((1,'a'))
listAsMultimap.append((2,'c'))
listAsMultimap.append((3,'d'))
listAsMultimap.append((2,'b'))
listAsMultimap.append((5,'e'))
listAsMultimap.append((4,'d'))

Jetzt sortiere es.

listAsMultimap=sorted(listAsMultimap)

Nach dem Drucken erhalten Sie:

[(1, 'a'), (2, 'b'), (2, 'c'), (3, 'd'), (4, 'd'), (5, 'e')]

Das heißt, es funktioniert als Multimap!

Bitte beachten Sie, dass wie bei Multimap hier auch Werte in aufsteigender Reihenfolge sortiert werden, wenn die Schlüssel gleich sind (für Schlüssel = 2 steht 'b' vor 'c', obwohl wir sie nicht in dieser Reihenfolge angehängt haben.)

Wenn Sie sie in absteigender Reihenfolge erhalten möchten, ändern Sie einfach die Funktion sortiert () wie folgt:

listAsMultimap=sorted(listAsMultimap,reverse=True)

Und nachdem Sie folgende Ausgabe erhalten haben:

[(5, 'e'), (4, 'd'), (3, 'd'), (2, 'c'), (2, 'b'), (1, 'a')]

In ähnlicher Weise sind hier die Werte in absteigender Reihenfolge, wenn die Schlüssel gleich sind.

hafiz031
quelle
Dies ist NICHT dasselbe wie eine Multimap, bei der O (1) Kosten entstehen. Das obige ist O (NlogN).
user48956
@ user48956, ich denke du wirst zwischen unordered_multimap und multimap verwechselt. Multimap hat eine Komplixität von O (NlogN) und NICHT O (1). Die obige Implementierung gilt für Multimap und NICHT für unordered_multimap, bei dem Hashing zur Reduzierung der Zeitkomplexität verwendet wird und die im Durchschnitt eine konstante durchschnittliche Zeitkomplexität aufweist. Finden Sie die Unterschiede hier: ( en.cppreference.com/w/cpp/container/multimap ) und hier: ( cplusplus.com/reference/unordered_map/unordered_multimap )
hafiz031
3

Die Standardmethode zum Schreiben in Python ist ein Diktat, dessen Elemente jeweils ein listoder sind set. Wie stephan202 sagt , können Sie dies mit einem Standarddikt etwas automatisieren, müssen es aber nicht.

Mit anderen Worten, ich würde Ihren Code in übersetzen

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

print(a[1])  # prints: ['a', 'b']
print(a[2])  # prints: ['c']
Poolie
quelle
Warum die Abstimmungen? Weil es nicht genug wie ein Diktat aussieht? Ich denke , es ist eher verwirrend als hilfreich , a[1] = 'b'als Anhängen zu behandeln, anstatt es zu ersetzen a[1].
Poolie
2
Ich habe nicht abgelehnt, aber ich denke, Ihr Vorschlag fügt der Diskussion nichts hinzu, was die negative Reaktion erklären könnte. Sie können sicherlich ein Diktat von Schlüsseln für Wertelisten verwenden, aber diese manuelle Implementierung ist ärgerlich, sich wiederholend und etwas fehleranfällig. Eine Multimap wie Guavas Multimap für Java ist nichts anderes als eine Karte mit Listen, aber sie ist äußerst praktisch, gerade weil sie diese Implementierung verbirgt. Ihr Vorschlag ist korrekt, aber es fehlt ihm jede Bequemlichkeit.
dimo414
4
Der Punkt, den ich ansprechen wollte, der nicht von den anderen gemacht wird, ist: Die Verwendung einer Multimap ist nicht pythonisch. Der idiomatische Weg ist ein Diktat von Mengen.
Poolie
Ich mag die Diskussion über Python. Ich vermute, dass @ dimo414 aus Java und Perl stammt und damit zu tun hat, dass die Liste beim Hinzufügen eines neuen Schlüssels instanziiert wird. Die Antwort hätte das Pythonische in dieser Hinsicht erweitern können.
Chris
... ging und schaute sich defaultdict genauer an und mochte es als Lösung. Ich würde vermuten, dass die Abstimmungen darauf zurückzuführen sind, dass Sie nicht die Liste erstellt haben, die defaultdict für Sie erstellt.
Chris
3

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)
Jay
quelle
2
Dies wird sich jedoch nicht genau wie ein Diktat verhalten. stackoverflow.com/questions/3387691/…
Johncip
2

Derzeit gibt es in den Python-Standardbibliotheken keine Multi-Map.

WebOb verfügt über eine MultiDict- Klasse, die zur Darstellung von HTML-Formularwerten verwendet wird. Sie wird von einigen Python-Webframeworks verwendet, sodass die Implementierung kampferprobt ist.

Aus dem gleichen Grund hat Werkzeug auch eine MultiDict- Klasse.

Luciano Ramalho
quelle
-4

Ich verstehe die Semantik Ihres Beispiels nicht klar

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

Soll die zweite Zeile a[1] = 'b'das Element bei [1] ersetzen? Wenn ja, müssen Sie ein Wörterbuch verwenden. Wenn nicht, müssen Sie ein Listenwörterbuch verwenden (wie bereits vorgeschlagen).

BostonLogan
quelle