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

StackOverflow https://stackoverflow.com/questions/135314

  •  02-07-2019
  •  | 
  •  

Вопрос

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

Это было полезно?

Решение

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

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

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

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

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

Другие советы

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

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

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

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

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

Обратите внимание, что итерация по экземпляру 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-петля:

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

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

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

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

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

Вы почти наверняка хотите 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».

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top