Структура данных для динамического распределения памяти

12

Подумайте о модели клеточного зонда. Существует ли структура данных, которая может выделять непрерывные порции памяти любой длины (например, malloc в C) и освобождать их, избегая при этом сегментации памяти, и выполняет каждую операцию в наихудший случай детерминированного времени O (log n), где n равно общий размер памяти?

Избегая сегментации памяти, я имею в виду, что если общее количество свободных ячеек равно F, то я должен быть в состоянии выделить непрерывный сегмент F-ячеек или около F-ячеек.

ds.data-structures memory Manu
источник

6

Даже без ограничения по времени невозможно «избежать сегментации памяти», если вы не можете перемещать выделенные объекты, как в компактном сборщике мусора. См. «Границы некоторых функций, касающихся динамического выделения памяти» Робсона, в которых показано, что для распределения байтов в блоках размером от до требуется байтов памяти. $m$ $n$ $N$ $\Omega(m \log (N/n))$

Кроме того, система друзей достигает этой границы и может быть выполнена в логарифмическом времени.

jbapple
источник

Спасибо за ссылку. Я позволяю перемещать выделенные объекты вокруг (в противном случае это выглядит довольно легко, если придумать плохой пример). Применяется ли нижняя граница, которую вы упоминаете, по-прежнему?

Ману

m

$m$

O (\log n)

$O(\log n)$

4

В этом документе http://dl.acm.org/citation.cfm?id=3070693 точно рассматривается вопрос распределения памяти, куда вы можете перемещать вещи, но за дополнительную плату.

Мартин Фарах-Колтон
источник

Структура данных для динамического распределения памяти

Ответы: