3. vector sortieren. logikfehler ?

vector sortieren. logikfehler ?

  • K

    CStoll schrieb:

    Also so ganz habe ich dein Verfahren noch nicht durchschaut - wozu packst du denn am Anfang zehn Kopien des ersten Eintrags in deinen Hilfsvector?

    btw, wozu sowas umständlich von Hand programmieren, das gibt es bstimmt schon fertig in der STL. Nach der ersten Beschreibung würde ich zu partial_sort() tendieren.

    öhm, damit ich von diesen 10 Wegpunkten den größten raussuchen kann, um ihn dann zu löschen,dann kommt wieder ein wp hinzu und es wird wiedergeschaut welcher der größte ist und wird gelöscht. usw
    wahrscheinlich aber habe ich einen ziemlich schwerwiegenden denkfehler.

    ähm partial_sort() werde ich mal googlen, danke

    Edit :

    ähm mit den stl sort functions kann ich nicht viel anfangen, denke ich jedenfalls.
    ich denke das man damit nur integer nach ihrer größe sortieren kann. allerdings muss ich diese integer werte erst in eine formel einsetzen um zu sehen, ob sie wirklich größer/kleiner sind. der ursprungswert ist dabei völlig unrelevant.

    0
  • A

    ähm mit den stl sort functions kann ich nicht viel anfangen, denke ich jedenfalls.
    ich denke das man damit nur integer nach ihrer größe sortieren kann. allerdings muss ich diese integer werte erst in eine formel einsetzen um zu sehen, ob sie wirklich größer/kleiner sind. der ursprungswert ist dabei völlig unrelevant.

    Ähm nein, du kannst eine beliebige Funktion als Sortierkriterium verwenden, etwa:

    data startPoint{startX,startY,startZ};
vector<data> copy(svec);
partial_sort(copy.begin(),copy.begin()+10,copy.end(),
                     [&](const data& p1,const data& p2)
                     {
                       return p1.dist_p2(startPoint)<p2.dist_p2(startPoint);
                     });

    mit dist_p2:

    int data::dist_p2(const data& rhs)
{
  int xd = abs(X-rhs.X);
  int yd = abs(Y-rhs.Y);
  int zd = abs(Z-rhs.Z);
  return xd*xd+yd*yd+zd*zd;
}

    Zum Vergleichen ist das Wurzelziehen nicht notwendig. Vermeide außerdem pow, wenn du nur quadrieren möchtest. Allein damit kannst du die Geschwindigkeit auf ein Vielfaches steigern.

    Edit: dein Code ist übrigens (beinahe) korrekt, nur sehr langsam.
    Du betrachtest den ersten Punkt in svec zehnmal, das erscheint mir nicht viel Sinn zu machen. Außerdem behandelst du nicht den Fall, dass es zehn Punkte gibt, die auf dem Startpunkt liegen (bzw. wenn der erste Punkt auf dem Startpunkt liegt). Deine Schleife findet dann nichts, erase wird aber trotzdem aufgerufen.

    Edit2: statt meiner Variante solltest du gleich partial_sort_copy nutzen.

    0
  • K

    Zum Vergleichen ist das Wurzelziehen nicht notwendig. Vermeide außerdem pow, wenn du nur quadrieren möchtest. Allein damit kannst du die Geschwindigkeit auf ein Vielfaches steigern.

    stimmt, daran habe ich noch garnicht gedacht :x

    okay vorab möchte ich noch erwähnen das ich noch nie struct vorher benutzt habe und das ich erst ganz grob mit klassen beschäftigt habe.

    int data::dist_p2(const data& rhs)
{
  int xd = abs(X-rhs.X);
  int yd = abs(Y-rhs.Y);
  int zd = abs(Z-rhs.Z);
  return xd*xd+yd*yd+zd*zd;
}

    okay ich denke mal das nennt man struct member function? naja is ja auch egal.

    du definierst

    data startPoint{startX,startY,startZ};

    ich gehe mal davon aus das es durch eine reihenfolge initalisiert wird.
    so das

    X=startX
Y=startY
Z=startZ

    das kann ich alles nachvollziehen ohne mich genauer damit auszukennen, aber

    partial_sort(copy.begin(),copy.begin()+10,copy.end(),
                     [&](const data& p1,const data& p2)
                     {
                       return p1.dist_p2(startPoint)<p2.dist_p2(startPoint);
                     });

    ist ein wenig schwerer zu verstehen.

    copy.begin(),copy.begin()+10

    sind das die elemente die ausgetauscht werden müssen?
    also dh wenn ich den vector copy ausgebe sind die ersten 10 werte die kleinsten, die werte die danach kommen sind ungeordnet.stimmt doch so oder ?

    [&](const data& p1,const data& p2)

    hier setzt der algorithmus die verschiednen xyz werte ein, die im vector gespeichert sind.

    return p1.dist_p2(startPoint)<p2.dist_p2(startPoint);

    und das ist die bedingung mit der die ersten 10 elemente ausgetauscht werden.

    hmm ich kann nur raten was passiert, aber ich denke ich kann das einfach übernehmen.

    danke für die sehr ausführliche antwort 🙂

    0
  • C

    kantaki schrieb:

    int data::dist_p2(const data& rhs)
{
  int xd = abs(X-rhs.X);
  int yd = abs(Y-rhs.Y);
  int zd = abs(Z-rhs.Z);
  return xd*xd+yd*yd+zd*zd;
}

    okay ich denke mal das nennt man struct member function? naja is ja auch egal.

    der Unterschied zwischen struct und class ist wesentlich kleiner als viele Anfänger vermuten würden. Genau genommen besteht der Unterschied nur darin, wie die Member ohne explizite Angaben zugreifbar sind.

    partial_sort(copy.begin(),copy.begin()+10,copy.end(),
                     [&](const data& p1,const data& p2)
                     {
                       return p1.dist_p2(startPoint)<p2.dist_p2(startPoint);
                     });

    ist ein wenig schwerer zu verstehen.

    copy.begin(),copy.begin()+10

    sind das die elemente die ausgetauscht werden müssen?
    also dh wenn ich den vector copy ausgebe sind die ersten 10 werte die kleinsten, die werte die danach kommen sind ungeordnet.stimmt doch so oder ?

    Soweit stimmt das (außerdem übergibst du noch copy.end() als Ende der zu sortierenden Werte). Der letzte Parameter gibt dann an, nach welchem Kriterium entschieden wird, welcher Wert "kleiner" ist.
    In diesem Beispiel ist die Vergleichsfunktion eine anonyme Funktion, die dort direkt zusammengebaut wird (mit C++03 müsstest du dir einen eigenen Funktor dafür zusammenbauen, der das selbe macht).

    0
  • A

    Naja, sieh dir einfach die Dokumentation zu partial_sort an:
    http://www.cplusplus.com/reference/algorithm/partial_sort/

    Der erste und dritte Parameter grenzen den gesamten zu sortierenden Bereich ein (hier den gesamten vector), der erste und zweite geben den Bereich an, der hinterher sortiert sein soll (nämlich die ersten zehn Elemente).
    Der letzte Parameter ist eine Funktion, die zurückgibt, ob das erste übergebene Objekt kleiner als das zweite ist. Diese Funktion wird dann vom Sortieralgorithmus mehrfach aufgerufen.

    Edit: ui, langsam.

    0
  • K

    okay danke jetzt macht das alles schon einwenig mehr sinn =).

    allerdings hat das mit dem defenieren der member function nicht außerhalb funtioniert, also habe ich sie einfach ins struct miteinbezogen. dürfte doch keinen unterschied machen oder ?

    struct data
{
     double X;
     double Y;
     double Z;
     double dist_p2(const data& rhs)
        {
        double xd = abs(X-rhs.X);
        double yd = abs(Y-rhs.Y);
        double zd = abs(Z-rhs.Z);
        return xd*xd+yd*yd+zd*zd;
}

};

    und bei

    data startPoint{startX,startY,startZ};
        vector<data> copy(svec);
        partial_sort(copy.begin(),copy.begin()+10,copy.end(),
                     [&](const data& p1,const data& p2)
                     {
                       return p1.dist_p2(startPoint)<p2.dist_p2(startPoint);
                     });

    meckert mein compiler:

    no primary expression before [
    no primary expression before ]
    no primary expression before const
    no primary expression before const

    irgentwas habe ich mal wieder extrem falsch gemacht oder 😞 ?

    0
  • A

    allerdings hat das mit dem defenieren der member function nicht außerhalb funtioniert, also habe ich sie einfach ins struct miteinbezogen. dürfte doch keinen unterschied machen oder ?

    Ja, das gehört in die Klassendeklaration (denn das erlaubt Inlining auch ohne LTO).

    meckert mein compiler:
    [...]

    Er wird sich an der Lambdafunktion stören, denn die gibt es erst ab C++11. Wenn du GCC >=4.5 benutzt, kannst du mit -std=c++0x kompilieren.
    Ansonsten müsstest du einen eigenen Funktor basteln, wie CStoll schon gesagt hat.

    0
  • K

    Athar schrieb:

    allerdings hat das mit dem defenieren der member function nicht außerhalb funtioniert, also habe ich sie einfach ins struct miteinbezogen. dürfte doch keinen unterschied machen oder ?

    Ja, das gehört in die Klassendeklaration (denn das erlaubt Inlining auch ohne LTO).

    meckert mein compiler:
    [...]

    Er wird sich an der Lambdafunktion stören, denn die gibt es erst ab C++11. Wenn du GCC >=4.5 benutzt, kannst du mit -std=c++0x kompilieren.
    Ansonsten müsstest du einen eigenen Funktor basteln, wie CStoll schon gesagt hat.

    das ist ja das merkwürdige. ich hab extra meinen gnu compiler auf -std=c++0x umgestellt.
    ich habe es testweise mit dem vs2010 kompiler Kompiliert.

    error C2662: 'data::dist_p2': this-Zeiger kann nicht von 'const data' in 'data &' konvertiert werden

    also habe ich es einfach mal geändert

    data startPoint;
		startPoint.X = startX;
        startPoint.Y=startY;
        startPoint.Z=startZ;
        vector<data> copy(svec);
        partial_sort(copy.begin(),copy.begin()+10,copy.end(),
                     [&](data p1,data p2)
                     {
                       return p1.dist_p2(startPoint)<p2.dist_p2(startPoint);
                     });

    jetzt meckert vs2010 nicht mehr nur noch gnu, ich werd mal weiter schreiben.

    0
  • A

    Das war mein Fehler. Statt die Parameter zu ändern, solltest du das fehlende const bei dist_p2 ergänzen:

    double dist_p2(const data& rhs) const
{ ...
    0
  • K

    ah super danke 🙂

    0
  • K

    ich benutze code blocks mit dem mitgelieferten gnuc++ compiler. auch nach einbinden des std c++0x kann ich den code nicht kompilieren.
    hat jemand vielleicht eine idee woran es liegen könnte?

    ich lade mir mal
    http://webscripts.softpedia.com/script/Development-Scripts-js/Compilers/GNU-Compiler-Collection-26869.html
    gnu 4.6.1 herunter.
    edit : ah ich glaube der mitgelieferte gnu kompiler ist nur version 4.4.1 vielleicht liegt es daran

    0
  • A

    Hier wird dir geholfen:
    http://tdm-gcc.tdragon.net/

    Vernünftige MinGW-Distributionen mit GCC 4.6 sind mir bisher nicht bekannt (vernünftig=keine Abhängigkeiten zu mingwm10.dll, msvcp*.dll oder msvcrXX.dll)
    Edit: ftp://ftp.equation.com/gcc/ erfüllt das Kriterium doch. Die Namen einiger dieser DLLs tauchen zwar in der Binary auf (warum auch immer), aber importiert wird daraus nichts.
    Außerdem funktioniert mit dieser Version OpenMP anstandslos, anders als bei der neuesten TDM-Variante.

    0
  • K

    super funktioniert alles wie es soll.

    nochmals vielen dank =).

    allerdings hätte ich nur noch eine verständisfrage zu

    [&](const data& p1,const data& p2)

    [&]

    und zwar verstehe ich nicht wofür das sein soll, was macht es?

    0
  • P

    kantaki schrieb:

    super funktioniert alles wie es soll.

    nochmals vielen dank =).

    allerdings hätte ich nur noch eine verständisfrage zu

    [&](const data& p1,const data& p2)

    [&]

    und zwar verstehe ich nicht wofür das sein soll, was macht es?

    Das ist Teil eines Lambda-Ausdrucks. Ich behaupte aber mal, dass du nicht nur den Teil nicht ganz verstanden hast. Wenn du den nicht verstehst, macht der ganze Aufruf von partial_sort keinen wirklichen Sinn...

    0
Anmelden zum Antworten