3. Hash-Funktion für arrays bzw. double-werte

Hash-Funktion für arrays bzw. double-werte

  • E

    Warum ein Array: Der gesamtalgorithmus hat halt arrays. Ich werde jetzt sicherlich nicht die gesamten datenstrukturen umbauen. stl::vektoren sind ja im grunde arrays.

    Von mir aus kannst du ja Arrays als Keys nehmen. Zwar schlechtes Design, aber soweit egal.

    Mir geht es eher darum dass eine Hashtable ein unpassender Container ist, wenn du riesige Keys hast.

    Und: Bist du dir sicher, dass die Arrays als SCHLÜSSEL fungieren sollen? Nicht eher als Data?

    0
  • N

    Testo schrieb:

    kann den gesamten code jetzt nicht auf boost umstellen.

    Ich dachte, es ging nur um eine Hash-Funktion?

    Testo schrieb:

    gibts da was?

    TR1.Hash

    Testo schrieb:

    Warum ein Array: Der gesamtalgorithmus hat halt arrays. Ich werde jetzt sicherlich nicht die gesamten datenstrukturen umbauen. stl::vektoren sind ja im grunde arrays.

    Ja, nur ist es im Allgemeinen dumm, in C++ Arrays zu verwenden. Mindestens std::array sollte schon hin 😉

    0
  • K

    Einfach dein double-Array als byte-Array interpretieren und eine der Hashfunktionen von Wikipedia nehmen.

    0
  • ?

    Wie du deine hash-Funktion erstellen kannst, findest du in der Doku.

    danke für den kommentar, allerdings kann ich auf solche hilfe verzichten. meine frage war spezifisch und genau. diese antwort dagegen nicht.

    Ja, nur ist es im Allgemeinen dumm, in C++ Arrays zu verwenden. Mindestens std::array sollte schon hin

    Begründung?

    Ich dachte, es ging nur um eine Hash-Funktion?

    richtig ja. aber wenn ich NUR die eine einzige hash-funktion auf boost setze und deswegen gleich der gesamte code eine abhängigkeit auf boost hat weiss ich nicht ob das sinnvoll ist. ich schaue mir mal TR1.Hash an

    Einfach dein double-Array als byte-Array interpretieren und eine der Hashfunktionen von Wikipedia nehmen.

    puh. ist die reihenfolge der elemente gesichert? Also liefert 0.0,1.0 einen anderen schlüssel als 1.0,0.0 ? genau verstehe ich deinen kommentar jetzt nicht?

    nd: Bist du dir sicher, dass die Arrays als SCHLÜSSEL fungieren sollen? Nicht eher als Data?

    Ja die arrays müssen als schlüssel dienen. Sobald 2 arrays gleich sind passiert etwas. Nur die Überprüfung dass 2 arrays gleich sind ist nicht trivial wie ich finde. Das ganze muss im hash liegen wegen schnellem zugriff.

    0
  • 3

    Testo schrieb:

    danke für den kommentar, allerdings kann ich auf solche hilfe verzichten. meine frage war spezifisch und genau. diese antwort dagegen nicht.

    Meine Antwort war genau genug. Dazu hat Nexus dir den Link gegeben, damit DU dir das aus der Doku rausliest. Ich habe sie kurz aufgeschlagen, selbst im Inhaltsverzeichnis sieht man schon, wo man hin muss.

    Testo schrieb:

    Begründung?

    Wenn du nach ner Begründung dafür fragst und die STL Mist schimpfst, dann lern erst mal C++.
    Ich wette du kommst von Java. Oder vielleicht von C#? Was noch primitiveres? Irgendwas, wo du jeden Scheiß in Form einer Klasse in den Arsch geschoben bekommst.

    0
  • E

    Ja die arrays müssen als schlüssel dienen. Sobald 2 arrays gleich sind passiert etwas. Nur die Überprüfung dass 2 arrays gleich sind ist nicht trivial wie ich finde. Das ganze muss im hash liegen wegen schnellem zugriff.

    Und nochmal: Wie sieht es mit einer normalen Map aus?

    Angenommen du hast große Arrays. Wenn diese sich innerhalb der ersten Elemente unterscheiden(Was der Regelfall ist), ist ein Vergleichen sehr viel billiger als das Hashen des ganzen Arrays. Vor allem Kollisionen werden bei soetwas richtig teuer.

    Probiers doch einfach mal aus was schneller ist, ich tippe gerade stark auf die Lösung ohne Hashtable.

    0
  • ?

    Zu dem Vorschlag TR1.hash.: Einfach container benutzen - aber wie definier ich die hash-funktion? Ähnlich zu hash_map?

    0
  • ?

    Wenn du nach ner Begründung dafür fragst und die STL Mist schimpfst, dann lern erst mal C++.
    Ich wette du kommst von Java. Oder vielleicht von C#? Was noch primitiveres? Irgendwas, wo du jeden Scheiß in Form einer Klasse in den Arsch geschoben bekommst.

    ich will mich nicht auf das niveau herablassen: java habe ich vor 6 jahren hinter mir gelassen genau wie c#. stl ist natürlich kein mist. aber wir wissen alle dass die STL nicht immer das gelbe vom Ei ist.

    Und nochmal: Wie sieht es mit einer normalen Map aus?

    ich weiß jetzt nicht ob ich dich richtig verstehe. du meinst die hash-map aussondern und ne normale map verwenden ohne hash-funktion? wie vergleichst du dann die dobule-elemente? über eine epsilon=1e-16 mittels fabs(vec1[i]-vec2[i])< eps oder so?

    0
  • 3

    Mit std::less<double> 😉

    0
  • ?

    Mit std::less<double>

    Aha. sehe ich das richtig dass mir std::less binär arbeitet und zurückgibt ob 2 typen identisch bzw. kleiner sind? Also wäre das ja genau ein korrektes hilfsmittel mir zu sagen ob 2 double-werte identisch sind auf binärbasis. ist das so?

    0
  • 3

    Nein, std::less vergleich nicht auf Binärbasis. Allerdings mit einem Epsilonvergleich soweit ich weiß. (korrigiert mich, wenn ich falsch liege)

    Edit: Irrtum, scheinbar verwendet std::less<double> den ganz normalen built-in operator <.

    0
  • Mod

    314159265358979 schrieb:

    Edit: Irrtum, scheinbar verwendet std::less<double> den ganz normalen built-in operator <.

    Ja, das ist sozusagen die Definition und der Zweck all dieser Funktionsobjekte.

    Überhaupt, was soll ein Epsilon-Vergleich bei "kleiner" sein? Und woher sollte less ein epsion nehmen?

    0
  • 3

    Es wäre ja denkbar, dass std::less eine Spezialisierung für double hat.

    Epsilon-Vergleich habe ich mich geirrt. Jaja, wieder so ein Post, den ich mir hätte sparen können. Ich weiß schon.

    0
  • K

    Testo schrieb:

    Einfach dein double-Array als byte-Array interpretieren und eine der Hashfunktionen von Wikipedia nehmen.

    puh. ist die reihenfolge der elemente gesichert? Also liefert 0.0,1.0 einen anderen schlüssel als 1.0,0.0 ? genau verstehe ich deinen kommentar jetzt nicht?

    Weisst du was eine Hashfunktion macht und wie sie sich von einer perfekten Hashfunktion unterscheidet? Natuerlich gibt es keine Garantie, aber wit grosser Wahrscheinlichkeit unterscheiden sie sich. Aber wahrscheinlich solltest du wohl auf std::set oder std::map zurueckgreifen (nach deinen Anforderungen zu urteilen). Deine Frage ueber die Reihenfolge verstehe ich nicht, ein reinterpret_cast<int*> veraendert nicht die Reihenfolge.

    0
  • 3

    knivil schrieb:

    Deine Frage ueber die Reihenfolge verstehe ich nicht, ein reinterpret_cast<int*> veraendert nicht die Reihenfolge.

    Verletzt aber die strict aliasing rule (Oder wars doch ne andere? Ist doch egal, irgend ne Regel im Standard wird verletzt!). Daher wenn dann reinterpret_cast<char*> 😉

    0
  • K

    Bei einem double-Array als Ausgangspunkt hoffe ich einfach, dass es aehnlich wie ein int-Array bzw. int64-Array ausgerichtet ist.

    0
  • 3

    Hoffen ist aber nicht standardkonform 😉

    0
  • K

    Dann kuerze es doch ab und zeig mir die entsprechende Stelle ...

    0
  • ?

    Weisst du was eine Hashfunktion macht und wie sie sich von einer perfekten Hashfunktion unterscheidet? Natuerlich gibt es keine Garantie, aber wit grosser Wahrscheinlichkeit unterscheiden sie sich. Aber wahrscheinlich solltest du wohl auf std::set oder std::map zurueckgreifen (nach deinen Anforderungen zu urteilen). Deine Frage ueber die Reihenfolge verstehe ich nicht, ein reinterpret_cast<int*> veraendert nicht die Reihenfolge.

    So wie ich das verstehe ist die funktion zuständig für das mapping der objekte und dem hash. also generiert mir einen schlüssel nachdem dann das element abgelegt wird. perfekt ist keine hash-funktion, zumindest im sinne von kollisionsfreiheit.

    ich glaube ein minimalbeispiel mit dem reinterpret_cast wäre sinnvoll. Bastelst du schnell was?

    0
  • C
    Mod

    knivil schrieb:

    Dann kuerze es doch ab und zeig mir die entsprechende Stelle ...

    3.10 Lvalues and rvalues [basic.lval] Absatz 15 (bzw. Absatz 10 in n3242)

    0
Anmelden zum Antworten