Optimierung von Funktionen

Der Rechenaufwand deines Algorithmus für ein Array mit n Elementen ist O(n²). Wenn du das Array erst in O(n·log(n)) sortierst, geht das anschließende Filtern der Duplikate in O(n) und damit der gesamte Algorithmus in O(n·log(n)+n) = O(n·log(n)).

Zumindest für sehr große Arrays wird das die Rechenzeit drastisch reduzieren.

Edit:

Mit einer Hashtabelle geht es evtl. noch schneller, unter günstigen Bedingungen in O(n).

Wenn der Wertebereich der Array-Elemente beschränkt und nicht allzu groß ist, kannst du dabei die Elemente selber als Hash-Werte nehmen, dann geht es sogar noch schneller und garantiert in O(n).

Aber wie kann ich jetzt vorgehen um die Funktion zu optimieren?

Geeignete Hardware verwenden. Die schafft das in O(1). Vom Aufwand war ja keine Rede. :)

Chandler B. schrieb:

for (size_t y=0; y<*pResultCount; y++) { if(values[x] == ptr[y]) { valueExisting = true; } }

Eine einfache Optimierung: Nach der Zuweisung ein break einfügen, damit die innere Schleife nicht immer komplett bis zum Ende weitersucht, obwohl der Wert schon gefunden wurde.

Habe ich aus der Suchmaschine: "The compiler unrolls loops automatically at -O3"

Chandler B. schrieb:

if (count >= 1)

Sollte man sich bei C-Programmierung lieber gleich abgewöhnen.

Asm-Unterfunktionen waren früher einfacher - wenn man aber die Hardware kennt, kann sich an Compilerfeinheiten orientieren: https://dmalcolm.fedorapeople.org/gcc/2015-08-31/rst-experiment/how-to-use-inline-assembly-language-in-c-code.html

Auch wenn es nicht gefragt war, in C++ ist es ein Dreizeiler, der allerdings das Ergebnis dann gleich noch sortiert zurückgibt.

1

void distinct(std::vector<int> &v)

2

{ 

3

    std::sort(v.begin(), v.end());

4

    auto last = std::unique(v.begin(), v.end());

5

    v.erase(last, v.end());

6

}

Klaus schrieb:

Auch wenn es nicht gefragt war, in C++ ist es ein Dreizeiler, der allerdings das Ergebnis dann gleich noch sortiert zurückgibt.

1

> void distinct(std::vector<int> &v)

2

> {

3

>     std::sort(v.begin(), v.end());

4

>     auto last = std::unique(v.begin(), v.end());

5

>     v.erase(last, v.end());

6

> }

7

>

Wobei Du auch auf das erase verzichten kannst und verwendest stattdessen den Ende-Iterator. Das tatsächliche Entfernen ist meisten unnötig.

Hallo Yalu,

Yalu X. schrieb:

Mit einer Hashtabelle geht es evtl. noch schneller, unter günstigen Bedingungen in O(n).

ohne weitere Erklärung ist diese Behauptung verwirrend.

Vermutlich willst Du alle Elemente der Reihe nach in einem Bitfeld aushaken, dass so groß ist wie der Wertebereich der Hashs, die sich auch für Dich in O(1) berechnen lassen müssen.

Dann ist der Bearbeitungsaufwand minimal [ O(1) ], weil Du für jedes Element nur nachprüfen musst, ob seine Position im Bitfeld schon gesetzt ist.

Du tauschst dann allerdings Rechenzeit gegen Speicherplatz ein. Allerdings gibt es auch keine Gewähr dafür, dass Dein Bitfeld in einem Stück im Speicher liegt und der Aushakvorgang nur O(1) dauert.

Die O-Notation zielt ja auf große n ab.

Von daher bezweifele ich jede Laufzeitangabe, die schneller ist als O(n*log(n)).

Der günstigste Fall ist ja eigentlich nicht der interessanteste, sondern eher der schlechteste Fall oder der mittlere...

Rbx schrieb:

Chandler B. schrieb:

if (count >= 1)

Sollte man sich bei C-Programmierung lieber gleich abgewöhnen.

Was wäre deine Alternative?

Oliver

Oliver S. schrieb:

Was wäre deine Alternative?

if (count) ...

Aber nur wichtig zur Vermeidung von Augenkrebs, da der Compiler es sowieso wegoptimiert.

Apollo M. schrieb:

Oliver S. schrieb:

Was wäre deine Alternative?

if (count) ...

Aber nur wichtig zur Vermeidung von Augenkrebs, da der Compiler es sowieso wegoptimiert.

Du weißt das, aber ob Chandler das auch weiß?

Oliver