Помогите выбрать правильную структуру данных

Question

Мне нужна структура данных со следующими требованиями:

1. Необходимо иметь возможность получить элементы по индексу (например, список).
2. Я всегда буду просто добавлять / удалять элементы в конце структуры.

Я склонен использовать ArrayList. В этой ситуации кажется, что O(1) может считывать элементы (они всегда есть?), Удалять элементы (мне нужно только удалить их в конце списка) и добавлять (я только добавляю в конец список).

Существует только проблема в том, что время от времени ArrayList будет иметь снижение производительности, когда он полностью заполнен, и мне нужно добавить к нему больше элементов.

Есть ли другая идея получше? Я не думаю о структуре данных, которая бы побила ArrayList здесь.

Спасибо

Answer 1

Звучит хорошо, хотя в C # вы должны использовать List<T>. Это Java-эквивалент ArrayList<E>. Класс ArrayList в C # не является универсальным и в основном устарел новым классом List<T>.

Существует только проблема в том, что время от времени ArrayList будет иметь снижение производительности, когда он полностью заполнен, и мне нужно добавить в него больше элементов.

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

Answer 2

Используйте ArrayList.

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

Answer 3

Вам необходимо сбалансировать относительную частоту вашего доступа на чтение к вашему доступу на запись к List<T>. Следует отметить, что для большинства случаев маловероятно, что вы заметите стоимость изменения размера ArrayList<T>

Однако, если вы добавляете и удаляете элементы по одному в конце, как вы говорите, больше, чем вы будете получать элементы по индексу (в основном, используя Список как Стек или Очередь ) и ваш профилировщик скажет вам, что ArrayList<T> - это то место, где находится ваше узкое место в производительности, вам следует рассмотреть возможность использования LinkedList<T>, предназначенного именно для такого рода использования.

Answer 4

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

Это O (1), если вы выделяете достаточно элементов для размещения всей коллекции во время строительства.

см .: http://java.sun.com/j2se/1.4.2/docs/api/java/util/ArrayList.html

Answer 5

всегда используйте List<T> вместо ArrayList