kleinste Elemente aus unsortierter Liste finden
-
#include <iostream> #include <vector> #include <algorithm> #include <ctime> using namespace std; int main(){ //ungetestet, es müßte noch sichergestellt werden, daß es mit allen eingaben klappt. int const n=1000; int const m=20; //vector anlegen vector<int> quelle; //zahlen von 1001 bis 1000+n reintun. for(int i=0;i<n;++i) quelle.push_back(10001+i); //durcheinanderwürfeln random_shuffle(quelle.begin(),quelle.end()); //anzeigen /* for(int i=0;i<n;++i) cout<<quelle[i]<<'\n';*/ //startzeit merken clock_t start=clock(); //zielgebiet sortieren sort(&quelle[0],&quelle[m]); //kleinste elemente vorziehen for(int i=m;i<n;++i){ swap(quelle[i],quelle[m]); int j=m; while(j>0 && quelle[j-1]>quelle[j]){ swap(quelle[j-1],quelle[j]); --j; } } //endzeit merken clock_t end=clock(); //anzeigen cout<<"Zeit: "<<(end-start)/double(CLOCKS_PER_SEC)<<'\n'; for(int i=0;i<m;++i) cout<<quelle[i]<<'\n'; return 0; }bei n=10000000 brauchte die alles-sortieren-methode bei mir 5 sekunden und die hier gezeigte hochblubbermethode 0.05 sekunden. die leistung bricht bei umgekehrt sortiertem feld ein auf 1.2 sekunden.
noch zwei messungen mit zufälligen daten:
n=100000000
hochblubbern:
m=100 -> zeit=0.516sstd::partial_sort:
m=100 -> zeit=0.234std::nth_element:
m=100 -> zeit=11.891#include <iostream> #include <vector> #include <algorithm> #include <ctime> using namespace std; int main(){ int const n=100000000; int const m=100; //vector anlegen vector<int> quelle; //zahlen von 1001 bis 1000+n reintun. for(int i=0;i<n;++i) quelle.push_back(10001+i); //durcheinanderwürfeln random_shuffle(quelle.begin(),quelle.end()); //anzeigen /* for(int i=0;i<n;++i) cout<<quelle[i]<<'\n';*/ //startzeit merken clock_t start=clock(); //zielgebiet sortieren sort(&quelle[0],&quelle[m]); //kleinste elemente vorziehen partial_sort(&quelle[0],&quelle[m],&quelle[n]); // nth_element(&quelle[0],&quelle[m],&quelle[n]); //endzeit merken clock_t end=clock(); //anzeigen cout<<"Zeit: "<<(end-start)/double(CLOCKS_PER_SEC)<<'\n'; for(int i=0;i<m;++i) cout<<quelle[i]<<'\n'; return 0; }ich denke, du solltest partial_sort nehmen.
-
Wow, und sowas um halb zwei morgens
Vielen Dank, ich werds morgen früh gleich testen!
-
Es gibt ein Verfahren, dass Aufwand O(n) hat. Das blöde ist nur, dass der Konstante Term so groß ist, dass du mit mehreren Gigabyte-Daten noch lange nicht schneller bist, als mit dem Sortieren Ansatz.
-
ProgChild schrieb:
Es gibt ein Verfahren, dass Aufwand O(n) hat. Das blöde ist nur, dass der Konstante Term so groß ist, dass du mit mehreren Gigabyte-Daten noch lange nicht schneller bist, als mit dem Sortieren Ansatz.
Google: k kleinste Elementnicht, daß es zu verwechslungen mit dem alles-sortieren-ansatz kommt, der ist bei n=100000000, m=100 (also den gleichen werten wie oben) bei mir mit 66,42 sekunden dabei.
-
partial_sort...
Es ist wie immer... man versucht etwas zu optimieren und findet irgendwann raus, dass es eine fertige Funktion gibt, die genau das tut was man will, und dass man sich die ganze Mühe auch hätte sparen können.Nee ich nehm die hochblubbern Methode, die gefällt mir
Eine Frage noch:
for(int i=m;i<n;++i)
Ich schreibe auch immer ++i statt i++, irgendwer hat mir vor Jahren mal eingeredet das wär besser, aber ich hab vergessen warum. Kannst du mir sagen wo da der Vorteil ist?
-
snOOfy schrieb:
Ich schreibe auch immer ++i statt i++, irgendwer hat mir vor Jahren mal eingeredet das wär besser, aber ich hab vergessen warum. Kannst du mir sagen wo da der Vorteil ist?
in
for(FetteKlasse i=ding.begin();i!=ding.end();i++)muß in i++ eine kopie der fetten klasse returnt werden, bei ++i reicht eine referenz. ++i ist potentiell schneller.
indem man immer ++i nimmt, muß man nie darüber nachdenken.
-
Könnte man es nicht einfach so machen, dass man durch die Liste geht und den 100. kleinsten Wert speichert (evtl. mit Häufigkeit). Dann geht man ein zweites mal durch und übernimmt alle Werte die <= sind (unter Berücksichtigung der Häufigkeit) in die Ergebnisliste. Aufwand wäre dann doch 2n € O(n)?
Wobei es je nach Größe von m und n vermutlich sinnvoller ist, für die Ergebnisliste eine Baumstruktur zu nehmen um dann einen Aufwand von log(m) * n zu bekommen. In O-Notation aufwendiger, aber wenn das m im Vergleich zum n hinreichend klein ist, könnte es schneller sein.
-
Limit schrieb:
Könnte man es nicht einfach so machen, dass man durch die Liste geht und den 100. kleinsten Wert speichert (evtl. mit Häufigkeit). Dann geht man ein zweites mal durch und übernimmt alle Werte die <= sind (unter Berücksichtigung der Häufigkeit) in die Ergebnisliste. Aufwand wäre dann doch 2n € O(n)?
Und wie willst du mit O(N) den 100. kleinsten Wert finden?
Ich würde einfach std::partial_sort verwenden. Das sollte optimal sein.
-
hustbaer schrieb:
Limit schrieb:
Könnte man es nicht einfach so machen, dass man durch die Liste geht und den 100. kleinsten Wert speichert (evtl. mit Häufigkeit). Dann geht man ein zweites mal durch und übernimmt alle Werte die <= sind (unter Berücksichtigung der Häufigkeit) in die Ergebnisliste. Aufwand wäre dann doch 2n € O(n)?
Und wie willst du mit O(N) den 100. kleinsten Wert finden?
Siehe auch nth_element http://www.sgi.com/tech/stl/nth_element.html mit zumindest erwarteter linearer Laufzeit.
-
life schrieb:
hustbaer schrieb:
Limit schrieb:
Könnte man es nicht einfach so machen, dass man durch die Liste geht und den 100. kleinsten Wert speichert (evtl. mit Häufigkeit). Dann geht man ein zweites mal durch und übernimmt alle Werte die <= sind (unter Berücksichtigung der Häufigkeit) in die Ergebnisliste. Aufwand wäre dann doch 2n € O(n)?
Und wie willst du mit O(N) den 100. kleinsten Wert finden?
Siehe auch nth_element http://www.sgi.com/tech/stl/nth_element.html mit zumindest erwarteter linearer Laufzeit.
Kuhl
Danke."I stand corrected"
