Struktura danych do dynamicznej alokacji pamięci

12

Pomyśl o modelu sondy komórkowej. Czy istnieje struktura danych, która może przydzielić ciągłe fragmenty pamięci o dowolnej długości (jak np. Malloc w C) i zwolnić je, unikając segmentacji pamięci, i wykonuje każdą operację w najgorszym przypadku deterministycznym czasie O (log n), gdzie n jest całkowity rozmiar pamięci?

Unikając segmentacji pamięci mam na myśli to, że jeśli całkowita liczba wolnych komórek wynosi F, to powinienem być w stanie przydzielić ciągły segment komórek F lub około komórek F.

ds.data-structures memory

— Manu
źródło

6

Nawet bez ograniczenia czasowego niemożliwe jest „uniknięcie segmentacji pamięci”, chyba że można przesuwać przydzielone obiekty, na przykład w kompaktowym śmietniku. Zobacz „Ograniczenia niektórych funkcji dotyczących dynamicznej alokacji pamięci” Robsona, która pokazuje, że przydzielanie bajtów w blokach wielkości między i wymaga bajtów pamięci. $m$ $n$ $N$ $\Omega(m \log (N/n))$

Dodatkowo system koleżeński osiąga tę granicę i można to zrobić w czasie logarytmicznym.

— jbapple
źródło

Dzięki za referencje. Pozwalam przesuwać przydzielone obiekty (w przeciwnym razie wymyślenie złego przykładu wydaje się dość łatwe). Czy dolna granica, o której wspominasz, nadal obowiązuje?

— Manu,

m

$m$

O (\log n)

$O(\log n)$

4

Ten dokument, http://dl.acm.org/citation.cfm?id=3070693 , dokładnie zajmuje się kwestią alokacji pamięci, w której można przenosić rzeczy, ale za opłatą.

— Martin Farach-Colton
źródło