Punkte zusammenfassen: Ist dieser Code gut? (Anfängerfehler)


  • Gesperrt

    Ist es so besser?

    #include <iostream>
    #include <limits.h>
    #include <math.h>
    #include <string>
    #include <unordered_set>
    
    using namespace std;
    
    class Point1D {
    public:
      const double x;
      Point1D(double x_) : x(x_) {}
    };
    
    namespace std {
    size_t getHash(const Point1D &p) { return floor(p.x / 3.0); }
    template <> struct hash<Point1D> {
      size_t operator()(const Point1D &p) const { return getHash(p); }
    };
    template <> struct equal_to<Point1D> {
      bool operator()(const Point1D &lhs, const Point1D &rhs) const {
        return getHash(lhs) == getHash(rhs);
      }
    };
    } // namespace std
    
    int main(int argc, char *argv[]) {
      unordered_set<Point1D> us{Point1D(2.99), Point1D(1), Point1D(2), Point1D(3)};
      for (auto itr = us.begin(); itr != us.end(); itr++) {
        cout << (*itr).x << endl;
      }
      return 0;
    }
    

    Jetzt ist Point1D doch eindeutig nicht mehr für das Hashing/Clustering zuständig.



  • getHash sollte sich nicht im namespace std befinden.



  • @EinNutzer0 sagte in Punkte zusammenfassen: Ist dieser Code gut? (Anfängerfehler):

    Jetzt ist Point1D doch eindeutig nicht mehr für das Hashing/Clustering zuständig.

    Wenn man Haare spalten will, dann nein. Allerdings ist die Funktionalität noch immer an Point1D gekoppelt. Das wirst du spätestens dann merken, wenn du irgendein anderes Clustering parallel zum floor(p.x / 3.0)-Clustering im selben Programm implementieren möchtest. Wie würdest du das machen? std::hash und equal_to sind ja bereits für das floor(p.x / 3.0)-Clustering spezialisiert. Es bliebe dir - wenn du deine aktuell Implementations-Methode beibehalten willst - nur, eine neue Punktklasse einzuführen Point1D_other_clustering oder sowas. Genau das ist die Schwäche dieses Ansatzes.

    Warum nicht z.B. statt der equal_to-Spezialisierung einfach eine freie Funktion in deinem Programm in_same_div3_floor_cluster(const Point1D& a, const Point1D& b) -> bool? Diese Funktion kannst du dann dem unordered_set als Template-Argument für die equal_to-Funktion übergeben. Auch hier gilt wieder: Zwei verschiedene Punkte, die im selben Cluster liegen, sind nicht gleich. Genau wie bei operator== ist equal_to ein schlechter und unintuitiver Name für die Clustering-Funktion.

    Für die Hash-Funktion würde ich übrigens die Standard-Hashfunktion für doubles nehmen wie in meinem Beispiel weiter oben. Deine Clustering-Funktion ist nämlich eine denkbar schlechte Hashfunktion, da sie ziemlich viele Kollisionen erzeugt (für alle Punkte im selben Cluster). Das ist etwas, dass eine Hashfunktion so gut wie möglich vermeiden sollte... Edit: Nicht die Cluster-Kollisionen sind in diesem speziellen Fall das Problem, sondern eher die mangelnde Streuung der Hashwerte, was ebenfalls zu vielen Kollisionen führen kann. Besser das Ganze nochmal durch eine etablierte Hashfunktion laufen lassen. Beachte aber, dass du in dem Fall dennoch den Hash von floor(p.x / 3.0) berechnen solltest (std::hash<double>{}(floor(p.x / 3.0))) - schliesslich müssen zwei Punkte, die als gleich evaluiert werden, auch den selben Hash-Wert haben - sonst funktioniert das unordered_set nicht korrekt. Und auch hier: Gib der Hashfunktion einen sprechenden Namen, der sie als speziell für dieses Clustering gedacht erkennbar macht und übergib sie ebenfalls dem unordered_set als Template-Argument.

    Und du willst auch wirklich bis auf den letzten alle in das unordered_set eingefügten Punkte wegwerfen, die im selben Cluster liegen? Nur um sicherzugehen, dass das auch wirklich beabsichtigt ist, dass du in deinem Beispiel am Ende nur 2 Punkte in deinem Set hast.


  • Gesperrt

    Ok, Danke. Ich setz mich später nochmal dran.

    Eine Frage noch, was wäre besser, wenn ich einen floor_n-Parameter übergeben möchte für die "Granularität" des Clusterings... (im Moment ist es ja 3.0). Eine Objektvariable, dann muss ich für jede Instanz den gleichen Parameter mitgeben, oder eine Klassenvariable, dann wäre der Wert im Code fest. Oder erübrigt sich diese Frage, wenn ich für das Clustering eine eigene separate Klasse habe?



  • Sobald du die Granularität von deinem Punkt entkoppelst erübrigt sich die Frage wie du diese übergibst.



  • @EinNutzer0 sagte in Punkte zusammenfassen: Ist dieser Code gut? (Anfängerfehler):

    Also, es geht darum, nahe beieinanderliegende 1D-Punkte zusammenzufassen, um so die Punktmenge zu reduzieren. 9 und 10 liegen zum Beispiel nahe beieinander (9/3==3 und 10/3==3...).

    Ich verstehe deine Norm nicht.

    Wenn ich die Punkte 2.999, 3, 3.999 in dein Programm füttere, so erhalte ich die Punkte 2.999 und 3.

    Ich hätte da eher 2.999 und 3.999 erwartet.

    Ist das so von dir angedacht?



  • @EinNutzer0 sagte in Punkte zusammenfassen: Ist dieser Code gut? (Anfängerfehler):

    Ok, Danke. Ich setz mich später nochmal dran.

    Eine Frage noch, was wäre besser, wenn ich einen floor_n-Parameter übergeben möchte für die "Granularität" des Clusterings... (im Moment ist es ja 3.0). Eine Objektvariable, dann muss ich für jede Instanz den gleichen Parameter mitgeben, oder eine Klassenvariable, dann wäre der Wert im Code fest. Oder erübrigt sich diese Frage, wenn ich für das Clustering eine eigene separate Klasse habe?

    Wenn du diese Granularität nur zur Compile-Zeit frei bestimmen willst, dann könntest du z.B. deinen Clustering-Funktionen den Wert als Template-Argument übergeben: unordered_set<Point1D, div_floor_hash<3>, in_same_div_floor_cluster<3>>.

    Oder du packst das Clustering in Funktionsobjekte (wie std::equal_to eines ist) und übergibst dem unordered_set eine konkrete Instanz. Damit kannst du die Granularität auch zur Laufzeit festlegen:

    unordered_set<
        Point1D,
        div_floor_hash,
        in_same_div_floor_cluster
    > us(
        { Point1D(2.99), Point1D(1), Point1D(2), Point1D(3) },
        bucket_count,
        div_floor_hash{ 3 },
        in_same_div_floor_cluster{ 3 }
    );
    

    P.S.: Jetzt, wo ich gerafft habe, dass us wohl für "unordered set" steht, möchte ich noch anmerken, dass das ebenfalls kein sonderlich guter Name ist. Immerhin war deine Eingangsfrage ja, ob der Code "gut" ist 😉


  • Gesperrt

    @Quiche-Lorraine sagte in Punkte zusammenfassen: Ist dieser Code gut? (Anfängerfehler):

    @EinNutzer0 sagte in Punkte zusammenfassen: Ist dieser Code gut? (Anfängerfehler):

    Also, es geht darum, nahe beieinanderliegende 1D-Punkte zusammenzufassen, um so die Punktmenge zu reduzieren. 9 und 10 liegen zum Beispiel nahe beieinander (9/3==3 und 10/3==3...).
    

    Ich verstehe deine Norm nicht.

    Wenn ich die Punkte 2.999, 3, 3.999 in dein Programm füttere, so erhalte ich die Punkte 2.999 und 3.

    Ich hätte da eher 2.999 und 3.999 erwartet.

    Ist das so von dir angedacht?

    first come first serve principle 😉 (nicht last come first go) Ich sage nicht unbedingt, dass das schlau wäre...

    Ein intelligenteres Clustering wäre sicherlich, jeweils den Mittelwert zu bestimmen (dann geht HashSet aber nicht mehr).

    Angenommen, 1 2 3 und 7. Dann gäbe es die Cluster 1 2 3 und 7. Nun kommen 4 5 und 6 sukzessive dazu. Habe ich dann 12345 | 67 oder 1234 | 567 oder 123 | 4567 ?



  • @SeppJ Es war spät und zu viele nicht nicht.



  • @EinNutzer0 sagte in Punkte zusammenfassen: Ist dieser Code gut? (Anfängerfehler):

    Angenommen, 1 2 3 und 7. Dann gäbe es die Cluster 1 2 3 und 7. Nun kommen 4 5 und 6 sukzessive dazu. Habe ich dann 12345 | 67 oder 1234 | 567 oder 123 | 4567 ?

    Wenn ich das richtig sehe, wären die Cluster bei deiner aktuellen Methode mit { 1, 2, 3, 7 } eher { { 1, 2 }, { 3 }, { 7 } }. Gerade wenn du wirklich ernsthaft clustern willst und das hier nicht nur eine konkrete Hausaufgabe ist, dann macht es Sinn, die zusätzlichen Punkte eines Clusters nicht wegzuwerfen. Bei den meisten Algorithmen, an die ich mich da noch erinnere, können nämlich auch vorhandene Punkte in ein anderes Cluster wandern, wenn neue Punkte hinzukommen.

    Schau dir mal an, was sich Informatiker zu dem Thema an Verfahren ausgedacht haben. Das ist kein neues Problem. Spontan als Stichwort fällt mir da als Einstiegspunkt z.B. k-means clustering ein.

    Je nach deiner Problemstellung könnte auch eine Variante des (einfacheren) Median Cut-Algorithmus ein Ansatz sein. Diesen benutzt man z.B. zur Farbraumreduktion um möglichst gut gemittelte repräsentative Farben zu finden, wenn man z.B. ein Bild auf weniger Farben herunterzurechnen will (Farben sind letztendlich auch nur z.B. 3D-Vektoren im RGB-Raum). Mit dem Verfahren könntest du z.B. einen "mittleren" Punkt bestimmten, der zwar vielleicht nicht Element der ursprünglichen Punktmenge ist, aber sein zugehöriges Cluster gut repräsentiert.

    Die Verfahren sollten sich alle auch auf deinen 1D-Punktraum übertragen lassen und damit relativ simpel werden.


Anmelden zum Antworten