Zeitkomplexität von Speicherzuweisung

Question

Was ist die Zeitkomplexität von dynamischer Speicherzuweisung mit neuen, malloc, usw.? Ich weiß sehr wenig darüber, wie Gedächtnis Zuweiser umgesetzt werden, aber ich nehme an, die Antwort ist, dass es bei der Umsetzung abhängt. Daher beantworten Sie bitte für einige der häufigsten Fälle / Implementierungen.

Edit: Ich erinnere mich vage, zu hören, dass Heapzuordnung im schlimmsten Fall unbeschränkt ist, aber ich bin wirklich daran interessiert, im Durchschnitt / typischen Fall.

Answer 1

Eines der Dinge, die Sie zu erkennen, wenn sie mit O-Notation zu tun ist, dass es oft sehr wichtig ist, zu verstehen, was n ist. Wenn die n ist etwas etwas im Zusammenhang Sie steuern können (zB: die Anzahl der Elemente in einer Liste, die Sie sortieren möchten). Dann macht es Sinn, es schwer zu sehen

In den meisten Heap-Implementierungen Ihre n ist die Anzahl von zusammenhängenden Blöcken von Speichern der Manager Handhabung ist. Das ist entschieden nicht etwas typisch unter Client-Steuerelement. Die einzige n der Kunde wirklich die Kontrolle über hat, ist die Größe des Teils des Speichers sie will. Oft trägt diese in keinem Zusammenhang mit der Höhe der Zeit der Zuordner nimmt. Ein großen n , so schnell wie ein kleines zugeordnet werden konnte n , oder es könnte viel länger dauern, oder es könnte sogar unservicable sein. All dies könnte für das gleiche ändern n je nachdem, wie vorherige Zuweisungen und Freigaben von anderen Kunden kamen. Also wirklich, wenn Sie einen Haufen implementieren, dann die richtige Antwort ist, dass es nicht ist -deterministic .

Aus diesem Grunde ist harte Echtzeit-Programmierer versuchen dynamische Zuordnung (nach dem Start) zu vermeiden.

Answer 2

Die Zeitkomplexität für einen Heap allocator auf verschiedenen Systemen unterschiedlich sein können, je nachdem, was sie vielleicht für sein zu optimieren.

Auf Desktop-Systemen verwendet die Halde allocator wahrscheinlich eine Mischung aus verschiedenen Strategien einschließlich Caching letzten Zuweisungen, Lookaside-Listen für gemeinsame Zuteilung Größen Bins Speicher Stücke mit bestimmten Größe Eigenschaften usw. eine keep Zuweisung Zeit nach unten, um zu versuchen, sondern auch halten Fragmentierung überschaubar. Beachten Sie die Hinweise für Doug Lea malloc-Implementierung für einen Überblick über die verschiedenen Techniken, die verwendet werden: http: //g.oswego.edu/dl/html/malloc.html

Für einfachere Systeme, eine Strategie des ersten Sitzes oder am besten passen könnte verwendet werden, die mit den freien auf einer verknüpften Liste gespeichert Blöcke (die einer O (N) Zeit mit wobei N die Anzahl der freien Blöcke geben würde). Aber ein anspruchsvolleres Speichersystem wie ein AVL-Baum könnte verwendet werden, um der Lage sein, freie Blöcke in O (log N) Zeit ( http://www.oocities.org/wkaras/heapmm/heapmm.html ).

Ein Echtzeit-System könnte einen Haufen allocator wie TLSF (Zwei-Level-segregieren Fit) verwenden, die einen O (1) hat Verrechnungskostenart: http://www.gii.upv.es/tlsf/

Answer 3

Ich würde denken, es in der Regel O wäre (n), wobei n die Anzahl der verfügbaren Speicherblöcke ist (da Sie die verfügbaren Speicherblöcke zu scannen haben eine passende zu finden).

Having said that, ich habe Optimierungen gesehen, dass es schneller machen kann, insbesondere mehrere Listen der verfügbaren Blöcke Aufrechterhaltung ihrer Größe Bereiche in Abhängigkeit (so Blöcke weniger als 1k in einer Liste enthalten sind, die Blöcke von 1k bis 10k sind in einer anderen Liste und so weiter).

Dies ist immer noch O (n) jedoch nur mit einem kleineren n.

würde ich interessiert sein, Ihre Quelle zu sehen, dass eine Heapzuordnung es, die unbegrenzt ist (wenn durch das, Sie meinen es könnte ewig dauern).

Answer 4

Just überprüfen, wie typische Verteilern Arbeit.

Ein Bump-the-Zeiger allocator arbeitet in O (1) , und es ist eine kleine ' 1 ' dazu.

Für einen segregierte Speicher Zuordner, die Zuweisung von k Bytes bedeutet "den ersten Block von Liste zurück ( n )", wo List ( n ) ist die Liste der Blöcke von n Bytes, wobei n> = k . Es könnte finden, dass die Liste ( n ) ist leer, so dass ein Block von der nächsten Liste (Liste ( 2n )) sein müßte geteilt mit beiden resultierenden Blöcke von n Bytes setzen auf Liste werden ( n ), und dieser Effekt macht kräuseln durch alle Erhältlichkeit Größen, so dass für eine Komplexität von O (ns) , wobei ns die Anzahl der verschiedenen Größen lieferbar bis ist und ns = log (N) , wobei N ist die Größe die größte Blockgröße vorhanden, so dass auch das wäre klein. In den meisten Fällen, vor allem nach einer bestimmten Anzahl von Blöcken zugeteilt wurde und freigegeben, Komplexität ist O (1) .

Answer 5

Nur zwei Bemerkungen:

• TLSF ist O (1) in dem Sinne, daß nicht a ist einfache Wiederholung; und verwaltet bis zu 2 GB. Obwohl es wirklich schwer zu glauben ist, nur den Code überprüfen.

• Es ist nicht wahr, dass die „best fit“ Politik (den engen Block findet) ist am geeignetsten erreichen kleine Fragmentierung. Es ist alles andere als trivial, diese Behauptung zu beweisen, in der Tat hat es nicht formal bewiesen, aber es gibt viele Beweise, die in diese Richtung gehen. (Nice Forschungsthema).