Doppelte Koordinaten entfernen



  • Hallo!

    Ich habe einen Quellcode, der Koordinaten erst einmal in einem Vektor sammelt und sie dann im nächsten Schritt herausschmeisst.

    Es sind etwa 10k - 50k Punkte. Mit dem Profiler habe ich festgestellt, dass dieses herausschmeissen etwa 15% der Zeit ausmacht.

    Meine Kenntnisse sind nicht gut genug um den Nutzen vorab abzuschätzen, deswegen habe ich angefangen eine Simulation durchzurühren.

    Hier der Quellcode, ich verwende ein unordered_set.

    // Hierbei handelt es sich um mehr oder weniger abstrahierten Pseudocode.
    
    template <typename T> std::string to_string( T const& value ) 
    {
    	stringstream sstr;
    	sstr << value;
    	return sstr.str();
    }
    
    // So werden die Koordinaten gespeichert
    class coord
    {
    	int col;
    	int row;
    
    	// Hier sind noch mehr member.
    
    	// Methoden
    
    	// Hash operator
    	operator size_t() const
    	{
    		std::hash<std::string> str_hash;
    		return str_hash( to_string( col ) + to_string( row ) );
    	}
    };
    
    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 > 1 || d_row > 1 )
    	{
    		return false;
    	}
    
    	return hypot( static_cast<double>( d_col) , static_cast<double> ( d_row ) );
    }
    

    Zum Operator size_t kann ich irgendwie nichts sinnvolles finden. Wie kann ich koordinaten sinnvoll hashen? Im Endeffekt ist meine einzige Lösung beide Koordinaten in ein string zu wandeln, zusammenzuketten und dann zu hashen.

    Wäre für jeden Performance-Tipp dankbar!


  • Mod

    asdasdasd schrieb:

    Ich habe einen Quellcode, der Koordinaten erst einmal in einem Vektor sammelt und sie dann im nächsten Schritt herausschmeisst.

    Hier der Quellcode, ich verwende ein unordered_set.

    Ich verstehe die Episode mit dem vector nicht. Wenn du eine set-artige Datenstruktur nutzt, dann werden doppelt vorkommende Werte doch automatisch entfernt.

    Zum Operator size_t kann ich irgendwie nichts sinnvolles finden.

    Was willst du dazu finden? Es ist höchst gefährlich, einen Konvertierungsoperator anzubieten, wenn das keine natürliche Konvertierung deiner Klasse ist. Stell doch lieber eine explizite Hashfunktion bereit.

    Wie kann ich koordinaten sinnvoll hashen? Im Endeffekt ist meine einzige Lösung beide Koordinaten in ein string zu wandeln, zusammenzuketten und dann zu hashen.

    Um also aus einem Zahlenpaar eine einzelne große Zahl zu machen, ist die beste Möglichkeit, die dir einfällt, der Weg über einen String und eine anschließende Hashfunktion? Wie wäre es, in einfachster Ausführung, einen der Werte zu shiften und dann die Werte zu addieren?



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



  • SeppJ schrieb:

    Ich verstehe die Episode mit dem vector nicht. Wenn du eine set-artige Datenstruktur nutzt, dann werden doppelt vorkommende Werte doch automatisch entfernt.

    Bisher sammelt das Programm alle möglichen Koordinatenpaare in einem std::vector. Erst im nächsten Schritt werden dann doppelte Punkte herausgeschmissen. Ich versuche Zeit einzusparen indem ich schon vorab doppelte Koordinaten herausfiltere.

    SeppJ schrieb:

    Was willst du dazu finden? Es ist höchst gefährlich, einen Konvertierungsoperator anzubieten, wenn das keine natürliche Konvertierung deiner Klasse ist. Stell doch lieber eine explizite Hashfunktion bereit.

    Mir geht es nur um den Hash für das unordered_set. Wie mache ich sowas? Sagen wir mal ich erstelle eine Member Funktion, wie übergebe ich sie an das unordered_set?

    SeppJ schrieb:

    Um also aus einem Zahlenpaar eine einzelne große Zahl zu machen, ist die beste Möglichkeit, die dir einfällt, der Weg über einen String und eine anschließende Hashfunktion? Wie wäre es, in einfachster Ausführung, einen der Werte zu shiften und dann die Werte zu addieren?

    Meinst du so etwas hier ( https://stackoverflow.com/questions/3934100/good-hash-function-for-list-of-2-d-positions )?

    public int hashCode()
    {
        int hash = 17;
        hash = ((hash + col) << 5) - (hash + col);
        hash = ((hash + row) << 5) - (hash + row);
        return hash;
    }
    

    Wie ist es mit der Eindeutigkeit?


  • Mod

    asdasdasd schrieb:

    SeppJ schrieb:

    Was willst du dazu finden? Es ist höchst gefährlich, einen Konvertierungsoperator anzubieten, wenn das keine natürliche Konvertierung deiner Klasse ist. Stell doch lieber eine explizite Hashfunktion bereit.

    Mir geht es nur um den Hash für das unordered_set. Wie mache ich sowas? Sagen wir mal ich erstelle eine Member Funktion, wie übergebe ich sie an das unordered_set?

    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.

    SeppJ schrieb:

    Um also aus einem Zahlenpaar eine einzelne große Zahl zu machen, ist die beste Möglichkeit, die dir einfällt, der Weg über einen String und eine anschließende Hashfunktion? Wie wäre es, in einfachster Ausführung, einen der Werte zu shiften und dann die Werte zu addieren?

    Meinst du so etwas hier ( https://stackoverflow.com/questions/3934100/good-hash-function-for-list-of-2-d-positions )?

    public int hashCode()
    {
        int hash = 17;
        hash = ((hash + col) << 5) - (hash + col);
        hash = ((hash + row) << 5) - (hash + row);
        return hash;
    }
    

    Ja, so etwas in der Art. Ich dachte zunächst sogar nur an etwas wie

    hash = col << 5 + row;
    

    Wie ist es mit der Eindeutigkeit?

    Kommt drauf an.

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

    return (lhs.row == rhs.row) && (lhs.col == rhs.col);
    


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


Log in to reply