array werte vergleichen...

[_Stefan]

Du hast übersehen, das ich nicht behauptet habe, das mein Algorithmus (auch ohne) der optimale ist, sondern halt nur mit der einfachste.
Ich hab mich nicht auf eine eventuelle Frage von dir bezogen ...

PS
ist dein neuer Name Mirauder_Mo ?

Mein ansatz war es eher das ganze nicht nur richtig sonder auch schnell zu machen, und da kann der algorythmus von dir wohl nicht mithalten.

Darauf habe ich Mirauder_Mo nur einen dezenten Tip gegeben, das es seinen Code schneller macht, wenn er einen Zeiger auf einen Vector zurückzugeben als den kompletten Vector.

[Taurin]

_Stefan schrieb:

Du hast übersehen, das ich nicht behauptet habe, das mein Algorithmus (auch ohne) der optimale ist, sondern halt nur mit der einfachste.

Einfach und hübsch übersichtlich: ja.
Schnell: nein.

Dein Algo beinhaltet viele unnötige vergleiche (s. oben)

Darauf habe ich Mirauder_Mo nur einen dezenten Tip gegeben, das es seinen Code schneller macht, wenn er einen Zeiger auf einen Vector zurückzugeben als den kompletten Vector.

Das wird ein guter Compiler wegoptimieren.

Er verwandelt ein Funktion wie folgt:

//von
vector<int> foo();
//nach
void foo(const vector<int>&);

//den Aufruf verändert er entsprechend:
//von
vector<int> a = foo();
//nach
vector<int> a;
foo(a);

s. dazu: http://fara.cs.uni-potsdam.de/~kaufmann/?page=GenCppFaqs&faq=Optimize#Answ

[Mirauder_Mo]

_Stefan schrieb:

ist dein neuer Name Mirauder_Mo ?

ich hatte noch nie einen anderen namen, wen auch immer du mit der frage gemeint hast!

[_Stefan]

Mein Algo ist schön klein und fein, und sollte auch nie der schnellste sein.
Er hat viele unnötige Vergleiche, die ich niemals nie bestreite.
Für den normalen Gebrauch wirds wohl genügen, wer was anderes meint, der müsste wohl lügen.

Die Meinung ein guter Compiler wirds schon richten, teile ich mitnichten.

Optimierung fängt beim Compilen an ?

[Taurin]

Wenn man weiß (!), wo der Compiler den Code optimiert, dann kann
man sich durchaus darauf verlassen. Man sollte nur nicht hoffen
oder vermuten, was er vielleicht so tun könnte

[Mirauder_Mo]

_Stefan schrieb:

Mein Algo ist schön klein und fein, und sollte auch nie der schnellste sein.
Er hat viele unnötige Vergleiche, die ich niemals nie bestreite.
Für den normalen Gebrauch wirds wohl genügen, wer was anderes meint, der müsste wohl lügen.

Die Meinung ein guter Compiler wirds schon richten, teile ich mitnichten.

Optimierung fängt beim Compilen an ?

klein, ja. schön, nicht nach meiner ansicht. wenn soviele funktionsaufrufe sind finde ich persönlich das nicht so schön, das ist aber vieleicht mein problem.

ich denke nicht das es für den normalen gebrauch langen wird (was ist normaler gebrauch?). bei kleinen feldern ist der algorithmus nicht relevant, aber wenn man O(n*n) im gegensatz zu O(n*n/2) vergleiche hat ist das bei grossen feldern schon ausschlaggebend. dann kommt es natürlichkeit auf die häufigkeit von wiederholungen an, wenn wenige erwartet werden ist mein algo nicht um sehr viel schneller.

das mit dem verlassen auf den Compiler sehe ich ähnlich, ich hab das mit dem vector aber nur gemacht um die schnittstelle HumeSikkins bei zu behalten.

ich denke aber das das problem nicht so relevant ist das man sich deswegen fetzen müsste.

[HumeSikkins]

Hm,
vergesst es einfach. Ich wollte das ganze eher aus informatischer/algorithmischer Sicht betrachten. Für mich sieht das Problem dem Sortieren ähnlich. Und sortieren kann man in O(n*logn). Mir schien O(n^2) für ein solch einfaches Problem irgendwie vollkommen unangemessen.
Da ich in diesem Bereich aber nun mal ein totaler Dummbeutel bin, habe ich nachgefragt.

Zu dem Rückgabe-Problem:
Für den allgemeinen Fall sehe hier genau zwei Möglichkeiten:
a) Verwendung eines Out-Parameters, also Übergabe eines Vektors per Referenz
b) Value-Rückgabe als Rückgabewert.

Die Rückgabe eines Zeigers, so wie von _Stefan vorgeschlagen, halte ich für fragwürdig, da dieser ja auch auf irgendwas zeigen muss. Bleibt also nur:
c) Dynamische Allokation in der Funktion + Rückgabe des Zeigers -> doof.
d) Aufrufer-Allokation + Übergabe des Zeigers -> ähnlich a) nur doof, falls man noch explizites Memory-Management hinzufügt.

Dann doch lieber
e) STL-kompatible Schnittstelle -> zwei Eingabeiteratoren (mindestens Forward-Iteratoren), die die zu bearbeitende Sequenz bestimmen und ein Ausgabeiterator, in den geschrieben wird.

Ich persönlich bevorzuge einfache Schnittstellen solange dies möglich ist. D.h. ich persönlich würde b) verwenden solange dieser Ansatz nicht nachweislich zum Flaschenhals wird. Es gibt ja schließlich RVO (kann eigentlich jeder Compiler) und NRVO (können die meisten Compiler).

Soll der Algo generisch werden, dann würde ich eine zu std::copy-kompatible Schnittstelle verwenden.