Doppelte Koordinaten entfernen



  • SeppJ schrieb:

    Entweder indem du eine Spezialisierung für std::hash schreibst (weil std::hash die Defaultfunktion ist) oder indem du eine passende Funktion an das unordered_set übergibst. Ich verstehe nicht, wie du auf den Operator size_t kommst.

    Okay kann ich machen. Als ich ein insert in das std::unordered_set programmiert hatte, gab es fehlermeldungen, dass der operator size_t und == fehlt, also habe ich sie nachimplementiert.

    SeppJ schrieb:

    Kommt drauf an.

    Ich bräauchte Eindeutigkeit bis in die vierte Dezimalstelle. Der Quellcode ist mal schnell zusammengestaucht, da kommen einiges an Fehlern auf.

    SeppJ schrieb:

    In anderer Sache: Deine Vergleichsfunktion sieht komisch aus. Wieso ist das nicht einfach Folgendes?

    Es handelt sich um mehrere Klassen, Einmal Integer und einmal Double für Subpixelgenauigkeiten. Eigentlich sollte operator == im return statement mit einem eps wert vergleichen.



  • Skym0sh0 schrieb:

    Also ein guter Hash wäre das verketten der Koordinatenwerte.

    Nehmen wir an die rows und cols gehen nur bis bis zu einem gewissen Wert kleiner als ein halbes std::size_t: Dann könntest du row auf die ersten Bits packen und die Cols auf die hinteren Bits, fertig.

    Davon kann ich leider nicht ausgehen. Jetzt in diesem kleinen Beispiel ist es okay. In der Praxis kommen da auch schonmal double Zahlen vor.


  • Mod

    asdasdasd schrieb:

    SeppJ schrieb:

    Kommt drauf an.

    Ich bräauchte Eindeutigkeit bis in die vierte Dezimalstelle.

    😕 Bist du der Meinung, das unordered_set würde nicht funktionieren, wenn es eine Kollision gibt? Es wird nur weniger effizient.

    Der hash gibt dem set einen Ratschlag, in welche Schublade es einen Wert packen soll. Wenn es in einer Schublade mehrere Werte geben sollte, dann wird der Vergleichsoperator herangezogen, um festzustellen, ob die Werte identisch sind oder nicht. Je weniger häufig dies passiert, desto besser die Performance. Die Hashfunktion sollte also möglichst so gewählt werden, dass es wenig Überschneidungen gibt.

    Davon kann ich leider nicht ausgehen. Jetzt in diesem kleinen Beispiel ist es okay. In der Praxis kommen da auch schonmal double Zahlen vor.

    Deswegen schreiben wir die ganze Zeit "kommt drauf an". Wir können dir keinen konkreten Ratschlag zu einer Hashfunktion anhand eines abstrakten Beispiels geben. Wie oben erläutert, sollte die Hashfunktion auf die zu erwartenden Werte optimiert sein.

    Wie ist das eigentlich von dir gemeint? Sollen verschiedenartige (int, double) Koordinatenpaare zusammen gespeichert werden? Das klingt unheimlich.



  • SeppJ schrieb:

    Bist du der Meinung, das unordered_set würde nicht funktionieren, wenn es eine Kollision gibt? Es wird nur weniger effizient.

    Da bin ich wohl in eine Falle getappt, dachte nämlich das bereits existierende Werte nicht übernommen werden. Dann hilft wohl nur der Pythagoras.

    SeppJ schrieb:

    Wie ist das eigentlich von dir gemeint? Sollen verschiedenartige (int, double) Koordinatenpaare zusammen gespeichert werden? Das klingt unheimlich.

    Es ist ein Template, welches wahlweise approximation = integer, genau = double ist.


  • Mod

    asdasdasd schrieb:

    SeppJ schrieb:

    Bist du der Meinung, das unordered_set würde nicht funktionieren, wenn es eine Kollision gibt? Es wird nur weniger effizient.

    Da bin ich wohl in eine Falle getappt, dachte nämlich das bereits existierende Werte nicht übernommen werden. Dann hilft wohl nur der Pythagoras.

    Ich verstehe immer weniger, was du eigentlich möchtest.

    SeppJ schrieb:

    Wie ist das eigentlich von dir gemeint? Sollen verschiedenartige (int, double) Koordinatenpaare zusammen gespeichert werden? Das klingt unheimlich.

    Es ist ein Template, welches wahlweise approximation = integer, genau = double ist.

    Und du hältst es für eine gute Idee, für beide dieselbe Vergleichsfunktion zu benutzen?



  • Einfacher Vorschlag für eine generische Hashfunktion:

    template<typename T, typename Hash = std::hash<T> >
    class HashCoord
    {
    	public:
    		Hash h;
    		std::size_t operator()(const Coord<T>& c)  const
    		{
    			return h(c.row) + 3*h(c.col);
    		}
    };
    

    Performance ist vlt. noch nicht optimal aber sicher besser als deine alte Methode.



  • [quote="SeppJ"]Ich verstehe immer weniger, was du eigentlich möchtest.

    Ich suche einen Container oder ein Pattern Koordinaten nicht doppelt zu speichern. Muss anmerken, dass ich nicht zu den erfahrenen Programmieren gehöre.

    [quote="SeppJ"]Und du hältst es für eine gute Idee, für beide dieselbe Vergleichsfunktion zu benutzen?

    Ja, das habe ich bisher angenommen. Der tatsächliche Code sieht so aus:

    inline bool operator == ( const coord & lhs , const coord & rhs )
    {
        auto d_col = abs( lhs.col - rhs.col );
        auto d_row = abs( lhs.row - rhs.row );
    
        if( d_col >= eps() || d_row >= eps() )
        {
            return false;
        }
    
        return hypot( static_cast<double>( d_col) , static_cast<double> ( d_row ) ) < eps();
    }
    

    Die Methode eps() liefert bei integern 1 und bei double 1e-4. Wo könnte es da zu Problemen kommen?



  • Das ist keine gültige Vergleichsfunktion. In einem unordered_set muss der operator== transitiv sein, und das ist deiner nicht.

    Also aus a==b und b==c muss a==c folgen. Bei dir ist (0,0)==(0,eps/2) und (0,eps/2)==(0,eps), nicht aber (0,0)==(0,eps).

    Zudem ist es unmöglich, zu dieser Vergleichsfunktion eine Hashfunktion zu entwerfen, die funktioniert.

    Je nach Anwendungszweck kannst du einfach double-Koordinaten auf ganzzahlige Werte runden (bzw. zuerst mit 1/eps zu multiplizieren) und dort dann doppelte Werte ohne diese komische Vergleichsfunktion rausschmeissen.


  • Mod

    asdasdasd schrieb:

    Ich suche einen Container oder ein Pattern Koordinaten nicht doppelt zu speichern. Muss anmerken, dass ich nicht zu den erfahrenen Programmieren gehöre.

    Ok. Set oder unordered set. Ich fragte mich, was das mit Pythagoras sollte.

    Die Methode eps() liefert bei integern 1 und bei double 1e-4. Wo könnte es da zu Problemen kommen?

    Es ist halt ungeheuer umständlich für Integer, denn du könntest exakt das gleiche Ergebnis mit wesentlich weniger Aufwand erhalten. Warum keine eigene Spezialisierung dafür?

    Und auch für Fließkommazahlen gefällt mir die Funktion nicht. Wieso nicht

    auto d_col = lhs.col - rhs.col;
    auto d_row = lhs.row - rhs.row;
    auto d = d_col * d_col + d_row * d_row;
    
    return d < passender_vergleichswert;
    

    ?

    Ich sehe hier übrigens ein gewaltiges Problem mit dem unordered_set, das noch nicht erwähnt wurde: Diese Definition der Gleichheit genügt nicht den Äquivalenzanforderungen für Typen, die in Containern gespeichert werden. Aus A == B und B == C folgt hier nämlich nicht B == C. Weiterhin verstößt somit deine Hashfunktion gegen die Anforderungen an eine Hashfunktion, da zwei Objekte, die nach dieser Definition gleich sind, nicht unbedingt den gleichen Hash liefern.

    edit: Zu langsam 😞 . Wollte noch im Standard ganz genau gucken, wie eine Hashfunktion definiert ist, was zu lange gedauert hat. Aber das gibt mir noch die Gelegenheit zu fragen, wie sich der Threadersteller überhaupt die Lösung dieses Problems vorstellt: Wenn du drei Punkte A, B, C hast und A == B und B == C aber A != C, welche sollen dann übrig bleiben?



  • SeppJ schrieb:

    Aber das gibt mir noch die Gelegenheit zu fragen, wie sich der Threadersteller überhaupt die Lösung dieses Problems vorstellt: Wenn du drei Punkte A, B, C hast und A == B und B == C aber A != C, welche sollen dann übrig bleiben?

    Ich rieche hier ein Minimum-Vertex-Cover-Problem.


Anmelden zum Antworten