array werte vergleichen...

Mein Algorythmus kann sehr wohl mit deinem mithalten.
Trotz der unnötigen Vergleiche liegt mein Algorythmus von der Geschwindigkeit mit deinem auf einer Linie.
Habs auch als Funktion in deinem Stil getestet.
Ps.
Wenn dein Code in Hinblick auf Schnelligkeit gemacht wurde würde ich niemals einen Vector zurückgeben.

vector <int> getUniqueValues(int *arr,unsigned arrsize)
{
   vector <int> result;
   for(int i=0;i<arrsize&&result.size()<2;i++)
   {
      if(count(arr,arr+arrsize,arr[i])==1) result.push_back(arr[i]);
   }
   return result;
}

HumeSikkins

@_Stefan
Also meiner Meinung nach hat dein Algorithmus (kein y) die Komplexität O(n^2) und wenn ich mich recht erinnere war meine Frage, ob das nicht besser geht. Er zählt sogar unnötig weiter, da er ja nicht die Frage "gibt es mehr als einen" sondern "wieviele gibt es" beantwortet.
Könntest du mir mal erklären, was ich übersehe?

PS: Es ging mir um den Algorithmus nicht um die Effizienz der Vektor-Rückgabe.

Taurin

@Hume
Ich deine beiden Algos mal getestet. Die erste Variante (const int* arr)
scheint nicht zu funktionieren.

Ich hab' mal Mirauder_Mo's Version ein bissl verändert. Insbesondere die
Schleife am Ende war überflüssig.

vector<int> getUniqueValues(int* arr, unsigned arrSize) 
{ 
  vector<int> result; 

  bool * nichtDoppelt = new bool[arrSize]; 

  fill(nichtDoppelt, nichtDoppelt+arrSize, true);

  for(int i=0; i<arrSize; ++i) 
  {  
    if(nichtDoppelt[i])
    { 
      for(int j=i+1; j<arrSize; ++j) 
      {  
        if(arr[i]==arr[j]) 
        { 
          nichtDoppelt[i]=false;
          nichtDoppelt[j]=false; 
        }  
      } 
      if(nichtDoppelt[i]) result.push_back(arr[i]);
    }  
  } 

  delete nichtDoppelt; 
  return result; 
}

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!

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.