FIFO Stack

Fru

Hallo alle miteinander!

Ich schreibe momentan eine Klasse namens FifoStack, die als push/pop Überladene Bitshift-Operatoren verwendet. Die Klasse verwaltet eine einfach verkettete Liste von einem Typ, der als Element ein *next hat.

Zur Zeit habe ich Probleme bei der push Methode.. Ich möchte gerne mein this->root auf dem "Anfang" meiner Liste behalten. Die ersten zwei Einträge funktionieren auch wunderbar, aber danach ändert sich aus irgendwelchen Gründen der Zeiger meiner Hilfsvariable tmp, die ich als static deklariert habe.

Meine Idee war eben, dass tmp immer auf den Speicherbereich meines letzen Elementes meiner Liste zeigt, doch irgendwann scheint sich tmp von meiner this->root zu "trennen". Ich sehe aber nicht, warum:

Die relevante Funktion sieht so aus:

FifoClass& FifoClass::operator<<(const Aktie &a) {
    static Aktie *tmp = this->root;
    Aktie * copy = new Aktie(a); // Erstelle Kopie

    if(this->root == NULL) {
        this->root = copy;
        tmp = this->root;
    } else {
        tmp->setNext(copy);
        tmp = tmp->getNext();
    }

    ++this->count;

    return *this;
}

Sollte der Code nicht ausreichen, poste ich gerne noch den Rest dazu.

Liebe Grüße,
Fru

DrakoXP

Zunächst mal gibt es keinen FIFO Stack.
Ein Stack ist ein IMMER LIFO (wegen der Metapher),
die FIFO Variante ist also die Queue.

Desweiteren halte ich deine statische tmp-Variable für höchst überflüssig...

FifoClass& FifoClass::operator << (const Aktie &a) {
    Aktie * copy = new Aktie(a); // Erstelle Kopie

    if (!root) {
        root = copy;
    } else {
        // Gehe ans Ende der Queue
        Aktie * tmp = root;
        while (tmp->getNext())
            tmp = tmp->GetNext();
        tmp->setNext(copy);
    }

    ++count;

    return *this;
}

Die obige Variante geht davon aus, dass deine Klasse nur root und count als Attribute hat.
Performanter würde es, wenn du neben root auch noch einen Zeiger auf das Ende speichern würdest:

FifoClass& FifoClass::operator << (const Aktie &a) {
    Aktie * copy = new Aktie(a); // Erstelle Kopie

    // Das Attribut "end" ist ein Aktie * und soll immer auf das Ende zeigen
    // Bei count == 1 gilt end == root
    // Bei count == 0 gilt end == NULL
    if (!root) {
        end = root = copy;
    } else {
        end->setNext(copy);
        end = end->getNext();
        // oder -> end = copy (weil copy ja theoretisch das gleiche sein sollte wie end->getNext()
        // und du hier einen Funktionsaufruf sparen kannst...
    }

    ++count;

    return *this;
}

Fru

Wegen der Perfomance wollte ich es gerne mit einer statischen Variable löse, die sich so ähnlich wie eine end-Member-Variable verhalten müsste.

theta

Fru schrieb:

Wegen der Perfomance wollte ich es gerne mit einer statischen Variable löse, die sich so ähnlich wie eine end-Member-Variable verhalten müsste.

Nicht nur dass es höchstwahrscheinlich überhaupt keinen messbaren Einfluss auf die Performance hat - es zerstört auch die Verwendung von mehreren Objekten deiner Klasse - geschweige denn von Objekten deiner Klasse unter mehreren Threads.

Wenn es einen Einfluss hat, dann eher einen negativen - es steht zu erwarten, dass der gegenwärtige Stackframe sich bereits im L1-Cache befindet, wohingegen die statische Variable unter Umständen einen Gang bis zum Hauptspeicher benötigen kann. Ferner ist es gut möglich, dass der Compiler eine lokale Variable an dieser Stelle gleich in ein Register legt. Von der Performance ganz unabhängig verbietet sich dieses Vorgehen aber aufgrund der von theta genannten Gründe sowieso.

Wenn dir deine Queue zu langsam ist, würde ich eher den Ansatz der einfachen verketteten Liste überdenken - moderne CPUs sind darauf getrimmt, Lokalität zu belohnen, d. h. es kann eine Menge bringen, zusammengehörige Daten in zusammenhängenden Speicherstücken aufzubewahren. Das gilt insbesondere dann, wenn viele Elemente direkt hintereinander aus der Queue geholt werden bzw. in sie gestopft werden sollen.

Fru

Ah okay, gecheckt.
Vielen Dank Euch dreien!