Потребление памяти в LinkedList и List при работе с большими массивами

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

Итак, учитывая структуру, которая, скажем, 40 байтов (я знаю о 16 байтах и ​​структуре, но я работаю с некоторым унаследованным кодом здесь, и было бы нелегко изменить структуру на класс). заключается в том, что каждый раз при изменении размера внутреннего массива списка необходимо выделять память для нового массива (new_array_size * 40). Так что с очень большим массивом вы в конечном итоге получите исключение из памяти, так как нет непрерывного пространства, достаточно большого для создания этого нового массива. Я знаю, что для связанного списка требуется больше места для каждого элемента (узла), поскольку он должен удерживать прямые и обратные указатели на элементы в списке, но мой вопрос заключается в том, означает ли это, что для добавления дополнительного элемента вам нужен только непрерывный слот памяти (40 + the_space_needed_for_the_pointers). Другими словами, связанный список не будет страдать от необходимости выделять огромный новый раздел непрерывной памяти для расширения.

4 голоса | спросил Andrew 7 Maypm10 2010, 15:28:24

2 ответа


0

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

Остерегайтесь того, что он не заменяет List, индексирование - это O (n) вместо O (1). Большая разница, если вы не всегда повторяете список последовательно. Когда вам нужно сделать такой резкий выбор, самое время начать рассматривать 64-битную операционную систему.

ответил Hans Passant 7 Maypm10 2010, 15:41:12
0

Поскольку связанный список ссылается только на прямую и обратную ссылку, вы не связаны непрерывным выделением памяти. Ответ @Hans имеет отличные баллы; однако я не согласен с тем, что 64-разрядная ОС - это единственный вариант высокопроизводительной индексации.

Вы ограничены этими двумя вариантами?

Если вы собираетесь ссылаться на большое количество структур, можете ли вы рассмотреть двоичное дерево? Недостатком использования дерева является то, что индексирование является частью связанного списка - O (log n). Недостатком является дополнительная работа, чтобы сохранить дерево сбалансированным. Балансировка обязательна - без баланса вы получите эквивалент связанного списка.

Ознакомьтесь с статьей MSDN (6 частей), начиная с части 3 с бинарными деревьями. Существует несколько разновидностей основного BST.

ответил Hans Passant 7 Maypm10 2010, 15:41:12

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132