Performance Tuning

Performance-Defizite in Software-Systemen verursachen in vielen Unternehmen jährliche Ausgaben in Millionenhöhe. Eine gezielte Performance-Optimierung spart häufig über 30% der Infrastrukturkosten, sichert die rechtzeitige Verarbeitung wichtiger Daten und reduziert Wartezeiten für Anwender.

Decke die relevanten Performance-Mängel unseres Code-Beispiels auf und optimiere seine Laufzeit! Kompiliert wird mit folgendem Kommando: g++ –std=c++11 -O3. Die aktuelle Laufzeit des nicht optimierten Codes beträgt 5,677s.

Gegeben ist eine allgemeine Implementierung, die besonders oft für einen Spezialfall gebraucht wird. Entsprechend soll der Code für diesen Fall optimiert werden – ohne dass die allgemeine Gültigkeit verletzt wird.


#include <vector>
#include <algorithm>

#include <stdlib.h>

template<typename X>
void qs(std::vector<X>& ts, const int l, const int r) {
  int i = l, j = r;
  X p = ts[r];

  while (i <= j) {
    while (ts[i] < p) i++; while (ts[j] > p) j--;
    if (i <= j) {
      std::swap(ts[i], ts[j]);
      i++;
      j--;
    }
  }

  if (l < j) qs(ts, l, j);
  if (i < r) qs(ts, i, r);
}

Der Vektor kann mehr als 10 Mio. Elemente mit max. 101 unterschiedlichen Werten enthalten.

Mit folgendem Code kannst du die Funktion testen. Diese wird hierbei für den oben genannten Spezialfall aufgerufen:

#include <random>
#include <functional>
#include <chrono>

#include <stdio.h>

int main() {
    int len = 100000000;
    std::vector<int> input;

    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::default_random_engine generator(seed);
    std::uniform_int_distribution<int> distribution(0, 100);
    auto rollDice = std::bind(distribution, generator);

    for (int i = 0; i < len; i++) {
       input.push_back(rollDice());
    }

    auto start = std::chrono::system_clock::now();
    qs(input, 0, input.size() - 1);
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - start);

    printf("Median: %d\n", input[len/2]);
    printf("Time: %d ms\n", duration.count());

    return 0;
}

Wie viel Laufzeitreduzierung schaffst du?

Lösung hochladen. Laufzeit checken.

Bist du unter den Top 10?






Ich habe die Datenschutzhinweise gelesen und akzeptiert. Ich stimme zu,
dass meine Angaben und Daten zur Beantwortung meiner Anfrage
elektronisch erhoben und gespeichert werden.*
Hinweis: Sie können Ihre Einwilligung jederzeit widerrufen.

 

itestra Tuning-Champion

Pseudonym Zeit
isk 0,124 s
Ben2 0,132 s
Cor4 0,142 s
Mnemonix 0,143 s
Bolpat 0,156 s
ne 0,156 s
Chessy95
0,160 s
sap 0,166 s
rauhfasertapete 0,176 s
Kong 0,177 s