Какая лучшая реализация списка для больших списков в java

Question

Мне нужно создать большой список из n элементов (может быть до 100 000). каждый элемент в списке является целым числом, эквивалентным индексу списка. После этого я должен вызвать Collections.shuffle в этом списке. Мой вопрос заключается в том, какая реализация списка (либо коллекции java, либо коллекции apache). Мое чувство кишки - ArrayList, которое можно использовать здесь. Все мысли оценены. Спасибо!

Спасибо за входные данные. Я думаю, что я придерживаюсь ArrayList. В настоящее время я использую конструктор ArrayList с параметром initialCapacity и передаю размер списка. Поэтому, если исходный список равен 100000, я создаю этот новый список с новым ArrayList (100000); Поэтому я думаю, что у меня нет создания массива и сделать asList, так как не будет никакого изменения размера. Кроме того, большинство списков коллекций apache, таких как GrowthList & LazyList не реализует RandomAccess. Это наверняка замедлило бы тасование (согласно javadocs). FastArrayList реализует RandomAccess, но apache имеет примечание для этого класса, говорящее: «Этот класс не является межплатформенным. Использование его может вызвать непредвиденные сбои на некоторых архитектурах».

Answer 1

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

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

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

Answer 5

Создание массива 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, поэтому доступ будет немного быстрее.Наверное, ничего не заметите, хотя :)

Answer 6

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

Answer 7

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

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

Answer 8

Вы также можете использовать реализацию списка файлов, привязанных к карте памяти. В такой реализации список не полностью присутствует в памяти, но в памяти будет активна только часть огромного списка. Если вы достигли ограничения пространства кучи (в основном, в 32-битном jvm), вам может понадобиться сделать список, который легко удаляет данные, используя файл с отображением памяти, который будет быстрее обычного ввода-вывода файлов. Одна такая реализация описана в этом google code и объясняется в этом link.

Answer 9

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