Что является лучшей Реализацией списка для Больших списков в Java

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

Цитируется из javadoc Collections.shuffle:

Этот метод работает в линейном времени. Если указанный список не реализует интерфейс RandomAccess и имеет большой размер, эта реализация выгружает указанный список в массив перед его перетасовкой и выгружает перетасованный массив обратно в список. Это позволяет избежать квадратичного поведения, которое могло бы быть результатом перетасовки списка «последовательного доступа».

Поэтому, если у вас нет других потребностей, я бы выбрал ArrayList, который реализует RandomAccess.

Создание массива Integer с последующим его заключением в Arrays.asList дает вам еще меньше накладных расходов, чем обычный ArrayList .

List<Integer> makeList(int size){
    if (size < 0) throw new IllegalArgumentException();
    Integer[] arr = new Integer[size];
    for (int i = 0; i < arr.length; ++i) arr[i] = i;
    List<Integer> list = Arrays.asList(arr);
    Collection.shuffle(list);
    return list;
}

Вы сохраняете одно целое пространство int (... что, по общему признанию, абсолютно ничто в данном контексте), но он выполняет меньше проверок диапазона, чем "настоящий" ArrayList , поэтому доступ будет немного быстрее. Но вы, наверное, ничего не заметите :)

ArrayList , вероятно, подойдет, да - но какие критерии вы все равно используете для «лучшего»? И насколько это вообще должно быть хорошо? Каковы ваши компромиссы между сложностью и «добротой» по любым критериям?

Javolution утверждает, что имеет самую быструю реализацию списка в java. Но я не смог найти в этой библиотеке какой-либо реализации перемешивания, поэтому вам придется сделать это вручную.

Библиотека Google Guava имеет действительно приятную примитивную обработку, включая Метод Ints.asList () , возвращающий список, который можно перемешать.

Проект Guava все еще находится на предварительной стадии развертывания, хотя код был тщательно проверен и активно используется в Google. Вам нужно будет получить код из SVN и построить классы com.google.common.primitive.

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

Но если вы действительно гонитесь за производительностью, вы можете рассмотреть возможность использования int [] или настраиваемого списка, основанного на int [], как со всеми списками и Перечислите стандартные реализации, которые вы будете упаковывать и распаковывать в целые числа.

Это не будет проблемой для суффла, поскольку это будет просто переупорядочение указателей, но вы будете создавать 100 000 объектов, когда вам это может не понадобиться. Предполагая, что вы знаете размер своего списка до создания, вы можете довольно легко создать новый класс List, который обертывает примитивный массив. Если используется как java.util.List, вам все равно нужно будет упаковать возврат из любого метода get.