C++Guns – RoboBlog blogging the bot

Wer ist schneller beim Zahlen eintippen über den Nummerntastenfeld?
Zwei Tastaturen. Ein Programm zeigt Zufallsziffern an. Wer die Zahl als erstes richtig eingetippt hat, bekommt ein Punkt. Und das Eingabefeld wird bei beiden Spielen gelöscht. Wird ein Fehler bei der Eingabe gemacht, bekommt der Spieler einen Minuspunkt und der andere Spieler hat die Möglichkeit aufzuholen. Return muss keiner drücken. Die nächste Zahl kommt, sobald sie einmal richtig eingetippt wurde.
Ist wie Tetris, nur dass man keine Blöcke richtig positionieren muss, sondern Zahlen richtig eintippen. Strange...

std::string class::func() const noexcept {
    return name.toLatin1().constData();
}

3 convertions. From QString to QByteArray to const char* to std::string. Lets see if it works. From Qt Docu

const char * QByteArray::?constData() const
Returns a pointer to the data stored in the byte array. The pointer can be used to access the bytes that compose the array. The data is '\0'-terminated unless the QByteArray object was created from raw data.

basic_string( const CharT* s, const Allocator& alloc = Allocator() )
Constructs the string with the contents initialized with a copy of the null-terminated character string pointed to by s. The length of the string is determined by the first null character. The behavior is undefined if s does not point at an array of at least Traits::length(s)+1 elements of CharT.

Okay this should work, but can fail.

Using Qt function to convert QString to std::string is the better solution:

std::string QString::toStdString() const

Diesmal hab ich mir selbst in den Fuß geschossen. Zum zweiten mal in den selben.

Alle Qt Container können nur maximal 2.1GB allocieren. Das ist eine Design Entscheidung von Qt. Dummerweise wird keine Fehlermeldung erstellt falls man mehr Speicher braucht. Ich kann schon verstehen, dass es irgendwie falsch ist, wenn eine GUI Anwendung auf einmal Tonnen von GB brauch. Aber einfach ein Absturz zulassen ist schlampig.

Warum 2.1GB? Das entspricht der Anzahl der Bytes die ein signed 32bit integer darstellen kann. Genauer 2^31 = 2,147,483,648. Das entspeicht etwas 500 millionen integer Werte. 250 millionen double Werte. Und 83 millionen x,y,z Koordinaten. Das hört sich viel an, aber wenn wir mal ehrlich sind, das ist garnichts. Gerade in der Big Data Zeit rechnet man nicht mehr in GB sondern ehr in PB.

Also, muss man in seiner GUI Anwendung so 10, 20 Zahlen speichern, dann sind die Qt Container alle gut.
Möchte man mehr wissenschaftlich arbeiten, dann nur die std Container. Alles schön trennen und streng zu sich selbst sein, dann stürzen die Programme auch nicht ab :)

Wikipedia's Kellerautomat Beispiel in C ist total falsch (Stand 11.03.2015).
Nicht nur, dass es im feinsten C programmiert ist, was kein Mensch versteht. Es wird nicht mal ein Kellerautomat implementiert. Die Konfiguration eines Kellerautomats hängt von seinem Zustand, dem zu lesenden Zeichen und dem Zeichen auf dem Stack (Keller) ab.
In dem Beispiel wird aber nur das zu lesende Zeichen und der Stack benutzt. Es gibt kein expliziten Zustand des Automaten. Vielmehr wird der Zustand in dem Kellerspeicher gespeichert. Was nicht Sinn der Sache ist. Das Beispiel verwirrt also mehr, als dass es nutzt.

Ich habe den Beispielcode nach C++ Qt übersetzt und so auch den Fehler gefunden.

#include < QCoreApplication >
#include < QTextStream >
#include < QString >
#include < QDebug >
#include < QStack > 
#include < QMap >


int main(int argc, char *argv[]) {
    QCoreApplication a(argc, argv);
    
    QStack stack;
    QTextStream ss(stdin);
    QByteArray s;

    /* Eingabestring */
    qDebug() << "Bitte Ausdruck eingeben:";

    ss >> s;
    // Wir benutzen in der  Zustandsuebergangsfunktion das Null Byte als Indikator fuer das Ende vom String.
    // Fuege es manuell in den String ein.
    s += '\0';

    /* Start-state auf Stack pushen */
    stack.push(0);

    /*
     Ein einfacher Kellerautomat ("pushdown automaton")

     Symbol   | (       | )     | \0
     ---------+---------+--------+-----------
     State 0  | PUSH 1  | ERROR  | ACCEPT
     State 1  | PUSH 1  | POP    | ERROR
    */

    enum class Actions {PUSH, POP, ERROR, ACCEPT};
    QMap< QPair< int, char>, Actions> states;
    states.insert(qMakePair(0, '('),  Actions::PUSH);
    states.insert(qMakePair(0, ')'),  Actions::ERROR);
    states.insert(qMakePair(0, '\0'), Actions::ACCEPT);
    states.insert(qMakePair(1, '('),  Actions::PUSH);
    states.insert(qMakePair(1, ')'),  Actions::POP);
    states.insert(qMakePair(1, '\0'), Actions::ERROR);


    /* Ausführungsschleife */
    bool finish = false;
    for(int i=0; i < s.size() && finish == false ; i++) {
        /* Aktion auf Basis des Eingabesymbols ermitteln */
        auto key = qMakePair(stack.top(), s.at(i));
        Actions action = states.value(key, Actions::ERROR);

        /* Ausführen der Aktionen */
        switch(action) {
        case Actions::ERROR: {
            qDebug() << "Unerwartetes Zeichen \"" << s.at(i) << "\"an Position" << i+1;
            finish = true;
            break;
        }
        case Actions::ACCEPT: {
            qDebug() << "Ausdruck akzeptiert!";
            finish = true;
            break;
        }
        case Actions::POP: {
            stack.pop();
            break;
        }
        case Actions::PUSH: {
            stack.push(1);
            break;
        }
        default:
            qDebug() << "internal error";
        }
    }

    return 0;
}

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;
}

Was ist das Problem mit folgenden Code?

    Element *ele                // uninitialisierter pointer;
    while(iter->hasNext()) {    // schleife kann auch nicht ausgefuehrt werden
        ele = iter->next();
        ...
    }
    qDebug() << ele;            // segfault
 

Wir nehmen mal an, dass qDebug() hier normalerweise nicht stehen würde. Man wollte sich aber das Element ausgeben lassen und hat vergessen die Debug Ausgabe wieder zu löschen.
Problem ist, dass die Variable ele durch qDebug dereferenziert wird, obwohl der Pointer ins Nirvana zeigen kann, wenn die Schleife nicht ausgeführt wird.
Der erste Fehler ist den Pointer nicht zu initialisieren. Man hätte ihn auf 0 (nulptr) setzen können. Das hätte den segfault aber nicht verhindert, aber das Debuggen erleichtert.
Der eigentliche Fehler ist, dass ele ausserhalb der Schleife deklariert wurde. Das Element darf nur innerhalb der Schleife existieren, da es auch nur dort gebraucht wird. Wie gesagt gäbe es im Normalfall auch keine Debug Ausgabe mit qDebug().

Leider gibt der Compiler in diesem Fall auch kein Warning aus (gcc 4.7 -Wall -Wextra)

Hier der richtige Code. Der Scope von ele wurde verkleinert und der Pointer sofort mit einer gültigen Adresse belegt.

    while(iter->hasNext()) {
        Element *ele = iter->next();
       qDebug() << ele;
    }
 

Stell dir vor, du willst die Qt Klasse QPolygonF erweitern damit man noch zusätzlich eine z Koordiante abspeichern kann.
Du erstellst also eine Klasse Polygon die von QPolygonF public erbt.
Dafür hast du dir eine Klasse Point3D erstellt, die eben x,y,z speichert. Und damit man zu Qt's QPointF Klasse kompatibel bleibt, die ja nur 2D arbeitet, kann man ein Point3D aus einem QPointF erstellen. Die Z Koordiante wird entsprechend auf 0 gesetzt.

Nun fängst du an die Klasse Polygon zu implementieren und schreibst eine push_back(Point3D) Funktion. Die x,y Koordinate wird weiter an QPolygonF::push_back() gegeben und den Z Anteil wird irgendwie in Polygon gespeichert.

Um an seine Daten wieder dran zu kommen gibt es mehere Möglichkeiten. Eine davon geht über die Funktion at(). Nun vergisst du aber gerade diese Funktion zu überladen. Kann schonmal passiert. QPolygonF (mit QVector) hat über 30 Funktionen die angepasst werden müssten. Noch dazu haben wir ja keine Zeit und der Compiler wird es auch nicht als Fehler werfen.

Hier die Datenstruktur. Unrelevate Teile hab ich weggelassen.

Hier mein kleines Testprogramm:

PolyShape poly;
Point3D pointIn(1.,2.,3.);
qDebug() << "put in " << pointIn.x << " "<< pointIn.y << " " << pointIn.z; poly.push_back(pointIn); Point3D pointOut = poly.at(0); qDebug() << "get out" << pointOut.x << " "<< pointOut.y << " " << pointOut.z;

Ich gebe also ein Punkt mit den Koordianten 1, 2, 3 in das Polygon ein und erwarte, dass der selbe Punkt wieder rauskommt.

Starting /home/kater/qtcode/test2/test2...
put in 1 2 3
get out 1 2 0

So ein Mist! Die Z Koordinate ist verschwunden! Aber ist ja auch kein Wunder. Da Polygon kein at() hat, wird die entsprechende Funktion von QPolygonF ausgerufen. Die speichert aber nur QPointF und keine z Koordiante.
Der Fehler passiert, wenn man ein QPointF einem Point3D zuweist. Durch den entsprechenden Konstructor in Point3D klappt das auch, aber wollten wir das so eigentlich?

Man kann mit dem Keyword explicit in diesem Fall einem Compilerfehler erzwingen.

explicit Point3D(const QPointF & point);


main.cpp:62: error: conversion from 'const QPointF' to non-scalar type 'Point3D' requested

Verwende explicit immer dort, wo der Konstructor nur ein Argument hat und es nicht der Copy Ctor ist.

Besser wäre es aber ein anderes Design zu finden. Jede Funktion von QPolygonF zu überladen klingt nicht so gut. Vllt. kommen in der Zukunft ein paar neue hinzu oder es fallen einige weg. Noch mehr Arbeit...