Datenstruktur für die dynamische Speicherzuordnung

12

Denken Sie an das Zell-Sonden-Modell. Gibt es eine Datenstruktur, die zusammenhängende Speicherblöcke beliebiger Länge (wie z. B. malloc in C) zuordnen und freigeben kann, wobei eine Speichersegmentierung vermieden wird, und die jede Operation in der ungünstigsten deterministischen O-Zeit (log n) ausführt, in der n ist die Gesamtgröße des Speichers?

Unter Vermeidung der Speichersegmentierung meine ich, dass ich in der Lage sein sollte, ein zusammenhängendes Segment von F-Zellen oder etwa F-Zellen zuzuweisen, wenn die Gesamtzahl der freien Zellen F ist.

Manu
quelle

Antworten:

6

Auch ohne die Zeitbeschränkung ist es unmöglich, eine "Speichersegmentierung" zu vermeiden, wenn Sie die zugewiesenen Objekte nicht wie in einem komprimierenden Garbage Collector verschieben können. Siehe Robsons "Grenzen für einige Funktionen in Bezug auf die dynamische Speicherzuweisung", aus dem hervorgeht, dass die Zuweisung von Bytes in Blöcken mit einer Größe zwischen n und N Ω erfordert ( m log ( N / n )mnNΩ(mLog(N/n))

Zusätzlich erreicht das Buddy-System diese Grenze und kann in logarithmischer Zeit durchgeführt werden.

Apfel
quelle
Danke für den Hinweis. Ich erlaube es, die zugewiesenen Objekte zu verschieben (ansonsten sieht es ziemlich einfach aus, ein schlechtes Beispiel zu finden). Gilt die von Ihnen erwähnte Untergrenze noch?
Manu
m
Ö(Logn)
4

Dieses Papier, http://dl.acm.org/citation.cfm?id=3070693 , befasst sich genau mit der Frage der Speicherzuweisung, wo Sie Dinge verschieben können, aber zu einem Preis.

Martin Farach-Colton
quelle