kleinste Elemente aus unsortierter Liste finden

snOOfy

Hallo!

Wie kann ich die m kleinsten Elemente in einer Liste mit n Elementen finden? Geht das irgendwie effektiver als mit dem Aufwand O(m n) ?

Es erscheint mir zu einfach, die Liste m Mal zu durchlaufen und jeweils das kleinste Element herauszuziehen...

Christoph

Das einfachste wäre wohl, die Liste zu sortieren und dann die ersten m Elemente herauszunehmen. Die Laufzeit ist dann O(n log n), unabhängig von m.

volkard

snOOfy schrieb:

Hallo!
Wie kann ich die m kleinsten Elemente in einer Liste mit n Elementen finden? Geht das irgendwie effektiver als mit dem Aufwand O(m n) ?
Es erscheint mir zu einfach, die Liste m Mal zu durchlaufen und jeweils das kleinste Element herauszuziehen...

Sortieren und die kleinsten rausnehmen hätte O(n*log(n)).

A) Aber ich gehe mal davon aus, du hast ein großes n und ein kleines m. Dann gehts schneller.

Ein Array der Größe m anlegen und alle Elemente aus m reinblubbern lassen, hat schlimmstenfalls O(n*m), dürfte aber bei unsortiertem m schneller als A sein.

C) Einen Heap der Größe 2*m anlegen und alle Elemente hochblubbern lassen, hat O(n*log(m)), dürfte aber bei unsortiertem m eher nur eine Vertauschung statt log(m) Vertauschungen machen, also schnell. Das war auch der Trick für B. edit: nee, klappt mit dem heap gar nicht.

D) Oder einfach quicksort kastrieren, daß es nicht sortiert, sondern im rekursiven abstieg immer die uninteressante hälfte in ruhe läßt (nebenbei die end-rekursion zur schleife machen). macht O(n).

snOOfy

Danke für die Antwort!

Ja, m ist viel kleiner als n. Aber ich fürchte ich bin deinen Methoden nicht ganz gewachsen

Ein Array der Größe m anlegen und alle Elemente aus m reinblubbern lassen

Sollte das zweite m ein n sein? Und wie lasse ich die Elemente aus dem n-Array in das m-Array blubbern? Indem ich n m-mal durchlaufe und jeweils das kleinste Element im m-Array speichere?

Einen Heap der Größe 2*m anlegen und alle Elemente hochblubbern lassen

Sorry die Methode verstehe ich nicht. Bei einem Heap könnte ich mir höchstens vorstellen, einen Min-Heap aufzubauen und dann die ersten m Elemente auszulesen, aber der Aufbau des Heaps hat ja auch wieder O(n log n) unabhängig von m.

Oder einfach quicksort kastrieren, daß es nicht sortiert, sondern im rekursiven abstieg immer die uninteressante hälfte in ruhe läßt

Wie kann man eine Hälfte in Ruhe lassen, wenn man nach mehreren Zahlen sucht? Was ist denn, wenn die kleinste in der einen und die zweitkleinste in der anderen Hälfte liegt?

volkard

ok, mir scheint, die einfachste methode wird erstmal die beste sein.
ich schreibs schnell...

volkard

#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.516s

std::partial_sort:
m=100 -> zeit=0.234

std::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.

snOOfy

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.

Google: k kleinste Element

volkard

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 Element

nicht, 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.

snOOfy

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?

volkard

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.

Limit

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.

hustbaer

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.

life

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?

http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22

Siehe auch nth_element http://www.sgi.com/tech/stl/nth_element.html mit zumindest erwarteter linearer Laufzeit.

hustbaer

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?

http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22

Siehe auch nth_element http://www.sgi.com/tech/stl/nth_element.html mit zumindest erwarteter linearer Laufzeit.

Kuhl
Danke.

"I stand corrected"