Które wdrożenie listy ma być używane?

W moim programie często używam kolekcji do przechowywania list obiektów. Obecnie używam ArrayList do przechowywania obiektów. Moje pytanie brzmi: czy to najlepszy wybór? Czy może lepiej korzystać z LinkedList? Albo coś innego?Które wdrożenie listy ma być używane?

Kryteria do rozważenia:

Użycie pamięci
wydajności

Operations które muszę to:

Dodaj elementu do zbioru
iterację elementów

Jakieś myśli?

Aktualizacja: mój wybór to: ArrayList :) Na podstawie tej dyskusji, a także następujących:

Źródło

2010-09-30 Andriy Sholokh

Prawdopodobny duplikat. http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist – Fil

Opracowanie na temat "Produktywności" proszę –

czy najczęściej dodajesz na końcu listy lub w dowolnej dowolnej pozycji? –

zawsze domyślnie ArrayList i będzie w Twoim przypadku, jak również, z wyjątkiem gdy

muszę bezpieczeństwa wątku (w tym przypadku mogę zacząć patrzeć na implementacje wykaz w java.util.concurrent)
wiem, że będę robić dużo wkładania i manipulacji do listy lub profilowania ujawnia moje wykorzystanie ArrayList być problem (bardzo rzadko)

Jak co wybrać w tym drugim przypadku, to Wątek SO.com ma kilka przydatnych wskazówek: List implementations: does LinkedList really perform so poorly vs. ArrayList and TreeList?

Źródło

2010-09-30 13:08:57 whaley

Dziękuję za link do bardzo interesującej dyskusji! –

w jaki sposób LinkedList jest bardziej wątkowo bezpieczny? – Thilo

@Thilo - Nigdy nie powiedziałem, że to było. Powiedziałem, że domyślam się ArrayList, chyba że potrzebuję bezpieczeństwa wątku. Aby uczynić to krystalicznie czystym, zmienię moją odpowiedź, aby powiedzieć, że idę do implementacji List w java.util.concurrent. – whaley

Związany lista jest szybsze dodawanie/usuwanie elementów wewnętrznych (tj. nie głowy lub ogona)

Arraylist jest szybszy do iterowania

Źródło

2010-09-30 13:04:06

Hm. Może to jest szybsze podczas iteracji, choć nie spodziewam się, że będzie to coś więcej niż margines. Prawdziwa korzyść powinna wynikać z dostępu do elementów w kolejności losowej ... – Dirk

Jak rozumiem, oba mają O (n) iterację. – Qwerky

O (n) iteracja na N elementach. Iterator listy powiązanej nie będzie się wyświetlał, jeśli przeczytasz tutaj i zmienisz sposób ... – GregC

To klasyczny kompromis między insertem a odzyskiwaniem optymalizacji. Powszechnym wyborem dla zadania, które opisujesz, jest ArrayList.

Źródło

2010-09-30 13:04:07 GregC

Dlaczego jest to powszechny wybór? –

Szybko iterować po całej kolekcji, a ilość miejsca w pamięci jest mniejsza, ponieważ łącza w połączonej liście muszą być gdzieś przechowywane. – GregC

ArrayList jest w porządku dla twoich (i większości innych) celów. Ma bardzo małe obciążenie pamięci i ma dobrą amortyzację dla większości operacji. Przypadki, w których to nie jest idealne są stosunkowo rzadkie:

Lista ist bardzo duży
często trzeba wykonać jedną z tych czynności:
- dodawania/usuwania elementów podczas iteracji
- Usuń pozycje od początku listy

Źródło

2010-09-30 13:06:39

Aby rozwinąć ten punkt: Iterator ArrayList wyrzuci wyjątek, jeśli wykryje zmianę podczas iteracji. Ponadto, usuń od początku kolejkę a-la lepiej jest wykonać za pośrednictwem listy połączonej z oczywistych powodów. – GregC

@GregC: Iterator LinkedList nie generuje wyjątków w przypadku jednoczesnych modyfikacji? Jeśli tak, dlaczego tak jest dobrze? – Thilo

Wygląda na to, że jestem w błędzie ... Będę musiał spróbować ... cytując: "Iteratory zwracane przez iterator tej klasy i metody listIterator są odporne na awarie: jeśli lista jest modyfikowana strukturalnie w dowolnym momencie po iteratorze utworzony, w jakikolwiek sposób, z wyjątkiem iteratora poprzez własne metody usuwania lub dodawania, iterator wygeneruje wyjątek ConcurrentModificationException, dlatego w obliczu równoczesnej modyfikacji, iterator ulega awarii szybko i czysto, zamiast ryzykować arbitralne, niedeterministyczne zachowanie w nieokreślonym czasie. czas w przyszłości. " – GregC

Jeśli dodajesz tylko na końcu listy, ArrayList powinno być w porządku. Z dokumentacji ArrayList:

The szczegóły polityki rozwoju nie są określone poza faktem, że dodanie elementu ma stale zamortyzowanego czasu kosztował

i ArrayList powinny także zużywają mniej pamięci niż połączonej listy ponieważ nie potrzebujesz miejsca na linki.

Źródło

2010-09-30 13:07:54

To zależy od profilu użytkowania.

Czy dodajesz na końcu listy? Oba są w tym dobre. Czy dodajesz na początku listy? LinkedList jest lepsza do tego. Czy potrzebujesz dostępu losowego (czy kiedykolwiek nazwiesz go na get(n))? ArrayList jest na to lepszy.

Obie są dobre w iteracji, obie implementacje Iteratora to O (1) dla next().

Jeśli masz wątpliwości, przetestuj własną aplikację przy każdej implementacji i dokonaj własnego wyboru.

Źródło

2010-09-30 13:18:00 Qwerky

Wiem, że późno, ale, być może, this page może pomóc, nie tylko teraz, ale w przyszłości ...

Źródło

2010-09-30 13:21:00 SoulWanderer

myślę, że to byłby dobry początek: http://www.odi.ch/prog/design/newbies.php#26 To pokazuje różnice w wydajności różnych implementacji List.

Źródło

2010-09-30 14:17:19

Biorąc pod uwagę swoje kryteria, powinieneś używać LinkedList.

LinkedList implementuje interfejs Deque, co oznacza, że może on dodawać do początku lub końca listy w stałym czasie (1). Ponadto zarówno ArrayList, jak i LinkedList będą iterować w (N) czasie.

NIE należy używać tablicy ArrayList tylko dlatego, że koszt dodania elementu, gdy lista jest pełna. W tym przypadku dodanie elementu będzie (N) z powodu tworzenia nowej tablicy i kopiowania wszystkich elementów z jednej tablicy do drugiej.

Ponadto ArrayList zajmie więcej pamięci, ponieważ rozmiar macierzy dyskowej może nie zostać całkowicie wypełniony.

Źródło

2010-09-30 15:55:41 javaman

Mój kolega właśnie napisał prosty test - dodawanie elementów do list o różnej wielkości w różnych miejscach. I oto wynik: Zrobiłem mój własny bezpretensjonalny test. Oto wynik: - Proste dodawanie (List.add ("A")): ArrayList szybciej niż LinkedList 3-5 czas w zakresie wielkości od 1 do 100 000. –

Dodawanie do nagłówka listy (List.add (0, "A"): W rozmiarze 1 czas jest równy; Przy rozmiarze 100 lista_połączeń szybsza ~ 2 razy; Przy rozmiarze 1000 lista_połączeń szybsza ~ 10 razy; Przy rozmiarze 10000 LiskedList szybsza ~ 50 razy; Przy rozmiarze 50000 lista_połączeń szybsza ~ 80 razy –

Losowe dodawanie (List.add (Math.random (list.size()), "A")): ArrayList szybciej niż LinkedList 2 razy w tym samym zakresie (1 do 100 000) –

Które wdrożenie listy ma być używane?

Odpowiedz

Powiązane problemy