Wie kann ich das generieren einer Karte-Schlüssel für diesen Vektor in MATLAB?

Ich habe eine Funktion, die Suche auf eine Anzahl von Elementen. Jedes element ist von der form von einer 8x1-Spalten-Vektor. Jeder Eintrag im Vektor ist eine ganze Zahl kleiner als 1000. Jedes mal, wenn ich sehe, wie ein Vektor, möchte ich hinzufügen, dass es eine Liste der "bereits gesehen" - Vektoren, nach der überprüfung, um zu sehen, dass der Vektor nicht bereits auf dieser Liste. Die Funktion wird prüfen, die auf der Reihenfolge der ~100,000 solcher Vektoren.

Ursprünglich wollte ich mit ismember(v', M, 'rows'), aber fand, dass das sehr langsam. Danach habe ich versucht:

found = containers.Map('KeyType', 'double', 'ValueType', 'any');

Dann jedes mal, wenn ich überprüfen eine neue Vektor - v berechnen:

key = dot(v, [1000000000000000000000 1000000000000000000 1000000000000000 ...
              1000000000000 1000000000 1000000 1000 1]);

Dann schauen Sie isKey(found, key). Wenn der Schlüssel nicht im container, dann found(key) = 1.

Scheint dies wie eine ziemlich miese Lösung, auch wenn es läuft deutlich schneller als ismember. Jede Hilfe/Anregungen würde sehr geschätzt werden.

EDIT: Vielleicht wäre es besser mat2str um den Schlüssel zu generieren, anstatt diese dumme dot product?

  • Sie haben, Sie zu verarbeiten, nacheinander? Sie konnte verketten alle Vektoren in einem 100.000-by-8-array z und call unique(z, 'Zeilen', 'first') auf, um die unterschiedlichen Werte und Indizes des ersten Vorkommens der einzelnen.
  • Das dot-Produkt-hash ist schneller als mat2str, aber Sie haben hash-Kollisionen aufgrund von Rundungsfehlern, da die hash-Bereich fällt die relative Präzision der double geben. E. g. die hashes für die [999 1 1 1 1 1 1 1] und [999 1 1 1 1 1 1 2] durch [999 1 1 1 1 1 1 100] kollidieren werden. Mat2str basierte hashes haben dieses problem nicht. Und mat2str ist ziemlich schnell hier ~80 usec für mich. Versuchen Sie, Zeitmessung Ihren Kandidaten-hash-Funktionen mit tic/toc, und das Profil der ganzen Sache. Klingt vernünftig zu mir.
InformationsquelleAutor Eric | 2011-07-19
  1. 1

    Der einfachste Weg, um einen Schlüssel erzeugen/hash in deinem Fall wäre zu einfach konvertieren den Vektor von integer-Werte zu einem Zeichen-array verwenden char. Da Ihr integer-Werte nie über 1000, und char akzeptieren können numerische Werte von 0 bis 65535 (entsprechende Unicode-Zeichen), dieser wird Ihnen eine einzigartige 8-stellige Schlüssel für jede einzigartige 8-by-1-Vektor. Hier ist ein Beispiel:

    found = containers.Map('KeyType', 'char', 'ValueType', 'any');

v = randi(1000, [8 1]);  % Sample vector
key = char(v);
if ~isKey(found, key)
  found(key) = 1;
end
    InformationsquelleAutor gnovice
  2. 0

    deine Idee ist gut. aber Sie brauchen, um zu finden, eine bessere hash-Funktion. verwenden Sie einige standard-hash-Funktion.
    Es ist eine Umsetzung von 'sha' algorithmen, die Sie zu sehen:

    http://www.se.mathworks.com/matlabcentral/fileexchange/31795-sha-algorithms-160224256384-512

    Wenn Sie den sha-Algorithmus langsam, dann kann man wahrscheinlich resort zu einigen tricks. Eine, an die ich gerade denke ist folgende:

    1. nehmen eine Anzahl Samen > 1000 z.B. 1024
    2. unterteilen jede Zahl im Vektor durch die Samen und speichern Sie den Rest in einen string.
    3. verketten alle die Reste, die Ihnen als 'code' für Ihre-Vektor-element. das kann für den Vergleich verwendet werden, wenn Sie sehen ein neues element.

    sollte dies wohl funktionieren, aber Sie werden zu prüfen haben.

    • Ich werde gehen auf ein Glied hier und sagen, "don' T download roll-your-own crypto-code aus dem web". Sie können call Java standard java.security.MessageDigest Klasse direkt aus Matlab, mit typecast(v,'int8') zu konvertieren Matlab double array an Java byte[], dann dec2hex die Antwort, wenn Sie es brauchen, in string-form. Es ist wahrscheinlich schneller und richtiger, dass die fileexchange-version.
    • Aufruf von Java standard java.security.MessageDigest ist wahrscheinlich nicht schneller sein, zumindest, Sie haben zu tun, einige tweaks für die. Für die Referenz können Sie die folgenden links: mathworks.com/matlabcentral/newsreader/view_thread/281221 mathworks.com/matlabcentral/newsreader/view_thread/...
    • Es ist ein gewisser Aufwand in die Java-Aufrufe, aber bezahlen Sie nur es ein paar mal pro hash-Berechnung. Dies wird aufgewogen durch die Tatsache, dass die fileexchange-Funktion verknüpft ist, wie viel die roll-your-own crypto-code auf dem web, niedrige Qualität. Bei der Prüfung, ich musste es ändern, um nutzbar zu sein, und ein einfaches java.Sicherheit.MessageDigest basierte Implementierung war 600x schneller, tut Eric ist 8-lange Vektoren in etwa .0001 Sek vs .6700 Sek. "Java in Matlab ist langsam" ist eine starke Vereinfachung.
    • +1 dass tatsächliche Ergebnisse. Dank
    • Kryptographische hashes sind völlig unangebracht, Wörterbuch Schlüssel, denn Sie sind entworfen, um langsam, um brute-force-Attacken teurer.
    • Wie sieht das Skript aus, das Sie link eigentlich funktioniert? Ich Lesen Sie die Dokumentation, für die es aber nicht bekommen kann es arbeiten, welche Eingänge soll das sein? Intuitiv, Eingang sollte das sein, was Nachricht, die Sie haben und die Spezifikation, welche hash-Funktion, die Sie verwenden möchten, aber das Skript hat drei Eingänge, und nicht akzeptieren hash(-,SHA256 -, -) trotz sagen, dass SHA256 ist eine gültige Eingabe.

    InformationsquelleAutor A. K.
  3. 0

    Nicht wirklich in hashing, aber immer noch glauben gefunden zu haben, der einfachste Weg, um Ihr problem zu lösen.

    Dieser läuft etwa 10x schneller als ismember.

    any(v(1)==M(1)&v(2)==M(2)&v(3)==M(3)&v(4)==M(4)&v(5)==M(5)&v(6)==M(6)&v(7)==M(7)&v(8)==M(8));
    InformationsquelleAutor Dennis Jaheruddin
Schreibe einen Kommentar