Kinder füttern :-)

Knuddlbaer

Naja,

entweder Du suchst die toten Kinder oder lässt die Kinder sich beschweren.

Wäre eventuell eine priority_queue die als Priorität ein timestamp/counter verwendet ? Dann könnte man das erste tote Kind suchen und alles ab diesem Punkt umweltgerecht entsorgen, denn alles was nach dem ersten toten Kind kommt müsste ebenfalls tot sein.

(Oder eine multimap ? Irgendwas, was nach dem Timestamp sortiert, ich glaub bei der queue müsste man die Kinder raus werfen und neu einsetzen was man sich bei der map sparen könnte.)

Wenn also mal ein wenig Luft herrscht, such nach den Laichen oder nach einer längeren Zeit zwangsweise, damit es nicht anfängt zu stinken. Du sarst Dir dann damit das suchen jeder einzelnen Laiche, weil Du diese stapelst und die Umerziehung der Kinder sparst.

THX 1138

Nö, nur einen Timer und bei jedem Step zählst Du bei allen Kindern den Zähler runter. Ist einer nahe null schreit das Kind.
Wie hast Du denn den Kindergarten angelegt? Vector?

BlackPepper

Dann bleibt aber immer noch das Problem, die Kinder mit einem Timestamp zu markieren, denn ich besuche nur die Kinder, die ein Freßpaket erhalten. Diese kann ich dann auch markieren.

Das mit der Priority Queue hab ich nicht so ganz verstanden. Wären markierte Kinder automatisch an einem Ender der Schlange? Dann bräuchte ich mir ja nur das andere Ende anzusehen und dort tote Kinder entfernen solange es welche gibt.

Grüße, Max

Knuddlbaer

ich hab mit der prio queue noch nicht gearbeitet. Ebentuell wäre die multimap (ggf. mit eigenen compare dingens) sinvoller.

Die Idee war folgende:

Das Kind wird bei der Geburt in die Queue eingetragen. Bei jedem Besuch setzt Du den Timespamp auf aktuell. Wenn Luft herrscht, schaust Du einfach nach der ersten Laiche (weil ja nach Timestamp sortiert) und entfernst alles bis zum Ende.

Du musst also dem Geburtshelfer das eintragen beibringen und ab und an mal nach einer Laiche suchen, was z.B. bei einer multimap durch den binärenbaum schnell gehen sollte (wobei Du hier untersuchen solltest ob das entfernen dann schnell genug geht.)

Ich hab leider zu wenig mit den STL Containern gemacht um dem Ansatz den passenden zu geben.

Ich denke jedoch, das schnell sortiert werden muss wärend man verhältnismässig selten die Laichen entfernt.

Bei dem Ansaz musst Du sogar nur das erste tote Kind finden und musst nicht alle untersuchen bis das erste Lebt und kannst die Kinder kinder sein lassen.

DarthZiu

Einen Timestamp brauchst du gar nicht.

Nimm mal an jedes Kind kann 100 (extra ohne Einheit) überleben, ohne was zu essen.
Dann ordnest du jedem Kind einen Wert zu, der am Anfang mit 100 initialisiert wird.
Nun zählst du in deinem Programm bei jeder Iteration (oder sekunde, oder wie immer du das realisierst) bei jedem Kind den Wert um eins runter. Dann kannst du dir sogar Intervalle einrichten (zum Beispiel bei Wert < 10 schon mal vorsorglich nen Sarg bestellen).
Wenn du die Kinder jetzt noch in einer geeigneten Datenstruktur verwaltest, die nach dem Wert jedes Kindes sortiert, hast du immer schön an einem Ende die kerngesunden, am anderen Ende jene, die wahrscheinlich nicht sehr alt werden.

Knuddlbaer

Es geht beim timestamp darum nicht jedes Kind anfassen zu müssen.

Für einen Zähler muss ich jedes Kind besuchen, bei einem timestamp nicht.

BlackPepper

1310-Logik schrieb:

Nö, nur einen Timer und bei jedem Step zählst Du bei allen Kindern den Zähler runter. Ist einer nahe null schreit das Kind.
Wie hast Du denn den Kindergarten angelegt? Vector?

Die Kinder liegen in einer map und es sind mehrere tausen. Das Problem sind die permanten eintreffenden Freßpakete, weshalb ich nicht viel Zeit für die Suche nach toten Kindern habe. Der Rest ist nicht das Problem, das läuft in der map bereits schnell genug.

Grüße Max

THX 1138

Dann machs mit der priority_queue.
Mach nen Zähler für die Pakete, die die eins kriegen erhöhst du um sagen wir 100.
Wenn Du etwas Zeit hast, schaust Du nach, wieviel Zeit vergangen ist und wieviel die Kids gegessen haben müssten in der Zeit. Alle die weniger bekommen haben, sind tot.
Das nachschauen und entfernen könntest Du mit lower_bound() und erase() machen, sollte effizient genug sein.

Knuddlbaer

Deswegen ja der Timestamp.

Du trägst jedes Kind bei der Geburt mit Timestamp ein und aktualisierst diesen wenn ein Fresspacket da ist.

Da Du weisst wie lange ein Kind ohne Frspacket lebt, musst Du nur suchen, welches Kind innerhalb der Grenze liegt. Den rest kannst Du ungesehen entsorgen da es ja sortiert ist.

net 0

BlackPepper schrieb:

Vielleicht hat mit jemand einen guten Tipp.

du könntest ja mal einen tag im kindergarten mitmachen.
aber vorher schön viel futtern, damit du nicht aus versehen verhungerst...

BlackPepper

1310-Logik schrieb:

Dann machs mit der priority_queue.
Mach nen Zähler für die Pakete, die die eins kriegen erhöhst du um sagen wir 100.
Wenn Du etwas Zeit hast, schaust Du nach, wieviel Zeit vergangen ist und wieviel die Kids gegessen haben müssten in der Zeit. Alle die weniger bekommen haben, sind tot.

Wenn ich jedem Kind einen Zähler gebe und die Priority Queue nach diesem Zähler sortieren lasse, stehen dann an einem Ende die Kinder die gerade gegessen haben und am anderen Ende die Kinder, die schon länger nicht mehr gegessen haben. Dann kann ich nämlich zu einem bestimmten Zeitpunkt ans anderen Ende sehen und muss nicht suchen, weil sich verhungerte Kinder dort befinden, ohne das ich was tuen muss. Lebt das Kind am anderen Ender der Priority Queue auch, kann ich sofort weiter Freßpakete verteilen, weil dann alle Kinder leben.

Grüße Max

THX 1138

Sagte schonmal jemand, dass das sehr makaber tönt?
Wofür züchtest du die Kinder denn? Internethandel?

tntnet

Es gibt wie immer mehrere Möglichkeite, das Problem zu lösen:
[] abwarten - irgendwann sind alle Tot und das Problem hat sich erledigt
[] sag den Eltern Bescheid, sie sollen den Kindern ein Pausenbrot mitgeben
[] stell ein paar Arbeitslose ein, die Dir helfen, wenn Du das nicht alleine schaffst
[] nimm nur so viele Kinder auf, die Du auch versorgen kannst

Dabei frage ich mich, was das in einem C++-Forum zu tun hat. C++ ist zwar eine Programmiersprache, mit der man alles machen kann, aber das "alles" bezieht sich lediglich auf Softwareprobleme.

Tntnet

phlox81

Kann ein Kind sich einfach nicht selber Löschen, wenn es stirbt?

Kind::Destroy(){Kindergarten->erase(this);delete this;}

BlackPepper

phlox81 schrieb:

Kann ein Kind sich einfach nicht selber Löschen, wenn es stirbt?
Kind::Destroy(){Kindergarten->erase(this);delete this;}

Hallo,

Das mußt du mir unbedingt genauer erklären. Ich meine den Sourcecode. Kannst Du ihn etwas näher erklären, denn ich verstehe nicht wer da wen löscht. Das wäre nämlich die Toplösung.

Grüße Max

Phoemuex

Der Code ist zwar nicht von mir, aber relativ einfach zu verstehen:

Das

Kindergarten->erase(this);

ist halt Pseudo-Code, weil wir nicht genau wissen, wie dein Kindergarten funktioniert, aber entweder müsste der Kindergarten halt global/static/Singleton/was auch immer sein oder jedes Kind müsste einen Zeiger auf den Kindergarten haben...

Mit erase(this) sagst du dem Kindergarten , er soll das Kind, dessen Methode da gerade ausgeführt wird, löschen.

Mit

delete this;

löscht sich das Kind dann am Ende selber, das geht allerdings nur und NUR dann, wenn es auch auf dem Heap erzeugt wurde und nachher nicht noch irgendwer versucht, über einen ungültig gewordenen Zeiger auf das Kind zuzugreifen.

Wenn der Kindergarten die Kinder verwaltet, könnte der aber auch direkt das delete für das Kind aufrufen...

Felix

P.S.: Falls es an dem this liegt: this ist immer ein Zeiger auf das Objekt, in dessen Methode man sich gerade befindet.

Jester

Warum eigentlich ne priority-Queue und keine list? Das würde die Laufzeitkomplexität noch deutlich senken.
Wer gefüttert wird, wird hinten wieder angehängt, dadurch bleibt die Liste sortiert. Jedesmal, wenn Du einen fütterst räumste ne konstante Anzahl Leichen weg.

BlackPepper

Phoemuex schrieb:

Das
Kindergarten->erase(this);
ist halt Pseudo-Code, weil wir nicht genau wissen, wie dein Kindergarten funktioniert, aber entweder müsste der Kindergarten halt global/static/Singleton/was auch immer sein oder jedes Kind müsste einen Zeiger auf den Kindergarten haben...
Mit erase(this) sagst du dem Kindergarten , er soll das Kind, dessen Methode da gerade ausgeführt wird, löschen.

Dann ist Kindergarten der Zeiger auf den Kindergarten, den jedes Kind mitführt. Also bittet das Kind den Kindergarten gelöscht zu werden.

Phoemuex schrieb:

Mit
delete this;
löscht sich das Kind dann am Ende selber, das geht allerdings nur und NUR dann, wenn es auch auf dem Heap erzeugt wurde und nachher nicht noch irgendwer versucht, über einen ungültig gewordenen Zeiger auf das Kind zuzugreifen.

Wenn der Kindergarten die Kinder verwaltet, könnte der aber auch direkt das delete für das Kind aufrufen...

Felix

Hmm, das setzt aber voraus, das ich den Timer der Kinder mindere und das tue ich nicht, da ich keine Kinder besuche, die kein Freßpaket bekommen. Ich weiß nur, wer gerade eins bekommen hat.

Grüße Max

BlackPepper

Jester schrieb:

Warum eigentlich ne priority-Queue und keine list? Das würde die Laufzeitkomplexität noch deutlich senken.
Wer gefüttert wird, wird hinten wieder angehängt, dadurch bleibt die Liste sortiert. Jedesmal, wenn Du einen fütterst räumste ne konstante Anzahl Leichen weg.

Weil ich erst mal in der Liste denjenigen finden muss, der gefüttert wurde um ihn dann nach hinten zu setzten und das dauert zu lange. Derweil hab ich Freßpakete verloren. Die Liste ist schnell beim einfügen und schnell beim löschen, weil sie aber unsortiert ist, ist sie langsam beim Zugriff auf ein beliebiges Element. In einer map, die bereits zufriedenstellen benutze, habe ich bessere Zugriffszeiten. Die Adressen der Kinder kann ich ja zusätzlich in einer priority queue verwalten und somit habe ich schnellen zugriff auf verhungerte Kinder, die sich an einem Ender der Schlange befinden.

Grüße Max