Какой список <Object> реализация будет самым быстрым для одного прохода писать, читать, а затем уничтожать?

Ответ 1

В основном зависит от того, знаете ли вы максимальный размер каждого списка спереди.

Если вы это сделаете, используйте ArrayList; это, безусловно, будет быстрее.

В противном случае вам, вероятно, придется профилировать. Хотя доступ к ArrayList равен O (1), создание его не так просто, из-за динамического изменения размера.

Еще один момент, который следует учитывать, заключается в том, что компромисс между пространством и временем не ясен. Каждый объект Java имеет довольно много накладных расходов. В то время как ArrayList может потерять некоторое пространство на излишках слотов, каждый слот составляет всего 4 байта (или 8 на 64-битной JVM). Каждый элемент из LinkedList, вероятно, составляет около 50 байтов (возможно, 100 в 64-разрядной JVM). Таким образом, у вас должно быть немало потраченных впустую слотов в ArrayList, прежде чем LinkedList фактически выиграет свое предполагаемое преимущество в пространстве. Местность ссылки также является фактором, и ArrayList также предпочтительнее.

На практике я почти всегда использую ArrayList.

Ответ 2

Первые мысли:

• Восстановите свой код, чтобы он не нуждался в списке.
• Упростите данные до скалярного типа данных, а затем используйте: int []
• Или просто используйте массив любого объекта, который у вас есть: Объект [] - Джон Гарднер
• Инициализировать список до полного размера: новый ArrayList (123);

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

Ответ 3

Итерация через связанный список - это O (1) для каждого элемента.

Время выполнения Big O для каждой опции одинаково. Вероятно, ArrayList будет быстрее из-за лучшей локальности памяти, но вам придется измерить его, чтобы точно знать. Выберите все, что делает код максимально понятным.

Ответ 4

Обратите внимание, что итерация через экземпляр LinkedList может быть O (n ^ 2), если сделать наивно. В частности:

List<Object> list = new LinkedList<Object>();
for (int i = 0; i < list.size(); i++) {
    list.get(i);
}

Это абсолютно ужасно с точки зрения эффективности из-за того, что список должен проходить до i дважды для каждой итерации. Если вы используете LinkedList, обязательно используйте либо Iterator, либо Java 5, улучшенный for -loop:

for (Object o : list) {
    // ...
}

Вышеприведенный код - O (n), так как список проходит на месте.

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

Ответ 5

Я предлагаю сравнить его. Это одна вещь, читающая API, но пока вы не попробуете ее для себя, она будет академической.

Должно быть справедливо легко протестировать, просто убедитесь, что вы выполняете значимые операции, или hotspot выйдет извне - усовершенствуйте и оптимизируйте все это до NO-OP:)

Ответ 6

Вы почти наверняка хотите ArrayList. Как добавление, так и чтение - это "амортизированное постоянное время" (то есть O (1)), как указано в документации (обратите внимание, что это верно, даже если список должен увеличить его размер - он создан так, как показано на рисунке http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html). Если вы знаете примерно количество объектов, которые вы будете хранить, то даже увеличение размера ArrayList будет устранено.

Добавление в конец связанного списка - O (1), но постоянный множитель больше, чем ArrayList (поскольку вы обычно создаете объект node каждый раз). Чтение практически идентично ArrayList, если вы используете итератор.

Это правильное правило всегда использовать простейшую структуру, которую вы можете, если нет веской причины не делать этого. Здесь нет такой причины.

Точная цитата из документации для ArrayList: "Операция add работает в режиме амортизированного постоянного времени, то есть для добавления n элементов требуется время O (n). Все остальные операции выполняются в линейном времени (грубо говоря). Постоянный коэффициент является низким по сравнению с тем, что для реализации LinkedList."

Ответ 7

Существует новая реализация List, называемая GlueList, которая быстрее, чем все классические реализации List.

Ответ 8

Я действительно начал думать, что следует избегать любого использования структур данных с недетерминированным поведением, таких как ArrayList или HashMap, поэтому я бы сказал, что используйте ArrayList, если вы можете связать его размер; в любом неограниченном списке используется LinkedList. Это связано с тем, что я в основном кодирую системы с почти реальными требованиями времени.

Основная проблема заключается в том, что любое распределение памяти (которое может происходить случайно при любой операции добавления) также может вызвать сбор мусора, и любая сборка мусора может привести к пропуску цели. Чем больше распределение, тем вероятнее это произойдет, и это также усугубляется, если вы используете сборщик CMS. CMS не уплотняется, поэтому найти место для нового связанного списка node, как правило, будет проще, чем найти место для нового массива элементов размером 10000.

Чем более строгим ваш подход к кодированию, тем ближе вы можете прийти в реальном времени с помощью JVM. Но выбор только структур данных с детерминированным поведением - один из первых шагов, которые вы должны предпринять.