Zahlen sortieren

cplusplus_anfaenger

Wieso bin ich da eigentlich nicht selber darauf gekommen ?

Und wie sieht das mit der Summation aus, kann man da die Rechenzeit noch irgendwie verringern ?

MFK

Wenn du wirklich nur die kleinste, die größte und die Summe brauchst, warum schreibst du die Zahlen dann überhaupt in einen Vector, und bearbeitest das nicht, wenn die Zahlen anfallen? Von woher schreibst du die Zahlen in den Vector? Die Algorithmen der Standardbibliothek arbeiten auch auf ganz gewöhnlichen Arrays.

Nexus

Es gibt auch den STL-Container std::set , der die Daten gerade sortiert abspeichert.

Oder du nimmst std::valarray mit der eingebauten Funktion sum() .

It0101

Wenn du nur die kleinste und die größte Zahl brauchst dann brauchst du keineswegs den Vektor sortieren.

double *Array;
// sagen wir mal das Array ist gefüllt und besitzt die Länge N
double min = Array[0];
double max = Array[0];

for ( int i = 1; i < N; ++i )
{
    if ( Array[ i ] < min )
        min = Array[ i ];
    if ( Array[ i ] > max )
        max = Array[ i ];
}

// falls du noch den Index der Min und Max-Elemente benötigst, musst du halt 
// noch den Index i speichern.

Ich denke es ist ganz gut wenn er das mal selbst programmiert und nicht gleich von Anfang an von der STL bemuttert wird

cplusplus_anfaenger

Aber bei arrays muß immer die Länge vorher feststehen. Da ich aber nicht weiß wieviele Zahlen ich jeweils habe, woraus ich min, max und eventuell Summe bestimmen muß, kann ich arrays hier nicht verwenden, oder ?

It0101 schrieb:

Wenn du nur die kleinste und die größte Zahl brauchst dann brauchst du keineswegs den Vektor sortieren.
double *Array;
// sagen wir mal das Array ist gefüllt und besitzt die Länge N
double min = Array[0];
double max = Array[0];

for ( int i = 1; i < N; ++i )
{
    if ( Array[ i ] < min )
        min = Array[ i ];
    if ( Array[ i ] > max )
        max = Array[ i ];
}

// falls du noch den Index der Min und Max-Elemente benötigst, musst du halt 
// noch den Index i speichern.
Ich denke es ist ganz gut wenn er das mal selbst programmiert und nicht gleich von Anfang an von der STL bemuttert wird

Nur leider läuft das mit O(N), was bei "sehr vielen" Zahlen wohl nicht ausreichend ist.

Wie schaut's mit PriorityQueues oder ggf. zwei Heaps (natürlich jeweils "invers" zum anderen) aus?

cplusplus_anfaenger

@ Nexus

Nexus schrieb:

Es gibt auch den STL-Container std::set , der die Daten gerade sortiert abspeichert.

Aber ich vermute mal, dass die Rechenzeit bei min_element und max_element auf einem Vector angewendet geringer ist, denn wenn ich set verwende wird ja wieder alles sortiert und das kostet Rechenzeit.
Oder ? Bin ja kein Experte

cplusplus_anfaenger

Die Anzahl der Zahlen (N) variiert übrigens und liegt jeweils zwischen 1 und 300 Millionen.

Nexus

cplusplus_anfaenger schrieb:

@ Nexus

Nexus schrieb:

Es gibt auch den STL-Container std::set , der die Daten gerade sortiert abspeichert.

Aber ich vermute mal, dass die Rechenzeit bei min_element und max_element geringer ist, denn wenn ich set verwende wird ja wieder alles sortiert wird und das kostet Rechenzeit. Oder ? Bin ja kein Experte

Nein, std::set speichert die Daten nicht linear (sprich Array), sondern meistens in einem Binärbaum ab. Das ist wesentlich performanter, da nicht die ganze Sequenz neu geordnet werden muss. Beim Einfügen eines neuen Elements wird automatisch geschaut, dass es an die richtige Stelle kommt.

Falls du aber sehr viele Einfügungen hast und vergleichsweise selten das Minimum/Maximum benötigst, lohnt sich evtl. ein linearer Container mehr. Wobei man dann wieder bedenken sollte, dass min_element bzw. max_element bei sequenziellen Containern in O(n) läuft, während es im Set nur O(1), also konstante Zeit benötigt (entweder Anfang oder Ende).

Du musst natürlich auch beachten, ob dein Container noch andere Bedingungen erfüllen soll (z.B. Random Access). Und was die Summe betrifft, die ist wohl überall linear. Oder du addierst beim Einfügen eines neuen Elementes den neuen Wert zu einer eigenen, separaten Variable, sodass du da auch konstante Zugriffszeit hast.

cplusplus_anfaenger

[quote="nur halb gelesen"]

It0101 schrieb:

Wie schaut's mit PriorityQueues oder ggf. zwei Heaps (natürlich jeweils "invers" zum anderen) aus?

Ich gebe diese Frage mal an die Experten weiter

(Also im Detail sieht der Ablauf meines Teilprogrammes (innerhalb eines Loops) so aus:
Ich bekomme Zahlen (doubles, und zwar eine bis maximal etwa 300 Millionen davon), davon benoetige ich die größte Zahl,kleinste Zahl, die Summe der Zahlen und N (Anzahl der erhaltenen Zahlen) und auch noch die kleinsten Zahlen aus Teilmengen, wenn man die Menge aus N Zahlen so wie sie kommen in Teilmengen aus (Wurzel aus N) Zahlen aufteilt (N ist Quadratzahl,also funktioniert das).)

cplusplus_anfaenger

Also wie geht das nun am schnellsten ?

a) array
b) Vector, min_element/max_element
c) Set
d) PriorityQueues
e) Heaps
f) Noch etwas anderes

Shade Of Mine

cplusplus_anfaenger schrieb:

f) Noch etwas anderes

einen eigenen "container" schreiben der die elemnte nicht einfügt, sondern nur zur berechnung von min, max und sum verwendet:

ein push_back würde zB so aussehen:

void push_back(value_type const& value) {
  if(value<min) min = value;
  if(value>max) max = value;
  sum += value;
}

7H3 N4C3R

Bei der Anzahl von Werten (300 Millionen) würde ich dir, je nach Beschaffenheit der Zahlen und einen Anforderungen an die Genauigkeit, den Kahan-Summierungsalgorithmus empfehlen:
http://en.wikipedia.org/wiki/Kahan_summation_algorithm

Bei doubles reicht oft die Genauigkeit aus. Aber du kannst ja mal ausprobieren, ob es in deinem Fall etwas ausmacht und ob du die Präzision wirklich brauchst (drückt natürlich auch die Performance, das muss auch als Gegenargument mit einfließen).

cplusplus_anfaenger

Bei doubles reicht oft die Genauigkeit aus. Aber du kannst ja mal ausprobieren, ob es in deinem Fall etwas ausmacht und ob du die Präzision wirklich brauchst

Naja, ich "bekomme" doubles, wenn ich mit floats weiterrechnen wollte müßte ich die doubles erst alle "casten"

unskilled

cplusplus_anfaenger schrieb:

Bei doubles reicht oft die Genauigkeit aus. Aber du kannst ja mal ausprobieren, ob es in deinem Fall etwas ausmacht und ob du die Präzision wirklich brauchst

Naja, ich "bekomme" doubles, wenn ich mit floats weiterrechnen wollte müßte ich die doubles erst alle "casten"

Hmm... Das hatte er nicht gemeint (double ist genauer als float)
Er meinte, du sollst das, was du da rechnest ma iwo nachrechnen (taschenrechner oder so ^^ (und 300 Millionen Zahlen addieren xD) ) - keine Ahnung, wie ^^ Wenn die Abweichung dir zu groß ist, dann musst du dir irgend ne Lib für große Zahlen suchen...
Wenn du 300 Millionen doubles 'einfach' addierst wird es schon nen extrem große standard-abweichung geben - aber da haste ja auch scho nen tollen link bekommen...

bb