bearbeiten:
So klar, dass ich das nicht gut erklärt habe, also lass es mich noch einmal mit Beispielen versuchen. Ich habe eine 'Pipe' einer bestimmten Größe, durch die Signale bei bestimmten Offsets geleitet werden. Die Pipe kann mit Signalen in verschiedenen Offsets fragmentiert werden, so dass es unmöglich ist, ein neues Signal anzupassen. Ich möchte einen Algorithmus, der mir sagt, wie die Signale angeordnet werden, um die Pipe zu defragmentieren. aber mit einer minimalen Anzahl von Signalen, die tatsächlich bewegt werden! Also für das Beispiel ..
Angenommen, ich habe eine Pipe der Größe 16. Sie hat die folgenden Signale mit den beschriebenen Größen und Offsets.
offset 0: A (size of 4; fills slots 0-3)
offset 5: C (size of 2, fills slot 5-6)
offset 8: B (size of 4, fills 8-11)
offset 14: D (size 2, fills 14-15)
Pipe: AAAA_CC_BBBB__DD
In diesem Fall habe ich 1 Steckplatz an den Offsets 4 und 7 und zwei am Offset 12-13 offen. Angenommen, ich möchte dieser Pipe ein Signal der Größe 4 hinzufügen. Es gibt jetzt keinen durchgehenden Platz dafür, aber ich weiß, dass ich genug Platz dafür habe, wenn ich defragmentiere. Die "offensichtliche" Lösung besteht darin, alle Signale oben wie folgt zu gruppieren:
offset 0: A (size 4, fills 0-3)
offset 4: B (size 4, fills 4-7)
offset 8: C (size 2, fills 8-9)
offset 10: D (size 2, fills 10-11)
Pipe: AAAABBBBCCDD____
Dadurch bleiben die Steckplätze 12-15 für mein neues Signal frei. Dazu habe ich jedoch 3 Signale (BD) neu positioniert. Für jedes Signal, das ich verschoben habe, muss ich Befehle an die Hardware senden und auf eine nicht triviale Zeit warten.
Wenn ich schlauer wäre, könnte ich erkennen, dass es einen anderen Ansatz gibt. Ich könnte so neu positionieren:
offset 0: A(size 4, fills 0-3)
offset 8: B(size 4, fills 8-11)
offset 12: C(size 2, fills 12-13)
offset 14: D(size 2, fills 14-15).
Pipe: AAAA____BBBBCCDD
Ich kann jetzt mein neues Signal in die Offsets 4-7 einpassen. UND ich musste nur ein Signal neu positionieren (B). So sparen Sie Hardware-Aufrufe.
Ich frage mich, ob es einen guten Algorithmus gibt, um solche Situationen zu erkennen. wo ich ein Signal mit der minimalen Anzahl von bewegten Signalen auf ein Rohr "passen" kann. Der Aproch, der mir in den Sinn kommt, ist ein N! Algorithmus; was im Grunde bedeutet, "jede mögliche Verteilung zu generieren, zu berechnen, zu wie vielen Zügen sie geführt hat". Ich suche einen schnelleren Ansatz.
Der Ansatz muss nicht 100% perfekt sein, ich versuche in erster Linie, den Durchschnittsfall zu minimieren, solange der schlimmste Fall nicht zu schrecklich wird. Ich weiß, dass ich nie mehr als 255 Signale auf einer bestimmten Pipe haben werde; so kann ich vielleicht mit N 'wegkommen'! so schlimm das klingt. Ich weiß auch, dass die Größe jedes Signals eine Potenz von 2 ist, ebenso wie die Rohrgröße.
Gibt es auch brillante Algorithmen zum Platzieren von Signalen, die die Fragmentierung minimieren?
Frage beantwortet; siehe unten.
Ich wollte die Antwort etwas näher erläutern, um besser zu erklären, wie eine Defragmentierung bei jedem Leser auftreten würde. Kumpel erklärt es Ich wollte auf einen einfacheren Ansatz hinweisen, um den Defraging-Teil detaillierter zu konzipieren und zu erklären, da dies die ursprüngliche Frage war.
Ich erkläre meinen Ansatz, der ein etwas anderer / einfacherer Ansatz ist, aber das "Kumpel" -Konzept effektiv beibehält. Ich berechne keine Blöcke vor oder beschrifte sie nicht. Dies ist zu aufwendig, um sie zu implementieren und zu warten. Für mich sind die CPU-Kosten für die Berechnung des Signalwegs im Vergleich zum tatsächlichen Platzieren / Löschen von Signalen ziemlich gering. Ich kann es mir also leisten, eine winzige, lineare Menge an CPU zu verlieren, indem ich nicht vorberechnete, um meine Logik zu vereinfachen. Der Prozess ist also:
zum Einfügen:
Alle Signale werden in Signalgrenzen gehalten, die der Signalgröße entsprechen, sodass ein Signal mit einem Versatz beginnt, bei dem die niedrigste% Signalgröße = 0 ist. Für den tatsächlichen Versatz gehen wir durch und finden Intervalle heraus, die diese Grenze einhalten. Wenn mein Signal auf einem Rohr der Größe 16 die Größe 4 hat, schaue ich mir die Intervalle 0-4, 5-7, 8-11, 12-15 an.
Überprüfen Sie für jedes Intervall, ob der gesamte Speicherplatz in diesem Intervall frei ist. Im einfachen Fall haben wir ein Intervall ohne Signale und setzen das Signal einfach in dieses Intervall. Wichtig ist, dass wir die Intervalle in der richtigen Reihenfolge betrachten und unser Signal in das erste freie Intervall legen. Dies stellt sicher, dass wir den kleinstmöglichen 'Block' (unter Verwendung von Buddy-Begriffen) brechen, wenn wir unser Signal hinzufügen. Dies sollte dem von im3l96 beschriebenen Buddy-Ansatz entsprechen. außer ohne Vorberechnung von Blöcken.
Wenn kein Intervall völlig frei ist, müssen wir defragmentieren. Dazu finden wir das Signal mit den am wenigsten genutzten Slots. Wenn Mehrfachintervalle die gleiche Anzahl nicht verwendeter Slots haben, wählen Sie das erste Intervall. Wir finden dann das größte Signal in diesem Intervall und rufen rekursiv denselben Einfügealgorithmus für das kleinere Signal auf (außer das Intervall, das wir ausgewählt haben, um unser erstes Signal einzufügen, als irgendwie nicht verfügbar zu markieren). Dadurch wird das Signal an eine andere Stelle verschoben, an die es passt. Wir finden dann das nächstkleinere Signal in unserem ausgewählten Intervall und machen dasselbe, bis wir alle Signale verschoben haben. Der schlimmste Fall von 2 ^ n-1 bewegten Signalen; Dabei ist N die Anzahl der möglichen Signalgrößen <= unser Signal (vorausgesetzt, die Signale sind ein Vielfaches von 2, dann ist N = log2 (signalSize)).
Hier ist ein Beispiel. * steht für einen Slot, der als nicht verfügbar markiert ist, wenn wir diese Methode rekursiv aufrufen (dh das Intervall, in dem die aufrufende Methode ihr Signal platzieren wollte und daher nicht möchte, dass der rekursive Aufruf versucht, ein Signal zu platzieren).
Hier ist ein Beispiel, der einfachste Fall, den ich mir einfallen lassen könnte und der immer noch die volle Komplexität zeigt. Hinweis: Die folgende Struktur wäre schwer zu schaffen, sondern könnte aus dem Buddy - approch führen , wenn jemand sehr , sehr hart versucht.
FFFFFFFF__AA_B__EEEE_HGGCC_DII_J
Jemand gibt ein Signal Z der Größe 8 ein
wir wählen Offset 8:
defragInsert (z, Größe 8)
effective structure: FFFFFFFF__AA_B__EEEE_HGGCC_DII_J
placing signal in interval: __AA_B__
defragInput (A, Größe 2)
effective structure: FFFFFFFF********EEEE_HGGCC_DII_J
place signal in interval (offset 20) _H
defragInput (H, Größe1)
effective structure: FFFFFFFF********EEEE**GGCC_DII_J
place signal between C & D
return defragInput (H, Größe1)
effective structure: FFFFFFFF********EEEE__GGCCHDII_J
place H at offset 20 now that it's open
return defragInput (A, Größe 2)
effektive Struktur: FFFFFFFF_ _ _B__EEEEAAGGCCHDII_J B jetzt bewegen ...
defragInput (B, Größe1)
effektive Struktur: FFFFFFFF * ** * EEEEAAGGCCHDII_J Platz B zwischen I & J.
return defragInput (B, Größe1)
effektive Struktur: FFFFFFFF_ __ _EEEEAAGGCCHDIIBJ add B.
return defragInsert (z, Größe 8)
fianl structure: FFFFFFFFzzzzzzzzEEEEAAGGCCHDIIBJ
quelle
Antworten:
Das Problem ähnelt der Speicherzuweisung, daher ist meine vorgeschlagene Lösung die Verwendung von http://en.wikipedia.org/wiki/Buddy_memory_allocation . Durch die Verwendung des Buddy-Allokators wird die Fragmentierung zunächst minimiert, indem der kleinste zusammenhängende freie Platz in der Pipe für ein Signal ausgewählt wird.
Anhand des Beispiels wird der Platz für Rohre der Größe 8 wie folgt zugewiesen:
Das Freigeben von Speicherplatz ist eine Frage der Überprüfung des "Kumpels" des freigegebenen Speicherplatzes. Wenn der Kumpel auch frei ist, können sie zusammengeführt werden, um einen größeren zusammenhängenden Raum zu bilden. Wenn also der Speicherplatz in der Reihenfolge der eingehenden Signale freigegeben wird, sieht dies folgendermaßen aus:
Es ist auch recht einfach und schnell, da es nur eine geringe Fragmentierung gibt, insbesondere weil die Größe der Signale eine Potenz von 2 ist.
Wenn es wirklich benötigt wird, kann auch die Defragmentierung / Verdichtung problemlos durchgeführt werden. Es geht lediglich darum, zugewiesene Blöcke gleicher Größe mit freien Freunden zu finden und zusammenzuführen (durch Verschieben eines zugewiesenen Blocks wird ein größerer freier Block erstellt).
quelle
Bevor Sie nach einer Antwort suchen, sollten Sie zunächst klar definieren, was Sie minimieren möchten, dh welche Art der Signalrepositionierung zulässig ist.
ein (und nur ein) Signal aus dem Rohr nehmen und an einer anderen Stelle ohne Überlappungen hinzufügen (und diesen Schritt n-mal wiederholen)?
oder um n Signale gleichzeitig von Ihrer Pipe zu nehmen und sie anschließend ohne Überlappungen wieder einzufügen (gezählt als n Züge)?
Offensichtlich ist diese erste Alternative viel eingeschränkter und bietet Ihnen einen viel kleineren Suchraum. Zum Beispiel , um von
AAAA_CC_BBBB__DDzuAAAA_CC___DDBBBBwerden braucht man mindestens 4 bewegt , wenn keine gleichzeitigen Neupositionierungen erlaubt sind, und 2 bewegt , wenn sie erlaubt sind.Ich gehe davon aus, dass Sie das erste Problem im Sinn haben (bitte bestätigen Sie dies). Hier ist mein Vorschlag dafür:
Machen Sie dies zu einem Problem bei der Diagrammsuche. Für eine Give-Pipe definiert jede Signalkonfiguration einen Scheitelpunkt Ihres Diagramms, und die Kanten zwischen diesen Scheitelpunkten sind die möglichen Neupositionierungen.
Geben Sie jedem Scheitelpunkt einen Wert: die Länge der längsten fortlaufenden Schlitzsequenz
Jetzt sollte es einfach sein, eine Standard-Grafiksuchtechnik wie die Breitensuche oder die A * -Suche zu verwenden, um die kleinste Anzahl von Schritten zu finden, bis Sie eine Rohrkonfiguration erreichen, die genügend Platz für das neue Signal bietet, das Sie hinzufügen möchten.
quelle
Sie müssen eine repräsentative Stichprobe Ihrer realen Daten entnehmen und verschiedene Umpackalgorithmen simulieren. Im Moment habe ich nicht genügend Informationen, um das System zu simulieren, daher konnte ich nicht überprüfen, wie ein Algorithmus funktioniert.
quelle