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

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

  • E
    Gesperrt

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

    Das soll mit einer unordered_set und custom class umgesetzt werden:

    #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) { h = floor(x / 3.0); }

  size_t getHash() const { return h; }

  bool operator==(const Point1D &p) const { return h == p.h; }

private:
  size_t h;
};

struct Point1D_hash {
  size_t operator()(const Point1D &p) const { return p.getHash(); }
};

unordered_set<Point1D, Point1D_hash> s1;

int main(int argc, char *argv[]) {
  const int n = 4;
  Point1D points[n] = {Point1D(2.99), Point1D(1), Point1D(2), Point1D(3)};
  for (int i = 0; i < n; i++) {
    s1.insert(points[i]);
  }
  unordered_set<Point1D, Point1D_hash>::iterator itr;
  for (itr = s1.begin(); itr != s1.end(); itr++) {
    cout << (*itr).x << endl;
  }
  return 0;
}

    Ist der Ansatz so richtig?

    0 1 Antwort
  • Mod

    Vom Design her problematisch. Deine Punktklasse ist an deine Problemlösung gekoppelt. Schlecht und unflexibel. Und die Problemlösung klingt nicht gerade toll: Wie kommt man denn von der Problemdefinition zu der Erkenntnis, dass ein unordered_set bei der Lösung eine Rolle spielen sollte?

    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.

    Und danach: Gehe ich recht in der Annahme, dass das eine Hausaufgabe ist, die die Vorgabe mit dem unordered_set macht? In dem Fall: Tja, dann mach es halt so, aber guck dir das nicht für später ab.

    Andere Kleinigkeiten:

    • Ich mag nicht die Benutzung von h bevor h definiert ist. Da liest man Zeile 13, 15 und hat keine Ahnung, was das ist.
    • Der vorhergehende Punkt würde vielleicht weniger stark wiegen, wenn man aus dem Namen h erschließen könnte, was h ist. Programmieren ist kein Wettbewerb um die kürzesten und unlesbarsten Bezeichner. Gilt auch für den Rest des Codes.
    • Warum ist h ein size_t? size_t ist semantisch gedacht für Größenangaben von Containern.
    • Warum ist s1 global?
    • Das hier:
    unordered_set<Point1D, Point1D_hash> s1
[...]
const int n = 4;
Point1D points[n] = {Point1D(2.99), Point1D(1), Point1D(2), Point1D(3)};
for (int i = 0; i < n; i++) {
s1.insert(points[i]);
 }

    ->

    unordered_set<Point1D, Point1D_hash> s1 {Point1D(2.99), Point1D(1), Point1D(2), Point1D(3)};
    • Das hier:
    unordered_set<Point1D, Point1D_hash>::iterator itr;
  for (itr = s1.begin(); itr != s1.end(); itr++) {

    ->

    for(auto itr: s1){
    0
    E
     1 Antwort
  • *

    Die Includes sollten stimmen d.h. cmath statt math.h, climits statt limits.h. Warum wird keine Initialisierungsliste für s1 genutzt? Weshalb die alten Schleifen? Parameter und Member gleich zu benennen ist auch nicht sonderlich intelligent.

    0
  • E
    Gesperrt

    Danke für deine Hinweise, @SeppJ , ich werde diese berücksichtigen!

    Ja, es handelt sich hierbei um Hausaufgaben, allerdings von jemand anderes, der mich um Hilfe gefragt hatte...

    0 1 Antwort
  • Mod

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

    0
    E
     1 Antwort
  • 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
Anmelden zum Antworten