Punkte zusammenfassen: Ist dieser Code gut? (Anfängerfehler)
-
@EinNutzer0 sagte in Punkte zusammenfassen: Ist dieser Code gut? (Anfängerfehler):
Ja, es handelt sich hierbei um Hausaufgaben, allerdings von jemand anderes, der mich um Hilfe gefragt hatte...
Dann kommt es drauf an, was genau die Vorgabe ist: Punkte clustern, oder Punkte auf exakt diese Weise clustern, oder Punkte auf exakt diese Weise mit diesen Sprachmitteln clustern?
-
@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.
-
@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 Point1Dso weit richtig?
-
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.
-
@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()
.
-
@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...
-
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.
-
Aber wie könnte ich das herausziehen? Hättest du ein Beispiel? Mit
friend
?
-
???
return p.x / 3;
?PS: Jetzt wo ich näher auf den Code gucke: Man kann's mit dem
const
auch übertreiben
-
#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)
-
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.
-
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 speziellefloor(x / 3.0)
-Clusterung fest in deine allgemeine Punktklasse ein. Was ist z.B. mit derfloor(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.
-
@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 aufthis
zu?@Finnegan Danke für deine Bemühungen, erfüllt die Anforderungen nicht.
-
@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.
-
@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 diePoint1dDiv3FloorCluster
-Objekte eben in einunordered_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 imunordered_set
gespeichert wird. Dieses enthält wenn ich das richtig sehe bei deinem Beispiel am Ende nur die Punkte2
und3
. Das liegt daran, dass in deinem Programm1 == 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.
-
@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.
-
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 zumfloor(p.x / 3.0)
-Clustering im selben Programm implementieren möchtest. Wie würdest du das machen?std::hash
undequal_to
sind ja bereits für dasfloor(p.x / 3.0)
-Clustering spezialisiert. Es bliebe dir - wenn du deine aktuell Implementations-Methode beibehalten willst - nur, eine neue Punktklasse einzuführenPoint1D_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 Programmin_same_div3_floor_cluster(const Point1D& a, const Point1D& b) -> bool
? Diese Funktion kannst du dann demunordered_set
als Template-Argument für dieequal_to
-Funktion übergeben. Auch hier gilt wieder: Zwei verschiedene Punkte, die im selben Cluster liegen, sind nicht gleich. Genau wie beioperator==
istequal_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
double
s 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 vonfloor(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 dasunordered_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 demunordered_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.
-
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 ja3.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?