Datenstruktur für "Beste X Elemente"



  • Hallo,
    ich benötige da mal eure Hilfe. Und zwar möchte ich maximal X Elemente vom Typ T abspeichern und habe eine absolute Ordnung zwischen diesen.
    Wenn ein T hereinkommt, wird es einsortiert. Falls die Liste bereits voll war, fällt das schlechteste Element raus (könnte auch das neueste T sein).
    Außerdem muss ich T's entfernen können und muss wissen wenn sich das beste T verändert.

    Irgendwie so müsste das Interface aussehen:

    template< typename T, typename id_type, size_t size, typename Order >
    struct container {
    
        bool insert( const T& foo ); // true wenn bestes Element verändert
                                     // falls voll, wird das schlechteste Item
                                     // rausgeworfen um Platz zu machen.
                                     // falls id_type(foo) schon gespeichert ist
                                     // wird das entsprechende element entfernt
                                     // und foo neu einsortiert
    
        bool remove( id_type foo ); // true wenn bestes Element verändert
    
        T* find( id_type );
        T* best();
    
        size_t size() const;
    
    private:
        std::array<T, size> elements_;
        // Alles was benötigt wird um das umzusetzen...
    };
    

    Ich war jetzt am überlegen, zwei Heaps mit Zeigern auf ein festes Array mit free-list umzusetzen, aber vielleicht fällt euch etwas ein, was einfacher umzusetzen ist, oder eine fertige Lösung die ich total übersehe?

    Dankeschön!



  • 1x array für elemente+status(frei/belegt)
    1x heap für prio mit pointer auf element

    wofür ist der zweite heap gedacht?



  • Der zweite Heap war jetzt dafür gedacht, schnell das schlechteste Element zu finden, das rausgeschmissen werden muss, falls der Container bereits voll war und das neue Element besser als das schlechteste ist.



  • Alles klar, mir erscheint ein interval-heap als sehr elegant, auch wenn ich jetzt keinen fertigen Source-Code dafür finden kann. Werde ich jetzt mal umsetzen bis ihr vielleicht eine bessere Idee habt... 🙂



  • Falls size ausreichend klein ist (sagen wir mal bis ca. 100) dann würde es ein einfaches sortiertes Array aus Zeiger auch tun.



  • ja dazu bin ich jetzt übergegangen, denn ich muss auch Elemente entfernen können, wenn ein keep-alive-timer ausläuft und zusätzlich können sich die einzelnen Elemente zeitweise verändern, was die Ordnung durcheinander wirft... Glaub kaum, dass es dafür bei kleinen Datenmengen eine effiziente Struktur gibt... wird mir jetzt auch zu kompliziert irgendwie.



  • datenstrukturator schrieb:

    ich benötige da mal eure Hilfe. Und zwar möchte ich maximal X Elemente vom Typ T abspeichern und habe eine absolute Ordnung zwischen diesen.
    Wenn ein T hereinkommt, wird es einsortiert. Falls die Liste bereits voll war, fällt das schlechteste Element raus (könnte auch das neueste T sein).
    Außerdem muss ich T's entfernen können und muss wissen wenn sich das beste T verändert.

    Was für Ts möchtest Du denn entfernen können? Beliebige? Oder eben nur das "beste"/"schlechteste"? Im letzten Fall kann dir eine "double ended priority queue" helfen. Eine Möglichkeit, so eine Queue zu bauen, ist ein Intervall-Heap. Einen Intervall-Heap habe ich selbst mal (in Rust) geschrieben und veröffentlicht. Die Schnittstelle würde in C++ so aussehen:

    template<class T>
    class interval_heap
    {
       ...
       unsigned len() const;
       T const& min() const; // precondition: len() > 0
       T const& max() const; // precondition: len() > 0
    
       void insert(T);
       T pop_min(); // precondition: len() > 0
       T pop_max(); // precondition: len() > 0
       ...
    };
    


  • Ok, sehe gerade, dass du auch belieige Elemente löschen können willst. Spricht eigentlich etwas gegen eine std::map ?



  • Ja, so einen interval-heap hatte ich ja schon begonnen zu implementieren, bis mir dann aufgefallen ist, dass er meine Probleme leider auch nicht löst (in der idealen Welt würde er es natürlich). Andererseits werden die Keep-Alive timer wahrscheinlich nicht allzu oft auslaufen und sich auch die Schlüssel, nach denen sortiert wird nicht allzu oft ändern. In den speziellen fällen könnte ich dann auch einfach den heap neu aufbauen (wobei das natürlich den worst-case ziemlich "worst" macht... keine Ahnung ob das so eine gute Idee ist). Vielleicht wenn ich die Muße habe, funktioniert ja jetzt auch so.
    Map und Konsorten sind nicht so gut, weil ich hier gerade auf einem Mikrocontroller unterwegs bin und mich jetzt nicht noch mit maßgeschneiderten Allokatoren rumprügeln möchte. Fand den In-Place-Interval-Heap schon relativ passend ansonsten.



  • Aber auf jeden Fall vielen Dank, dass Du Dich damit auseinander gesetzt hast! Sollte wohl mal erwähnt werden, hehe.



  • So ein in einem Vector lebender Intervall-Heap kann auch ein beliebiges Element effizient -- also O(log n) -- löschen, sofern du den Index kennst. Man händelt das genauso wie beim Löschen des Min oder Max-Wertes, der in der Wurzel steht, mit dem Unterschied, dass man eben nicht in der Wurzel anfängt, sondern schon tiefer im Baum.

    Das Problem ist hier nur, das zu löschende Element zu finden, welches ja im Array nicht unbedingt immer an derselben Stelle bleibt, wenn man noch neue Elemente hinzufügt und andere löscht. Wenn das aber nicht so oft vorkommt, reicht ja vielleicht auch die lineare Suche.

    Alternativ baut man eine Indirektion ein. Im Heap stünden dann selbst nur Indizes oder Adressen der Elemente, die dann in einem anderen Array irgendwo liegen könnten. Wenn man in den Elementen dann noch den Index im Heap-Intervall speichert und pflegt, wäre man mit der asymptotischen Laufzeit schon besser. Aber die Frage ist dann echt, ob sich der Aufwand lohnt. Kommt ja drauf an, mit wievielen Elementen du zu tun hast, O-Kalkül ist nicht alles.


Log in to reply