Optimierung von Funktionen

[Chandler B. (chandler)]

Hallo,

ich habe eine Funktion (in C) geschrieben, welche mir aus einem Array 
alle doppelten Werte Entfernt

int *distinct(const int *values, size_t count, size_t *pResultCount)
{
  int* ptr;
  bool valueExisting;
  *pResultCount = 0;
  ptr = (int*)calloc(count, sizeof(int));
  ptr[*pResultCount] = values[0];
  (*pResultCount)++;
  if (count >= 1)
  {
    for(size_t x=1; x<count; x++)
    {
      valueExisting = false;
      for (size_t y=0; y<*pResultCount; y++)
      {
        if(values[x] == ptr[y])
        {
          valueExisting = true;
        }
      }
      if (false == valueExisting)
      {
        ptr[*pResultCount] = values[x];
        (*pResultCount)++;
      }
    }
  }
  
  return ptr;
}

values: 1 1 1 2 3 0
count: 6

-> pResultCount: 4
-> return: 1 2 3 0

das ganze funktioniert auch.

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

[Yalu X. (yalu) (Moderator)]

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).

[Motopick (motopick)]

> 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. :)

[Rolf M. (rmagnus)]

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.

[Rbx (rcx)]

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

[Klaus (feelfree)]

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

void distinct(std::vector<int> &v)
{ 
    std::sort(v.begin(), v.end());
    auto last = std::unique(v.begin(), v.end());
    v.erase(last, v.end());
}

[Wilhelm M. (wimalopaan)]

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

> void distinct(std::vector<int> &v)
> {
>     std::sort(v.begin(), v.end());
>     auto last = std::unique(v.begin(), v.end());
>     v.erase(last, v.end());
> }
>

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

[Gerald K. (geku)]

void removeDuplicates(int *values, size_t *pResultCount) {
    if (*pResultCount <= 1) {
        // Keine oder nur ein Element im Array, daher keine Duplikate möglich
        return;
    }

    size_t uniqueIndex = 1;

    for (size_t current = 1; current < *pResultCount; ++current) {
        bool valueExisting = false;
        for (size_t prev = 0; prev < uniqueIndex; ++prev) {
            if (values[current] == values[prev]) {
                valueExisting = true;
                break;
            }
        }

        if (!valueExisting) {
            values[uniqueIndex++] = values[current];
        }
    }

    *pResultCount = uniqueIndex;
}

int main() {
    int values[] = {1, 1, 1, 2, 3, 0, 2};
    size_t count = sizeof(values) / sizeof(values[0]);

    removeDuplicates(values, &count);

    // Hier können Sie auf die eindeutigen Werte in 'values' zugreifen
    // und die Anzahl der eindeutigen Werte ist in 'count' enthalten.
    return 0;
}

[Peter M. (r2d3)]

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...

[Oliver S. (oliverso)]

Rbx schrieb:
> Chandler B. schrieb:
>> if (count >= 1)
>
> Sollte man sich bei C-Programmierung lieber gleich abgewöhnen.

Was wäre deine Alternative?

Oliver

[Apollo M. (Firma: @home) (majortom)]

Oliver S. schrieb:
> Was wäre deine Alternative?

if (count) ...

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

[Oliver S. (oliverso)]

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