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

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

  • ?

    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
  • 3

    Sag mal camper, kennst du die Stellen eigentlich auswendig, dass du die immer so schnell hast?

    0
  • C
    Mod

    314159265358979 schrieb:

    Sag mal camper, kennst du die Stellen eigentlich auswendig, dass du die immer so schnell hast?

    Diese eine Stelle: ja - kommt oft genug vor. Bei den meisten anderen Dingen weiß ich mittlerweile aber auch i.d.R. ungefähr, wo sie stehen müssten.

    0
  • K

    Habe ich das richtig verstanden:

    1. Es waere in diesem Fall reinterpret_cast<char*> korrekt, so dass kein undefiniertes Verhalten verursacht wird?
    2. Alternativ kann folgendes Union verwendet werden?
    union X {
  double in;
  int64_t out;
};

X converter;
converter.in = vec[i]
int64_t value = converter.out;
    0
  • 3

    1.) Richtig.
    2.) Falsch, aber ich bin mir nicht 100 % sicher. Warte da lieber noch auf camper 🤡

    0
  • C
    Mod

    1. auch das ist UB (wobei gcc über eine Compilererweiterung verfügt, die solches type-punning zulässt, falls ein expliziter Cast verwendet wird - z.B. im Linux-Kernel findet man das oft).
      Das Ganze ist UB, weil nach der Zuweisung in dem union ein double-Wert gespeichert ist, und nur dieser dort existiert (9.5/1), der folgende Zugriff folglich über ein lvalue des Typs int64_t auf einen gespeicherten Wert des Typs double zugreift - und genau das wird durch 3.10/15 verboten.
      Theoretisch müsste allerdings so etwas wie
    union X {
  double in;
  int64_t out;
};

X converter;
converter.in = vec[i];
memmove(&converter.out, &converter.in, sizeof converter);
int64_t value = converter.out;

    erlaubt sein, und wenn der Compiler clever ist, optimiert er das memmove weg.

    0
  • K

    Du bestaetigst meine eigenen Recherchen. Schade, dass es keine "einfache" Moeglichkeit gibt, standardkonform an das Bitmuster eines doubles zu kommen. Ich habe meist den Uniontrick benutzt, aber er ist wohl gcc-spezifisch.

    0
  • B

    An das Bitmuster kommt man schon, notfalls mit

    unsigned char buffer[sizeof double]; 
memcpy(buffer, &meindouble, sizeof double);

    Das Problem ist, dass das als Hashkey keine geeignete Grundlage ist, da doubles gleich sein können ( 0.0 == -0.0 ), obwohl das Bitmuster ungleich ist.

    0
Anmelden zum Antworten