2010-05-31 3 views
4

мне нужна структура данных с учетом следующих требований:Помощь выбора правильной структуры данных

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

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

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

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

Благодаря

ответ

6

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

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

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

0

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

+0

Что? Список - это интерфейс в Java. – Jack

+0

Нет, неправильно! Вы не поняли вопроса. Дело в том, что вопросник хочет знать, какая из конкретных реализаций Java из списка он должен использовать. Если бы это было о C#, я верну обратно. – DJClayworth

+0

yep, это было только для C# :) Кто использует Java в любом случае? :) –

4

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

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

0

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

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

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

+0

Пока полный массив распределение - O (N), амортизированная стоимость - только O (1) за добавление. Они делают это путем увеличения массива с экспоненциальным масштабным коэффициентом (что означает, что полные перераспределения происходят экспоненциально реже) – mikera

0

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

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

+0

Операции чтения и записи медленны LinkedList для доступа к последнему элементу. Вместе с Double Linked List это другая история. –

Смежные вопросы