Использование циклически связанного списка в качестве «свободного списка» v / s сбалансированного бинарного дерева поиска при динамическом распределении памяти - PullRequest
Новая
       14

Использование циклически связанного списка в качестве «свободного списка» v / s сбалансированного бинарного дерева поиска при динамическом распределении памяти

4 голосов
/ 08 марта 2012

Недостатком связанного списка является то, что для malloc () блок памяти должен выполнять поиск в списке ссылок, а затем, если этот адрес найден, вернуть его. Так почему бы не использовать двоичное дерево для сокращения времени поиска?

Один из вопросов, заданных NVIDIA http://www.careercup.com/question?id=9765724

Нашел соответствующую статью, которая обсуждает это здесь

1 Ответ

1 голос
/ 08 марта 2012

Если я правильно вас понимаю, проверьте эту ссылку:

Временная сложность выделения памяти

Выделение кучи может быть сделано путем представления свободной памяти в виде связанного списка, но любой достаточно сложный менеджер памяти будет использовать что-то более быстрое, например, дерево AVL, упомянутое в ответе на вопрос, который я опубликовал. Существует даже решение O (1) под названием TLSF (двухуровневое разделенное соответствие), также упомянутое в ответе.

...