Деревья: Связанные списки против массивов (Эффективность)

Question

Это задание, на которое у меня возникают проблемы с ответом.

«Предположим, что на каждом узле может быть до k детей. Пусть v - среднее число детей на узел. Для каких значений v это более эффективно (с точки зрения используемого пространства) для хранения дочерние узлы в связанном списке и хранилище в массиве? Почему? "

Я считаю, что могу ответить «почему?». более или менее на простом английском языке - будет эффективнее использовать связанный список, потому что вместо того, чтобы иметь пустую пустые узлы (т. е. пустые индексы в массиве, если ваше среднее значение меньше максимального), занимая память, вы выделяете только пространство для узла в связанном списке, когда вы фактически заполняете значение.

Итак, если у вас в среднем 6 детей, когда ваш максимум равен 200, массив будет создавать пространство для всех 200 детей каждого узла при создании дерева, но связанный список будет только выделять пространство для узлов по мере необходимости. Таким образом, со связанным списком используемое пространство будет приблизительно (?) Средним; с массивом, используемые интервалы будут максимальными.

... Я не вижу, когда было бы более эффективно использовать массив. Это вопрос с подвохом? Должен ли я учитывать тот факт, что массив должен иметь ограничение на общее количество узлов при его создании?

Answer 1

Для многих часто используемых языков для массива потребуется выделить хранилище k адреса памяти (из данных). Одноуровневый список потребует 2 адреса на узел (данные & далее). Для двусвязного списка потребуется 3 адреса на узел.

Пусть п быть фактическое число детей конкретного узла :

• Массив использует к адресов памяти
• Однократно связанный список использует 2 п адреса
• В двусвязном списке используются 3 n адреса

Значение к позволяет определить, является ли 2 н или 3 п адреса в среднем на прибыль или потери по сравнению с просто хранить адреса в массиве.

Answer 2

... Я не вижу, когда было бы более эффективно использовать массив. Это вопрос с подвохом?

Это не трюк. Вспомните память накладные расходы, что связанный список имеет. Как реализован связанный список (по сравнению с массивом)?

Также (хотя это выходит за рамки вопроса!), Потребление пространства не является единственным решающим фактором на практике. Кэширование играет важную роль в современных процессорах, а хранение отдельных дочерних узлов в массиве вместо связанного списка может значительно улучшить локальность кеша (и, следовательно, производительность дерева).

Answer 3

Я могу себе представить, что это может быть очень хорошая идея, и очень эффективно во многих случаях использовать LinkedList если элемент данных один использует имеет внутреннюю логику для предыдущего и следующего пункта в любом случае, для примера TimeTableItem или что-нибудь, что это каким-то образом относящиеся ко времени. Они должны реализовать интерфейс, поэтому реализация LinkedList может использовать это и не должна обертывать элементы в свои собственные объекты узла. Вставка и удаление были бы намного более эффективными, чем использование реализации List, которая внутренне манипулирует массивами.

Answer 4

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

Подсказка: вы можете выделить весь массив сразу, если вы хотите, но, как правило, мы выделяем,
позволяет сказать, 4 записи, и мы изменить ее размер, удваивая размер, когда нам нужно больше места.

Answer 5

Вы предполагаете, что массив не может быть динамически перераспределен. Если это возможно, массив выигрывает, потому что он должен быть не больше, чем k элементов (плюс постоянные накладные расходы), а также потому, что для указателей нет необходимости в хранилище для каждого элемента.