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

Question

Какова самая быстрая реализация списка (в java) в сценарии, где список будет создаваться по одному элементу за раз, а в более поздний момент считываться по одному элементу за раз? Чтения будут выполняться с помощью итератора, а затем список будет уничтожен.
Я знаю, что обозначение Big O для get - O (1), а add - O (1) для ArrayList, а LinkedList - O (n) для get и O (1) для add. Работает ли итератор с той же нотацией Big O?

Answer 1

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

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

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

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

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

Answer 2

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

• Рефакторинг вашего кода, чтобы не нуждаться в списке.
• Упростите данные до скалярного типа данных, затем используйте: int []
• Или даже просто используйте массив любого имеющегося у вас объекта: Object [] - John Gardner
• Инициализировать список в полном размере: new ArrayList (123);

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

Answer 3

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

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

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

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

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

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

Answer 4

Итерация по связанному списку - O (1) на элемент.

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

Answer 5

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

Answer 6

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

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

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

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

Answer 7

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

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

Answer 8

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

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

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