Design-Ideen gesucht

HumeSikkins

Hallo,
ich stehe hier vor einem Design-Problem, dass mich schon seit längerem beschäftigt (ich habe mittlerweile auch drei Implementationen) und wollte mal Fragen, ob ihr vielleicht noch eine gute Lösungsidee habt.

Hier eine stark vereinfachte Beschreibung meiner Situation:

Kontext:
Ich habe einen (statischen) Graphen, der zu beginn viele ungefärbte Knoten enthält. Ziel ist es alle ungefärbten Knoten zu färben.
Dazu werden viele viele verschiedene Schritte und Operationen durchgeführt, die hier aber nicht weiter wichtig sind.
Wichtig ist, dass zu bestimmten Zeitpunkten a) durch die Menge aller gerade ungefärbten Knoten iteriert und b) zu anderen Zeitpunkten aus dieser Menge der "beste" ungefärbte Knoten ausgewählt werden muss.
Um entscheiden zu können, welcher Knoten der "beste" ist, bedarf es einer Bewertung. Sowohl der Zeitpunk, wann die Bewertung stattfindet als auch die Implementation der Bewertungsfunktion sind dabei variabel (pro Programmlauf. Innerhalb eines Laufs bleibt beides stabil).

Zusammengefasst:
Ich habe eine Menge von ungefärbten Knoten deren Größe zur Laufzeit
ständig variiert. Die maximale Größe steht aber zum Startzeitpunkt fest.

Die Menge braucht die folgenden Basis-Funktionen:
* Knoten hinzufügen, Anforderung: Schnell
* Knoten entfernen, Anforderung: Schnell
* Knoten iterieren

Außerdem braucht sie eine Operation getBestNode, die den besten Knoten liefert.

Problem:
Die Bewertung der Knoten geschieht entweder:
1. Einmal am Anfang des Programms (der Wert bleibt danach immer Gleich)
2. Jedesmal bevor der Knoten mit dem höchsten Gewicht ausgewählt werden soll
3. Dynamisch durch andere Objekte (sprich: zwischen zwei Aufrufen von
getBestNode ändert sich das Gewicht von manchen Knoten).

Meine Frage: Wie implementiere ich das Ganze so, dass alle Fälle ordentlich performant sind (für den ersten Fall würde es z.B. sinn machen, wenn die Knoten sortiert gespeichert werden), gleichzeitig aber Client-Code unabhängig von den Implementationsdetails ist?

Wer sich selbst was ausdenken will, sollte hier erstmal aufhören zu lesen.

Für diejenigen die lieber meine derzeitige Lösung kritisieren möchten geht's unter dem Strich weiter

-------------------------------------------------------------------------------
Meine derzeitig bevorzugte Version (der Code ist natürlich nur Pseudo-Code)

1. Für den Client-Code gibt's eine (abstrakte) Basisklasse. Diese implementiert die Basisoperationen. Sie Speichert die Knoten in einer hash_set. Was die Basisoperationen relativ schnell macht:

class UncoloredNodesBase {
    typedef hash_set<Node*>::iterator Iterator;
public:
    void addNode(Node* n) { nodes_.add(n); doAddNode(n); }
    void removeNode(Node* n);

    // wird einmal am Anfang des Programms aufgerufen
    virtual void stable() = 0;

    virtual Node& getBestNode() = 0;

    Iterator begin();
    Iterator end();
private:
    virual void doAddNode(Node* n) = 0;
    virual void doRemoveNode(Node* n) = 0;
    hash_set<Node*> nodes_;
};

2. Eine Template-Klasse die von der Basisklasse erbt. Der Template-Parameter
Heu ist der Typ, der die Heuristik festlegt, nach der der beste Knoten
ausgewählt wird.

template <class Heu>
class UncoloredNodes : public UncoloredNodesBase {
public:
    void stable() { heu.stable(begin(), end()); }
    Node& getBestNode() { heu.getBestNode(begin(), end()); }
private:
   void doAddNode(Node& n) { heu.addNode(n); }
   void doRemoveNode(Node&) { heu.removeNode(); }
   Heu heu;
};

3. Eine Template-Klasse für den ersten Fall (Bewertung einmal am Anfang des Programms). In stable werden einmal alle Knoten bewertet und dann in einer std::multiset gespeichert (also sortiert).

template <class Impl>
class StaticHeuristic {
public:
    typedef typename Impl::Compare_Type CompareType;
    typedef typename Impl::Evaluate_Type EvaluateType;
    // einmal alle Knoten bewerten und dann sortiert speichern
    template <class Iter>
    void stable(Iter begin, Iter end) {
        stable_ = true;
        for_each(Node* n in [begin, end)) {
            evaluator_(n);  // bewerten
            sortedNodes_.insert(n);
        }
    }
    template <class Iter>
    Node* getBestNode(Iter, Iter) const {return *nodes_.begin();}

    void addNode(Node* n) { if (stable_) sortedNodes_.insert(n); }
    void removeNode(Node* n) { if (stable_) sortedNodes_.erase(n); }
private:
    EvaluateType evaluator_;
    std::set<Node*, CompareType> sortedNodes_;
};

4. * Eine Template-Klasse für den zweiten Fall

template <class Impl>
class DynamicHeuristic {
public:
    typedef typename Impl::Compare_Type CompareType;
    typedef typename Impl::Evaluate_Type EvaluateType;

    template <class Iter>
    void stable(Iter, Iter) { /* nothing to do */ }

    template <class Iter>
    Node* getBestNode(Iter begin, Iter end) {
        for_each(Node* n in [begin, end)) {
            evaluator_(n);
        }
        return max_element(begin, end, CompareType());
    }
    void addNode(Node*) {}
    void removeNode(Node*) {}
};

5. Eine Template-Klasse für den dritten Fall (wie DynamicHeuristic nur
werden hier die Knoten vor dem Vergleich nicht erst bewertet).

6. Viele Klassen für den tatsächlichen Vergleich bzw. für die Bewertung.
Bsp:

class Random {
public:
    struct Compare {
        bool operator()(const Node* n1, const Node* n2) const {
            return n1->getVal() > n2->getVal();
        }
    };
    struct Evaluate {
        bool operator()(Node& n) const {
            n->setVal(rand() % 1024);
        }
    };
    typedef Compare CompareType;
    typedef Evaluate EvaluateType;
};
// Wertet den Lookahead-Wert aus, den ein anderes Objekt vorher gesetzt hat
class CmpLookaheadValue {
public:
    struct Compare {
        bool operator()(const Node* n1, const Node* n2) const {
            return n1->extractValue<int>("LookaheadValue") >
                n2->extractValue<int>("LookaheadValue");
        }
    };
    typedef Compare CompareType;
};

typedef UncoloredNodes<StaticHeuristic<Random> > SR_Heu;
typedef UncoloredNodes<DynamicHeuristic<Random> > DR_Heu;
typedef UncoloredNodes<OperatorBasedHeuristic<CmpLookaheadValue> > Lookahead_Heu;

7. Instanziieren:

// Fall 1: statische Heuristik - Bewertung: Random
UncoloredNodesBase* b = new SR_Heu();
...
// Fall 2: dynamische Heuristik - Bewertung: Random
UncoloredNodesBase* b = new DR_Heu();

// Fall 3: Wert wird von einem anderen Objekt gesetzt. Heuristik wertet nur aus
UncoloredNodesBase* b = new Lookahead_Heu();

Offensichtliche Nachteile:
* Fall 1 speichert die Knoten doppelt
* Fall 2 und Fall3 haben einen unnötigen virtuellen Aufruf, wann immer ein Knoten hinzugefügt/entfernt wird.

Andere Idee:
Man macht den Iterator zu einem polymporphen Objekt, spart sich die dadurch die Template-Klasse UncoloredNodes und leitet die drei Klassen direkt von der abstrakten Basisklasse ab. Fall 1 speichert dann eine multiset. Fall 2 und Fall 3 jeweils eine hash_set.
Offensichtlicher Nachteil:
* Iterieren ist teuer.

So, ich hoffe das Ganze ist trotz der starken Vereinfachung noch verständlich genug und ihr habt ein paar gute Ideen für mich.

otze

Was sind ungefärbte/gefärbte Knoten? den begriff hör ich jetzt zum ersten mal.

pli

otze schrieb:

Was sind ungefärbte/gefärbte Knoten? den begriff hör ich jetzt zum ersten mal.

Faerbbarkeit eines Graphen, ist ein NP-schweres (glaub ich) Problem der Algorithmik. 2 benachbarte Knoten duerfen nicht die gleiche Farbe haben.
Anwendung: politische Landkarten, benachbarte Laender duerfen nicht die gleiche Farbe haben und die Anzahl der Farben soll minimal sein.

pli

Als Datentyp fuer deine Knoten, nimm doch einfach eine Priority Queue (ist sogar in der STL meines Wissens) mit deiner Bewertung als Referenzwert, so steht der beste Wert immer am Kopf der Queue.

Denke hier kannst du sehr viele Infos zu deinem Problem finden:
http://www.algo.informatik.tu-darmstadt.de/ Unter Lehre->WS04/05->Effiziente Graphenalgorithmen, stehen auch die Laufzeiten fuer die verschiedenen Operationen drin

HumeSikkins

pli schrieb:

Als Datentyp fuer deine Knoten, nimm doch einfach eine Priority Queue (ist sogar in der STL meines Wissens) mit deiner Bewertung als Referenzwert, so steht der beste Wert immer am Kopf der Queue.

Eine Priority-Queue kann ich nur für Fall 1 benutzen. Für die anderen Fälle funktioniert ein Priority-Queue nicht. Für Fall 1 hat eine Priority-Queue allerdings genau die gleichen Nachteile wie eine set. Sprich: Ich muss die Knoten doppelt speichern. Allein schon, weil man durch eine PQ weder iterieren kann noch an beliebigen Stellen löschen. Beides sind aber Operationen die ich brauche.

Denke hier kannst du sehr viele Infos zu deinem Problem finden:
http://www.algo.informatik.tu-darmstadt.de/ Unter Lehre->WS04/05->Effiziente Graphenalgorithmen, stehen auch die Laufzeiten fuer die verschiedenen Operationen drin

Wie helfen mir Graphenalgorithmen in dieser Situation? Ich bin auch stolzer Besitzer von Sedgewicks "Algorithms in C++ - Part 5 Graph Algorithms". Aber keiner der dort beschriebenen Algorithmen löst meine derzeitige Situation, da diese eigentlich wenig mit klassischen Graphen zu tun hat.

Trotzdem schonmal danke für die Anregungen.

Was sind ungefärbte/gefärbte Knoten? den begriff hör ich jetzt zum ersten mal.

Ist in diesem Kontext nicht wichtig. Wichtig ist nur, dass ich eine Menge von Knoten habe, die ein bestimmtes Attribut besitzen. Der Wert des Attribut verändert sich laufend.

Wen's interessiert: Das Anwendungsgebiet ist die Berechnung von Antwortmengen (auch stable models gennat). Die Knoten sind Teil eines Body-Head-Graphens, der die Abhängigkeiten der Regeln eines Logischen Programms beschreibt. Ungefärbte Knoten sind Choice-Point-Kandidaten sowie Kandidaten für Lookahead-Operatoren.
Aber das ist für mein konkretes Problem eigentlich alles nicht relevant.

otze

Gut. hab mir jetzt was überlegt:

ich hab hier was für den ersten Fall, ich setz hierbei voraus, dass UncoloredNodesBase ein public typedef auf Iterator hat:

template <class Impl>
class StaticHeuristic {
public:
    typedef typename Impl::Compare_Type CompareType;
    typedef typename Impl::Evaluate_Type EvaluateType;
    typedef UncoloredNodesBase::Iterator Iter;

    void stable(Iter begin, Iter end) {
        for_each(Node* n in [begin, end]){
            evaluator_(n);  // bewerten
        }
        bestNode=max_element(begin, end, CompareType());
        this->begin=begin;
        this->end=end;
    }
    template <class Iter>
    Node* getBestNode(Iter, Iter) const {return bestNode}

    void addNode(Node* n) {
        evaluator_(n);
        if(n->getVal()>bestNode->getVal()){
            bestNode=n;
        }
    }
    void removeNode(Node* n) {
        if(n==bestNode){
             bestNode=max_element(begin, end, CompareType());
        }
    }
private:
    Iter begin;
    Iter end;
    Node* bestNode;
    EvaluateType evaluator_;
};

HumeSikkins

Sehr schön!

Hat aber noch ein kleines Problem: Der Iterator begin kann ungültig werden. Kann man aber recht einfach lösen, in dem man removeNode neben dem Knoten auch noch die beiden Iteratoren die die Sequenz markieren mitgibt. end bleibt zwar stabil und man könnte deshalb auf die Übergabe verzichten. Aber von der Logik wäre es imo einfacher.

Hat sich ja schon gelohnt, dass ich hier gefragt habe. Danke!

HumeSikkins

Zu früh gefreut

Da die Auswahl des Besten Knotens immer auch dazu führt, dass dieser aus der Menge entfernt wird, hat deine Lösung für die Auswahl des Besten Knotens ein Laufzeitverhalten von O(n). Was ich ja gerade verhindern wollte

otze

das bedeuted, dass irgendwo in deinem programm ein

Node& n=SR_Heu.getBestNode();
SR_Heu.removeNode(&n);

steht?

das ist natürlich bitter...

vielleicht hilft ja ein zwischending aus deiner und meiner lösung?

das man zb nur die besten 5/10/15 nodes in einem set speichert.
müsstest dann halt nichtmehr alles doppelt speichern, hast aber immer einen puffer.

HumeSikkins

otze schrieb:

das bedeuted, dass irgendwo in deinem programm ein
Node& n=SR_Heu.getBestNode();
SR_Heu.removeNode(&n);
steht?

Zumindest vom Effekt her, ja. Der Tatsächliche Code ist natürlich komplizierter

das man zb nur die besten 5/10/15 nodes in einem set speichert

Daran habe ich auch schon gedacht.

Das blöde ist: Das Problem ließe sich trivial lösen, wenn es sowas wie virtuelle Template-Funktionen gäbe. Kluge Leute haben mir aber erklärt, dass ein Design, das virtuelle Template-Funktionen braucht einen Design-Fehler enthält. Dumm nur, dass ich diesen nicht finde

otze

Das blöde ist: Das Problem ließe sich trivial lösen, wenn es sowas wie virtuelle Template-Funktionen gäbe

sorry, ich komm nicht drauf, wie soll das hier helfen? haben die nodes eine bestimmte Eigenschaft, auf die du dann zurückgreifen kannst?

HumeSikkins

sorry, ich komm nicht drauf, wie soll das hier helfen?

Was ich brauche ist eine Möglichkeit wie ich
begin- und end so implementieren kann, dass der Iterator-Typ variable ist ohne das er dazu polymorph sein muss.
Dann könnte ich das Problem effizient lösen. Fall 1 würde die Knoten in einer set speichern und begin und end würde set::iteratoren liefern. Fall 2 und Fall 3 würden die Knoten in einer hash_set speichern und hash_set::iteratoren liefern.
Verwendet man nun internal- statt external-Iteratoren könnte man das Ganze mit virtuellen Templates so lösen:

class UncoloredNodes {
public:
	template <class P>
	virtual void for_each(P p) = 0;
};

class Static : public UncoloredNodes {
public:
	template <class P>
	virtual void for_each(P p) {
		for_each(s_.begin(), s_.end(), p);
	}
private:
	set<Node*> s_;
};

class Dynamic : public UncoloredNodes {
public:
	template <class P>
	virtual void for_each(P p) {
		for_each(s_.begin(), s_.end(), p);
	}
private:
	hash_set<Node*> s_;
};

Ohne virtuelle Templates muss P ein polymorpher Typ sein. Das wäre dann aber Geschwindigkeitstechnisch das selbe wie ein polymorpher Iterator.