Jaka jest najlepsza realizacja Lista dla dużych list w Javie

Question

trzeba utworzyć dużą listę n elementów (może być do 100000). każdy element na liście jest liczbą całkowitą równoważną indeksowi listy. Po tym muszę wywołać Collections.shuffle na tej liście. Moje pytanie dotyczy tego, która implementacja list (kolekcje java lub zbiory apache) powinna być używana. Moim zdaniem jest ArrayList. Wszystkie myśli są doceniane. Dzięki!

Dzięki za dane wejściowe. Myślę, że trzymam się ArrayList. Obecnie używam konstruktora ArrayList z parametrem initialCapacity i przekazuję rozmiar listy. Więc jeśli oryginalna lista to 100000, tworzę tę nową listę z nową tablicą ArrayList (100000); Dlatego myślę, że nie mam stworzyć tablicy i zrobić asList, ponieważ nie będzie żadnej zmiany rozmiaru. Poza tym większość zbiorów apache takich jak GrowthList & LazyList nie implementuje RandomAccess. To na pewno spowolniłoby przetasowanie (jak na javadocs). FastArrayList implementuje RandomAccess, ale apache ma dla tej klasy notatkę: "Ta klasa nie jest wieloplatformowa, a używanie jej może spowodować nieoczekiwane awarie na niektórych architekturach".

Answer 1

ArrayList najprawdopodobniej ma najmniejszy narzut za element listy, więc powinno być najlepszym wyborem. Może to być gorszy wybór, jeśli często trzeba usuwać elementy na środku listy.

Answer 2

ArrayList<T> prawdopodobnie byłby w porządku, tak - ale jakie kryteria używasz dla „najlepszy” tak? I jak dobrze musi być i tak? Jakie są twoje kompromisy między złożonością a "dobrocią", niezależnie od tych kryteriów?

Answer 3

Cyt z javadoc Collections.shuffle:

Ten sposób jest uruchamiany w czasie liniowo. Jeśli określona lista nie implementuje interfejsu RandomAccess i jest duża, ta implementacja zrzuca określoną listę do tablicy przed jej przetasowaniem i zrzuca przetasowaną tablicę z powrotem na listę. Pozwala to uniknąć kwadratowego zachowania, które wynikałoby z tasowania listy "dostępu sekwencyjnego".

Więc jeśli nie masz innych potrzeb, skorzystałbym z ArrayList, która implementuje RandomAccess.

Answer 4

ArrayList będzie najlepszym List w tej sprawie. Jako, że podkładka macierzy jest bardzo wydajna do zamiany elementów używanych w tasowaniu.

Ale jeśli naprawdę chcesz sprawdzić wydajność, możesz rozważyć użycie int [] lub niestandardowej listy opartej na int [], tak jak w przypadku wszystkich standardowych implementacji List i List, w których będziesz boksować i rozpakowywać int do Integer.

To nie będzie problemem na Suffle jak to będzie po prostu zmianę kolejności wskazówek ale będzie utworzenie 100.000 obiektów, jeśli nie może wymagać. Zakładając, że znasz rozmiar swojej listy przed utworzeniem, możesz całkiem łatwo utworzyć nową klasę List, która otoczy prymitywną tablicę. Jeśli użyjesz go jako java.util.List, nadal będziesz musiał zapisać zwrot z dowolnej metody pobierania.

Answer 5

Tworzenie tablicy Integer, a następnie jej owijanie za pomocą Arrays.asList zapewnia jeszcze mniej kosztów ogólnych niż zwykły 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; 
} 

zapisać jedną całą int wartości przestrzeni (... który wprawdzie ma absolutnie nic w tym kontekście), ale wykonuje mniej kontrole zasięg niż „prawdziwy” ArrayList, więc dostęp będzie nieco szybciej.Prawdopodobnie nic nie zauważysz, ale :)

Answer 6

Javolution twierdzi, że ma najszybszą implementację List w java. Ale nie mogłem znaleźć żadnej implementacji shuffle w tej bibliotece, więc będziesz musiał to zrobić ręcznie.

Answer 7

Biblioteka Google ma bardzo dobrą prymitywną obsługę, w tym metodę zwracającą listę, którą można przetasować.

Projekt Guava znajduje się wciąż na wstępnym etapie wdrożenia, chociaż kod został dokładnie sprawdzony i intensywnie wykorzystywany w Google. Musisz pobrać kod z wersji SVN i utworzyć klasy com.google.common.priitive.

Answer 8

Można również użyć implementacji listy opartej na mapowaniu pamięci. W takiej implementacji lista nie jest w pełni obecna w pamięci, ale tylko część ogromnej listy będzie aktywna w pamięci. Jeśli zbliżasz się do miejsca sterty (głównie w jvm 32-bitowym), być może będziesz musiał sprawić, aby lista bezproblemowo wypychała dane, używając pliku odwzorowanego w pamięci, który będzie szybszy niż normalne operacje we/wy pliku. Jedna z takich implementacji jest opisana w tej publikacji google code i objaśniona w tej publikacji: link.

Answer 9

Istnieje nowo wymyślona implementacja listy o nazwie GlueList, która jest bardzo szybka niż ArrayList i LinkedList.