Wie effizient aus großer Anzahl von Elementen die n größten herausfinden ?

Benja_m

Hi

Ich habe viele (Bereich von 10^9) Integer-Zahlen. Ich suche nun die n (5, 30, xyz) größten Zahlen davon. Das ganze möglichst effizient.

Mir fällt dazu nur folgendes ein:

- Erzeuge ein Array der Größe n und fülle mit Nullen.
- Speichere in einer Variablen die Position des kleinsten Elements des Arrays
- Durchlaufe die Liste der Zahlen von Anfang bis Ende
    - vergleiche aktuelle Zahl mit kleinstem Element des Arrays
    - wenn aktuelle Zahl kleiner -> gehe zur nächsten Zahl
    - wenn aktuelle Zahl größer -> überschreibe Element in Array, finde kleinstes Element in Array und merke es dir, gehe zur nächsten Zahl

Wirklich effizient finde ich das noch nicht (insb. wenn n groß ist wird das ziemlich ineffektiv denke ich).
Hat jemand einen besseren Vorschlag ? Links o.ä. reicht auch, muss nichts ausgearbeitetes sein (wenngleich ich das auch okay fände ;))

Vielen Dank.

BigNeal

Benja_m schrieb:

- Erzeuge ein Array der Größe n und fülle mit Nullen.

und was ist, wenn du negative zahlen hast?

Sgt. Nukem

Sind die Zahlen denn in gewisser Weise vorsortiert?

CStoll

Schau dir mal die STL an, partial_sort() oder nth_element() könnten den richtigen Ansatz bieten.

Benja_m

negative zahlen *sicher* kommen nicht vor.

vorsortiert sind die zahlen nicht.

nth_element sieht brauchbar aus. aber ob es sinnvoll ist, *alle* zahlen in die korrekte reihenfolge zu sortieren ?

danke schonmal !

CStoll

Benja_m schrieb:

aber ob es sinnvoll ist, *alle* zahlen in die korrekte reihenfolge zu sortieren ?

nth_element() sortiert gar nicht alle Elemente, es partitioniert sie nur um:

vector<int> data(10000);
...
nth_element(data.begin(),data.begin()+30,data.end());

^^ das schiebt die 30 kleinsten Elemente des Vektors an den Anfang.

Benja_m

hiernach (als URL in browser kopieren)
msdn.microsoft.com/library/en-us/vclang98/html/sample_nth_element_(STL_Sample).asp#_sample_stl_nth_element

habe ich es anders verstanden. siehe beispiel dort. das ist dann vermutlich schlecht gewählt ... ?

verstehe ich es richtig, dass dann ein aufruf a la

vector<int> data(10000);
...
nth_element(data.begin(),data.begin()+30,data.end(), >);

die 30 größten elemente an den anfang schieben würde ? wobei man da vermutlich nicht einfach ">" als komparator übergeben kann sondern das irgendwie anders beschreiben müsste ?

CStoll

Benja_m schrieb:

habe ich es anders verstanden. siehe beispiel dort. das ist dann vermutlich schlecht gewählt ... ?

Durchaus möglich - die vorgegebene Zahlenfolge ist ja schon fast sortiert.

verstehe ich es richtig, dass dann ein aufruf a la
vector<int> data(10000);
...
nth_element(data.begin(),data.begin()+30,data.end(), >);
die 30 größten elemente an den anfang schieben würde ? wobei man da vermutlich nicht einfach ">" als komparator übergeben kann sondern das irgendwie anders beschreiben müsste ?

Ja, ist richtig. Anstelle des > benötigst du übrigens "greater<int>()" (und den Header <functional>).

Benja_m

herzlichen dank !