C++Guns – RoboBlog blogging the bot

Kurzes Programm, welches überpüft ob der Benutzer eine Variable "resolution" definiert hat. Wenn ja, wird versucht die Benutzereingabe in eine Zahl umzuwandeln. Wenn nein, wird ein default Wert von 1 angenommen.

Variante 1:

const QString resolution = options().text("resolution");
bool userResolution = false;
// check if user defined cellsize
qreal newCellSize = 1;
if(!resolution.isEmpty()) {            
  userResolution = true;
  bool ok;
  const qreal userCellSize = resolution.toDouble(&ok);
  if(ok) {
    newCellSize = userCellSize;
  }
  else {
    qDebug() << "Cant parse user defined resolution:" << resolution;
  }
}

Die Variable userResoltion ist nicht als const declariert und könnte überschrieben werden. Machen wir sie read-only!

Variante 2:

const QString resolution = options().text("resolution");
const bool userResolution = !resolution.isEmpty();
// check if user defined cellsize
qreal newCellSize = 1;
if(!resolution.isEmpty()) {            
  bool ok;
  const qreal userCellSize = resolution.toDouble(&ok);
  if(ok) {
    newCellSize = userCellSize;
  }
  else {
    qDebug() << "Cant parse user defined resolution:" << resolution;
  }
}

Der Code sieht noch etwas aufgebläht aus. Trennen wir den normalen Programm Path und den Error Path, der durchlaufen wird, wenn die Benutzereingabe ungültig ist.

Variante 3:

qreal toDouble(const QString& s) throw(Exception) {
    bool ok;
    qreal x = s.toDouble(&ok);
    if(!ok)
        throw Exception("Cant convert to double" + s);
    return x;
}

...

const QString resolution = options().text("resolution");
const bool userResolution = !resolution.isEmpty();
// check if user defined cellsize
qreal newCellSize;
try {
      newCellSize = toDouble(resolution);
}catch(...) {
      newCellSize = 1.0;
      if(!resolution.isEmpty())
           qDebug() << "Cant parse user defined resolution:" << resolution;
}

Nun möchten wir die Variable newCellSize auch noch read-only haben, da sie ein Parameter ist und niemals mehr geändert werden darf. Dafür lagern wir nun die komplette Logik für das Parser der Benutzereingabe in eine Funktion aus.

Variante 4:

qreal toDouble(const QString& s, qreal defaultValue = 0.0) {
    if(s.isEmpty())
        return defaultValue;

    bool ok;
    qreal x = s.toDouble(&ok);
    if(!ok) {
        qDebug() << "Cant convert to double" + s;
        return defaultValue;
    }
    return x;
}

...

const QString resolution = options().text("resolution");
const bool userResolution = !resolution.isEmpty();
// check if user defined cellsize
const qreal newCellSize = toDouble(resolution, 1.0);

Der wesentliche Code ist jetzt nur noch 4 Zeilen lang, statt 15 Zeilen.
Er ist auf das wesentliche reduziert, verständlicher und gegen das versehentliche überschreiben der Variablen geschützt.
Nachteile gibt es allerdings auch. Die Fehlermeldung wenn das Konvertieren fehl schläng ist nicht anpassbar. Mit einem zustäzlichen Funktionsargument könnte man das aber nachbessern.

Es gibt viele Möglichkeiten den Median zu berechnen. Eine wäre die Daten zu sortieren und dann das mittlere Element zu wählen.
Dazu muss man aber eine Kopie der Daten speichern, was ungünstig ist, wenn der Arbeitsspeicher schon fast voll ist. Jaaa, heutzutage hat jeder Unmengen an Arbeitsspeicher. Es gibt aber Menschen die haben "NUR" 2GB RAM und die sind durch die aufgeblasenen Standardprogramme (Browser, Office, Mail, Clould, Solzial) schon zu 85% belegt. Und wenn man dann noch etwas Arbeiten will und sich ein paar Datensätze visualisiert, können schon 50MB mehr zum Überlaufen des RAMs führen ;)

(50MB entsprechen ca. 7Millionen double Variabeln)

Es wäre doch toll, wenn man den Median berechnen könnte, ohne den Datensatz zu verändern oder zu kopieren!

Eine Runde googlen:
http://stackoverflow.com/questions/638030/how-to-calculate-or-approximate-the-median-of-a-list-without-storing-the-list/638713#638713

Ich hab diesen Algorithmus mal in Qt implementiert und ein wenig verändert. Bei einer grade Anzahl von Eingangsdaten berechnet er ursprüngliche Algorithmus den falschen Median. Ich habe es jetzt so geändert, dass immer das oberste der beiden mittleren Elemente im Array zurückgegeben wird. Das kann man irgendwann auch noch mal verbessern.

Noch ein Wort zur Laufzeit. Die Anzahl der Iterationen betrug bei meinem Tests meist so um die 50. Das muss eigentlich auch so sein, denn wir haben es hier mit einer binären Suche zu tun. Denn bei jeder Iteration wird der Zahlenbereich, der mit einer double precision floating number Variable dargestellt werden kann, in 2 Hälften zerlegt. So tanzt der approximierte Median immer um den echten Median herrum, bis die Zahlengenauigkeit fein genug ist.
Mit double Precision bekommt man etwa 16 Ziffern Genauigkeit. Und der 2er Logarithmus von 50 ergibt eine Zahl mit 16 Ziffern. Das passt doch :D Man muss also immer 50mal den Zahlenbereich aufteilen um an den Median zu kommen.

Bei jeder dritten Iteration bekommt man also etwa eine Ziffer an Zahlengenauigkeit dazu. Gibt man sich mit nur 8 Ziffern Genauigkeit zufrieden, braucht man auch nur 25 Iterationen.

Wir haben also einen Agorithmus dessen Laufzeit linear mit der größe des Datensatzes wächst O(n*50). Das ist doch super! Ganz anders als die Variante welches erst die Daten sortiert O(n*log(n)). In der Praxis bringt einem das aber erstmal nichts an Laufzeit. Denn wie groß muss der Datensatz werden, damit der log(n) = 50 wird? 1,125,899,906,842,624 ! Also erst ab einer Billiarden Zahlen hätten wir ein Laufzeitvorteil. Dazu bräuchte man aber auch 8000 Terrabyte an Speicherplatz :D

Gibt man sich in Qt/C++ eine Zahl in der Konsole aus, bekommt man in der Regel nur 6 Ziffern angezeigt. Das entspricht 18Iterationen. Also log(n) = 18 für n = 262,144 Hier sieht die Welt schon besser aus. Schon ab 260,000 Zahlen bekomen wir ein Laufzeitvorteil.

Wir haben also ein Algorithmus, der keinen zusätzlichen Speicherplatz braucht und auch noch in der Laufzeit einstellbar ist. Gibt man sich nur mit wenigen relevanten Ziffern des approximierten Medians zufrieden, ist die Laufzeit schon bei kleinen Datenmengen besser als die des Sortierverfahrens.

Happy coding ;)

/*
Find Min and Max of the list containing N items through linear search and name them as HighValue and LowValue Let MedianIndex = floor(N/2)

1st Order Binary Search:

Repeat the following 4 steps until LowValue < HighValue.

    Get MedianValue approximately = ( HighValue + LowValue ) / 2

    Get NumberOfItemsWhichAreLessThanorEqualToMedianValue = K

    is K > MedianIndex ? then HighValue = MedianValue Else LowValue = MedianValue


  */
/*!
  Return the median. If data has even size, not the avg of the two numbers in the
  middel of the array is returned, but the upper one.

  This is an improved version from
  http://stackoverflow.com/questions/638030/how-to-calculate-or-approximate-the-median-of-a-list-without-storing-the-list/638713#638713

  This algorithm need in practice 50 iterations. Like a binary search around the true median.
  */
qreal experimenalMedian(const QVector &data) {
    if(data.isEmpty())
        return 0.0;

    QPair minmax = qMinMax(data);
    int medianIdx = qFloor(data.size()/2.0);
    qreal medianValue = (minmax.first + minmax.second)/2.0;

    while(minmax.first < minmax.second &&
          !fuzzyCompare(minmax.first, minmax.second)) {
        medianValue = (minmax.first + minmax.second)/2.0;
        int K = 0;
        for(int i=0; i < data.size(); i++) {
            if(data.at(i) <= medianValue) {
                K++;
            }
        }
        K > medianIdx ? minmax.second = medianValue : minmax.first = medianValue;
    }
    return medianValue;
}