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

Question

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

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

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

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

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

Answer 1

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

Пусть n будет фактическим числом дочерних элементов определенного узла A :

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

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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