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

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

  • E
    Gesperrt

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

    Punkte clustern, oder Punkte auf exakt diese Weise clustern, oder Punkte auf exakt diese Weise mit diesen Sprachmitteln clustern?

    Ich frage mal nach, ich glaube, unordered_set war vorgegeben. 😉

    0
  • E
    Gesperrt

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

    Sofortmaßnahme wäre, erst einmal die Punktklasse von dem Problem zu entkoppeln. Das Hashing hat dort nichts verloren. Merkwürdigerweise hast du schon alles zum Auslagern da, aber dein extra dafür geschriebener Code fragt dann die Punktklasse.

    Ok, aus deiner Sicht wäre eine Auslagerung der Hash-Logik sinnvoll, also single responsibility-Prinzip? Aber ... wo bleibt dann das "caching" des Hash-Werts? Also die nicht immer wieder Neuberechnung des Werts? Oder wäre das premature optimization, the root of all evil? Oder hab ich bei der Umsetzung mit unordered_set und custom class in C++ keine andere Wahl?

    Schauen wir uns doch einmal https://en.cppreference.com/w/cpp/container/unordered_set an. Ich brauche also folgende Dinge:

    template<
    class Key,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<Key>
> class unordered_set;

    Key==Point1D
    Hash==die struct
    KeyEqual==bool operator==
    Allocator==implizit vorgegeben durch Point1D

    so weit richtig?

    0
  • Mod

    Wie oft musst du den Hash denn berechnen? Einmal beim Einordnen. Wie oft ordnest du ein? Einmal. Ersparnis zur Laufzeit: Null. Kosten im Design: Unbezahlbar.

    0
    F
     1 Antwort
  • F

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

    Wie oft musst du den Hash denn berechnen? Einmal beim Einordnen. Wie oft ordnest du ein? Einmal. Ersparnis zur Laufzeit: Null. Kosten im Design: Unbezahlbar.

    Das, und auch noch:

    Gerade bei diesem Beispiel ist der Hash so trivial zu berechnen, dass die größere Datenstruktur aus Cache-Gründen vermutlich einen stärkeren negativen Einfluss auf die Performance hat, als die vielleicht zwei CPU-Instruktionen, die für die Berechnung erforderlich sind.

    Für Typen, wo der Hash so teuer zu berechnen ist, dass sich Caching tatsächlich lohnt, würde ich das Objekt in einer Klasse verpacken, die nur für das Zwischenspeichern des Hash-Werts zuständig ist: unordered_set<CachedHash<Point1D>>/cached_hash_point1d.value()/cached_hash_point1d.hash().

    0
    E
     1 Antwort
  • E
    Gesperrt

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

    Gerade bei diesem Beispiel ist der Hash so trivial zu berechnen, dass die größere Datenstruktur aus Cache-Gründen vermutlich einen stärkeren negativen Einfluss auf die Performance hat,

    Stimmt!

    Leute, 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_)
    {
    }

    size_t getHash() const { return floor(x / 3.0); }

    bool operator==(const Point1D& p) const { return this->getHash() == p.getHash(); }
};

namespace std {
template <>
struct hash<Point1D> {
    size_t operator()(const Point1D& p) const noexcept { return p.getHash(); }
};
}

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;
}

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

    Warum ist h ein size_t? size_t ist semantisch gedacht für Größenangaben von Containern.

    Ich hab noch mal nachgeschaut, das ist per definitionem so vorgegeben...

    0
  • Mod

    Ich finde es nach wie vor nicht gut, dass in einer Punktklasse fest eincodiert ist, ob, wie, und womit der später clusterbar ist. Anstatt das Parameter des Clusteralgorithmus zu machen, der dann allgemeine Punkte auf die Art und Weise Clustern kann, die er für richtig hält.

    0
  • E
    Gesperrt

    Aber wie könnte ich das herausziehen? Hättest du ein Beispiel? Mit friend?

    0
  • Mod

    ??? return p.x / 3;?

    PS: Jetzt wo ich näher auf den Code gucke: Man kann's mit dem const auch übertreiben

    0
  • E
    Gesperrt

    @SeppJ

    #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_) {}

  bool operator==(const Point1D &p) const { return floor(x / 3.0) == floor(p.x / 3.0); }
};

namespace std {
template <> struct hash<Point1D> {
  size_t operator()(const Point1D &p) const { return floor(p.x / 3.0); }
};
} // 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;
}

    Dann hast du in Zeile 14 und 19 Redundanzen. Ich hab extra dazugeschrieben, was dann mit bool operator== geschehen soll...

    https://de.wikipedia.org/wiki/Don’t_repeat_yourself == Clean code

    Zudem möchte ich Point1D einen Granularitäts-Parameter vielleicht mitgeben... (nimm 5 anstatt 3 zum Beispiel) 😬

    0
  • Mod

    Du kapierst es nicht, ich weiß nicht mehr, was ich machen soll. Es ist doch nicht schwer. Und wenn du dann auch noch solchen Quatsch anschleppst, bei dem du dich selber für superschlau hältst, obwohl du es bist, der einfachste Dinge nicht versteht, dann hab ich auch keine Lust mehr.

    0
    E
     1 Antwort
  • F

    Problematisch ist hier, dass dein operator== alle Punkte als gleich auswertet, die im selben Cluster liegen. Das ist erstens intuitiv falsch, weil es durchaus verschiedene (nicht-gleiche) Punkte geben kann, die Elemente der selben Cluster-Menge sind. Zweitens codierst du damit die sehr spezielle floor(x / 3.0)-Clusterung fest in deine allgemeine Punktklasse ein. Was ist z.B. mit der floor(x / 4.0)-Clusterung? Brauchst du dafür eine neue Punkt-Klasse? Wie soll die heißen?

    Wenn du deinen Code unbedingt so beibehalten willst, dann hätte ich damit weniger ein Problem, wenn du die Klasse umbenennst, so dass deutlicher wird, wass sie tatsächlich abbildet:

    class Div3FloorCluster {
public:
  const double representative;
  Div3FloorCluster(double representative) : representative{ representative } {}

  bool operator==(const Div3FloorCluster& other) const { return floor(representative / 3.0) == floor(other.representative / 3.0); }
};

    Das ist immer noch deine Punkt-Klasse, nur ebenen umbenannt. Hier steht die Klasse für ein Cluster deiner floor(x / 3.0)-Clusterung. Die Klasse wird mit einem Repräsentanten des Clusters initialisiert, also einem beliebigen Punkt, der Element des Clusters ist, für das die Klasseninstanz steht.

    Wenn man das weiter spinnt, dann kommt man am Ende eventuell bei so etwas hier an:

    #include <cmath>
#include <functional>

using namespace std;

class Point1D {
    public:
        double x;
        Point1D(double x_) : x(x_) {}
};

class Point1dDiv3FloorCluster {
    public:
        Point1dDiv3FloorCluster(const Point1D& representative)
        : cluster_identifier{ floor(representative.x / 3.0) } {}
        
        double get_identifier() const {
            return cluster_identifier;
        }

        bool operator==(const Point1dDiv3FloorCluster& other) const {
            return cluster_identifier == other.cluster_identifier;
        }
        
    private:
        double cluster_identifier;
};

namespace std
{
    template<> 
    struct hash<Point1dDiv3FloorCluster> {
        size_t operator()(const Point1dDiv3FloorCluster& cluster) const noexcept {
            return std::hash<double>{}(cluster.get_identifier());
        }
    };
}

    Das ist sicher noch nicht perfekt, bringt aber m.E. deinen Ansatz in eine sinnvollere Struktur.

    Damit kann man schon weiterarbeiten, denke ich. Z.B. indem man die Punkte in eine std::unordered_map<Point1dDiv3FloorCluster, std::vector<Point1D>> einfügt. In der Datenstruktur hättest du dann all deine Punkte schön nach Clustern gruppiert.

    0
  • E
    Gesperrt

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

    Du kapierst es nicht, ich weiß nicht mehr, was ich machen soll. Es ist doch nicht schwer. Und wenn du dann auch noch solchen Quatsch anschleppst, bei dem du dich selber für superschlau hältst, obwohl du es bist, der einfachste Dinge nicht versteht, dann hab ich auch keine Lust mehr.

    Tipps sind meistens dann gut, wenn sie richtig sind. 😉

    Wo soll deiner Meinung nach die Berechnung stehen? Und wenn außerhalb von Point1D, wie greife ich dann auf this zu?

    @Finnegan Danke für deine Bemühungen, erfüllt die Anforderungen nicht.

    -1
    F
     2 Antworten

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

    wenn sie richtig sind.

    Ja, SeppJ hat tatsächlich ein "nicht" vergessen:

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

    Du kapierst es nicht, ich weiß nicht mehr, was ich machen soll. Es ist doch nicht schwer. Und wenn du dann auch noch solchen Quatsch anschleppst, bei dem du dich selber für superschlau hältst, obwohl du es nicht bist, der einfachste Dinge nicht versteht, dann hab ich auch keine Lust mehr.

    0 1 Antwort
  • F

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

    @Finnegan Danke für deine Bemühungen, erfüllt die Anforderungen nicht.

    Welche? unordered_set? Dann pack die Point1dDiv3FloorCluster-Objekte eben in ein unordered_set, ohne die einzelnen Punkte nochmal extra abzuspeichern. Schliesslich gehen dir auch bei deiner derzeitigen Lösung Punkte verloren, da wegen der Art, wie du hier "Gleichheit" definiert hast, nur der zuletzt eingefügte Punkt des Clusters im unordered_set gespeichert wird. Dieses enthält wenn ich das richtig sehe bei deinem Beispiel am Ende nur die Punkte 2 und 3. Das liegt daran, dass in deinem Programm 1 == 2 gilt, da passiert eben sowas (kann ja durchaus auch in dem Kontext Sinn machen und so gewollt sein). Hätte jetzt eher vermutet, dass man am Ende noch sagen können will, welche Punkte jetzt konkret zu welchem Cluster gehören.

    0
  • Mod

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

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

    wenn sie richtig sind.

    Ja, SeppJ hat tatsächlich ein "nicht" vergessen:

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

    Du kapierst es nicht, ich weiß nicht mehr, was ich machen soll. Es ist doch nicht schwer. Und wenn du dann auch noch solchen Quatsch anschleppst, bei dem du dich selber für superschlau hältst, obwohl du es nicht bist, der einfachste Dinge nicht versteht, dann hab ich auch keine Lust mehr.

    Nein, hab ich nicht. Was ist daran so schwer zu verstehen, das Konzept von "Punkt" und "Cluster" zu trennen? Dinge unterscheiden kann jedes Baby.

    0 1 Antwort
  • E
    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.

    0
    F
     1 Antwort

  • getHash sollte sich nicht im namespace std befinden.

    0
  • F

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

    0
  • E
    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?

    0
    F
     1 Antwort

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

    0
Anmelden zum Antworten