MemberQ in Mathematica
Ich bin ein bisschen ratlos, wie man in Mathematica das Folgende effizient macht:
%Vor%Erwartete Ausgabe ist:
%Vor% Meine Listen a und b sind groß, also macht Mathematica eine kazillion lineare Suche durch b . Ich möchte, dass es schnellere Lookups mit einer Hashtabelle macht. Aber es scheint keine solche Struktur zu geben. Der nächste, den ich finden konnte, ist ein SparseArray, aber
ist False .
Ich bin mir sicher, dass dies in Mathematica in einer Zeile Code oder weniger möglich sein muss, ich kann es einfach nicht für die Bäume sehen oder so etwas.
Jeder Held zur Rettung? In der Zwischenzeit mache ich das mit C #.
3 Antworten
Eine andere Idee wäre, Regeln und Dispatch zu verwenden. Es scheint schneller zu sein, wenn die Länge des Blist groß ist:
Auf meinem Laptop, Regeln (0,06s) & lt; fct (0,09 s) & lt; spärlich (0,9 s) & lt; membQ (40s).
Bearbeiten / Vergleichen von Fct- und Regelzeiten
@Karsten zögern Sie nicht, zu Ihrer ursprünglichen Antwort zurückzukehren
Tabellen, die mit Prime erstellt wurden [...]
Mit RandomInteger erzeugte Tabellen [...]
Die folgende Frage entspricht Ihrer und enthält eine Antwort in Mathematica:
Hier ist diese Antwort (die ich gerne stehlen werde, weil sie wirklich meine ist):
%Vor%Die Idee besteht darin, eine Hash-Tabelle f zu erstellen, die in konstanter Zeit antworten kann, ob ein bestimmtes Element ein Mitglied der Liste b ist. Zuerst wird f der Standardwert False zugewiesen (wenn wir es nicht gesehen haben bevor es nicht in b ist). Dann wird ein einzelner Durchlauf durch die Liste b gemacht, wobei für jedes i in b f [i] auf Wahr gesetzt wird. Das ist alles eingerichtet. Jetzt gibt uns ein einziger Durchlauf der Hash-Funktion f über die Liste a die Antwort. Gesamtzeit ist O (n + m) - ein Durchlauf durch jede Liste.
Das durch lineare Suche konstruierte filter kann vereinfacht werden zu:
Wie auch immer, du könntest ein spärliches Array von b erstellen mit:
%Vor% Dann wird für die Indizes i im Sparse-Array s[[i]] den Wert True und für die Outside s[[i]] den Wert False zurückgeben. Die Liste kann also mit
Wir können die Ergebnisse vergleichen:
%Vor%Tags und Links wolfram-mathematica hashtable