Деревья: связанные списки по сравнению с массивами (эффективность)
Это - вопрос о присвоении, на который я испытываю затруднения при формулировке ответа.
"Предположим, что дерево может иметь до k детей на узел. Позвольте v быть средним числом детей на узел. Поскольку, какое значение (значения) v более эффективно (с точки зрения использованного пространства) сохранить дочерние узлы в связанном списке по сравнению с устройством хранения данных в массиве? Почему?"
Я полагаю, что могу ответить "почему?" более или менее без обиняков - будет более эффективно использовать связанный список, потому что вместо того, чтобы иметь набор пустых узлов (т.е. пустых индексов в массиве, если Ваше среднее число будет ниже, чем макс.) приведение в рабочее состояние памяти Вы только пространство выделения для узла в связанном списке, когда Вы на самом деле заполняете значение.
Таким образом, если у Вас будет в среднем 6 детей, когда Ваш максимум будет 200, массив будет создавать пространство для всех 200 детей каждого узла, когда дерево создается, но связанный список будет только пространство выделения для узлов по мере необходимости. Так, со связанным списком использованное пространство будет приблизительно(?) средним числом; с массивом, расположенным с интервалами используемый, будет максимум.
... Я не вижу, когда когда-либо было бы более эффективно использовать массив. Действительно ли это - вопрос о приеме? Я должен принять во внимание то, что массив должен иметь предел на общее количество узлов, когда это создается?
5 ответов
Для многих широко используемых языков массиву потребуется выделить хранилище k адресов памяти (данных). Для односвязного списка потребуется 2 адреса на узел (данные и следующий). Для двусвязного списка потребуется 3 адреса на узел.
Пусть n будет фактическим количеством потомков конкретного узла A :
- Массив использует k адресов памяти
- связанный список использует 2 n адресов
- Двусвязный список использует 3 n адресов
Значение k позволяет определить, 2 ] n или 3 n адреса будут усреднены в выигрыш или потерю по сравнению с простым хранением адресов в массиве.
Если вы находитесь в фоновом режиме .net/VS, я говорю, идите с IDE. Я c # разработчик, который работает с рубином и рельсами в свободное время (так что я не 'профессиональный рубиновый парень), и, как Джек Райан выше сказал, мы .net devs привыкли к определенному способу обучения вещей. Это легче узнать, когда у вас есть IDE, показывающая вам автозаполнение опций и соответствующую документацию бок о бок. этот путь вы бы быстро выучили.
Но для чего-то вроде запуска генераторов, задач грабли, тестов... и т.д. вы можете использовать консоль в начале (эй вы можете использовать консоль и IDE вместе правильно?:)). это даст вам представление о том, что происходит «под капотом.» позже вы могли бы использовать «бегунки» вашей среды IDE или что-нибудь еще, чтобы запустить те же самые вещи с GUI.
-121--4606278-⇧⌘A. Он будет создавать и анализировать, что означает, что Xcode предупредит вас о возможных утечках.
-121--528969-... Я не вижу, когда было бы когда-нибудь более эффективно использовать массив. Это трюк вопрос?
Это не трюк вопрос. Подумайте о служебных данных памяти , которые имеются в связанном списке. Как реализуется связанный список (в сравнении с массивом)?
Также (хотя это выходит за рамки вопроса!), потребление пространства не является единственным решающим фактором на практике. Кэширование играет важную роль в современных процессорах и хранение отдельных дочерних узлов в массиве вместо связанного списка может значительно улучшить локализацию кэша (и, следовательно, производительность дерева).
Массивы должны предварительно выделять пространство, но мы можем использовать их для очень быстрого доступа к любой записи.
Списки выделяют память всякий раз, когда они создают новый узел, и это не идеально, потому что
выделение памяти требует времени процессора.
Совет: вы можете выделить весь массив сразу, если хотите, но обычно мы выделяем,
допустим, 4 записи, и мы изменяем их размер, удваивая размер, когда нам нужно больше места.
You're assuming the array can't be dynamically re-allocated. If it can, the array wins, because it need be no bigger than k items (plus a constant overhead), and because it doesn't need per-item storage for pointers.
Я могу представить, что было бы очень хорошей идеей и очень эффективным во многих сценариях использовать LinkedList , если используемый элемент данных в любом случае имеет внутреннюю логику для предыдущего и следующего элемента, например TimeTableItem или что-то еще, что так или иначе связано со временем. Они должны реализовывать интерфейс, поэтому реализация LinkedList может использовать это и не должна заключать элементы в собственные объекты узлов. Здесь вставка и удаление были бы намного эффективнее, чем использование реализации List , которая внутренне манипулирует массивами.