ArrayList vs LinkedList - ankieta

W praktyce takie listy mają po kilka elementów i nie widziałem nigdy sytuacji żeby miało to jakiekolwiek znaczenie. Już prędzej bym rozkminiał HashMap vs TreeMap bo częściej można się spotkać z dużą mapą w pamięci jako jakiś cache

No prosta sprawa, tam gdzie byś użył array'a jako kolekcji używasz ArrayList, a tam gdzie by Ci się chciał pisać listę jednokierunkową to LinkedList.

Twoja ankieta właściwie jest tożsama z ankietą: "Używasz array'ów czy list jednokierunkowych dwukierunkowych?".

Przecież LinkedList jest dwukierunkowa.
dokumentacja

@TomRiddle: Ja wiem czym się różnią te implementacje, jakie są teoretyczne przypadki użycia A, lub B. Moja niewyartykułowana teza, to że dość rzadko zdarza się sytuacja kiedy liczba elementów w takich listach i scenariusz operacji ma jakiekolwiek znaczenie.

@jarekr000000: Inne implementacje List, własne/zewnętrzne .collections, czy nie używasz kolekcji?

piotrpo napisał(a):

@TomRiddle: Ja wiem czym się różnią te implementacje, jakie są teoretyczne przypadki użycia A, lub B. Moja niewyartykułowana teza, to że dość rzadko zdarza się sytuacja kiedy liczba elementów w takich listach i scenariusz operacji ma jakiekolwiek znaczenie.

No tak, dosyć rzadko.

Ale to jest pytanie bardziej o zasadnoć array vs lista dwukiernunkowa.

Sorry - skasowałem post, bo stwierdziłem, że w sumie mogę olać ankietę. Ale się wypowiem.

Nie używam w normalnym kodzie żadnej z nich (99% przypadków).
Jeśli już w javie/kotlinie to vavro.io.collection.List albo vavr.io.collection.Vector

Javowe kolekcje są tragiczne, bo mutowalne i mają powalone api (metoda add zwracająca void i rzucająca exceptionem to moje ulubione).

W praktyce spotkałem sie z kodem gdzie jakby ktoś wstawił LinkedList zamiast ArrayList to byłoby średnio, ale ponieważ programista Javy zwykle używa ArrayList więc problemu sie nie spotyka. Odwrotna sytuacja jest możliwa, ale na tyle nietypowa, że nie pamiętam żebym kiedykolwiek widział (ale mogłem zapomnieć).

Przeciez to troche zalezy od tego co kto programuje. W biznesowym korpo kodzie gdzie listy maja po 5-15 elementow i nic ambitnego sie z nimi nie robi no to whatever. Ale przy pisaniu jakiegos AI te optymalizacje juz maja znaczenie.

@stivens pech polega na tym, że w kodzie gdzie to ma znaczenie i tak zwykle schodzi się na tablice prymitywów :-) (dokładnie zresztą w AI na javie).

Jeśli piszesz np. parser i nie wiesz ile elementów masz do sparsowania (a musisz je zapamiętywać), to wtedy warto wiedzieć, że lepiej użyć LinkedList . Według mnie ważniejsza od samej znajomości tego jak te struktury są zbudowane jest umiejętność określenia w jakich sytuacjach konkretna implementacja będzie lepsza.

Co do samej LinkedList to osobiście miałem sytuację, gdzie legacy aplikacja robiła cache "sesji" który potrafił spuchnąć do 30GB heapa - po zmianie implementacji na BitSet zużycie nie przekraczało 4GB :)

Domyślnie używałem ArrayList bo są szybsze przy odczycie. Nigdy nie spotkałem kodu gdzie LinkedList byłoby szybsze.

BTW ciekawa jest sytuacja gdy ma się niemutowalne listy. Tam naprawdę trzeba wybrać dobrą. I widać to już nawet na łańcuchach znaków w Haskellu

Twoja ankieta właściwie jest tożsama z ankietą: "Używasz array'ów czy list jednokierunkowych dwukierunkowych?".

@TomRiddle: niekoniecznie. Większość dobrych przykładów użycia linked list jakie znam używa intrusive lists (np http://www.davidespataro.it/kernel-linux-list-efficient-generic-linked-list/). Uproszczonym Javowym odpowiednikiem byłoby:

class E {
// some data here
  E next;
}

"Opakowane" kontenery nie mają wielu zalet, które są szczególnie uwydatione, gdy używa się list jednokierunkowych np. operacje atomic albo "multikontenery": takie hybrydy, gdzie element jest w wielu kontenerach na raz, w porównaniu do np. LinkedHashSet to nie jest zahardkodowany ulep, tylko dowolna kompozycja

@KamilAdam: Dlaczego w przypadku niemutowalnych kolekcji ma znaczenie jaka implementacja została wybrana?

Dlatego że jak masz LinkedList to możesz to niej preapendowac łatwo. W przypadku gdy masz kolekcję opartą o tablice musisz kopiować całą tablicę i dodawać

piotrpo napisał(a):

@KamilAdam: Dlaczego w przypadku niemutowalnych kolekcji ma znaczenie jaka implementacja została wybrana?

Bo są dramatyczne różnice przy modyfikacji kolekcji niemutowalnych. Załóżmy że chcesz dodać lub odjąć element z listy niemodyfikowalnej:

• W przypadku niemutowalnego Vector musisz przepisać wszystkie elementy (ale za to jest najszybszy do odczytu) to bardziej skompilowane. Usuwanie jest w czasie O(1), ale dodawanie w czasie O(n)
• W przypadku klasycznej listy linkowanej List możesz swobodnie dodawać i usuwać elementy, ale tylko od strony głowy. Działa dobrze jako stos, ale jak chcesz coś głębiej zmieniać to jest to liniowe do indeksu
• W przypadku DList (i prawdopodobnie FMList) możesz swobodnie dodawać z obu stron, ale usuwanie jest kosztowne
• W przypadki Sequence możesz robić modyfikacje ze stałym czasem log n. Prawdopodobnie pod spodem to są drzewa, ale nie sprawdzałem implementacji

Więcej implementacji nie znam :D

A czy w przypadku ArrayList pamięć nie jest ciągła? Bo jeśli tak to będzie wielokrotnie szybsza przez ograniczenie zjawiska cache miss.

Ostatnio dosyć często korzystam z dużych kolekcji i praktycznie zawsze muszę mieć optymalizację na względzie. Koniec końców wygląda to tak, że w 90% przypadków wybieram albo tablicę, albo ArrayList (jeśli to typ prymitywny to coś z Trove). Używanie LinkedList ma sens tylko i wyłącznie wtedy, kiedy chcesz się bawić w modyfikację istniejących kolekcji - przy przetwarzaniu większych ilości danych jednak rzadko trzeba modyfikować kolekcje na żywca.

Ja mam właśnie taką sytuację gdy typ listy ma znaczenie.
Korzystam z biblioteki JTS do tworzenia geometrii, i tam sobie wymyślono że można stworzyć geometrię tylko z tablicy Coordinates[] (https://locationtech.github.io/jts/javadoc/org/locationtech/jts/geom/GeometryFactory.html). I o ile taką tablicę robi się dość prosto z ArrayList metodą toArray, pewnie dlatego że w obu przypadkach pamięć jest liniowa, to już z generycznej Listy się nie da i trzeba robić kopię całej listy.

myślę, że List.toArray w javce zawsze kopiuje całą tablicę

@KamilAdam:

Jak masz klasyczną linked listę niemutowalą to czas tworzenia nowej kolekcji przy dodawaniu od przodu wynosi O(1), jest to czas dodania nowego elementu z przodu. Dodatkowa pamięć nie jest używana. Używana jest tylko pamięć na nowy element. Cała reszta jest współdzielona. Żadna cześć starej listy nie jest przepisywana

Albo inaczej rozumiemy niemutowalność, albo ja nie rozumiem jak działa LinkedLista :)
Szybka implementacja w Java:

class MyLinekdList<T>{
  Item<T> firstItem;
  public MyLinkedList(List<T> elements){
    elements.forEach(e -> MyLinkedList::addElement(e);
  }
  private void addElement(T element){
    firstItem = new Element(element, firstItem);
  }

private class Item<T>{
  T element;
  Item<T> nextItem;
  Item(element, item){
    this.element = element;
    this.item = item;
  }
}

Elementy listy nie będą oczywiście kopiowane, bo przenoszone są jedynie referencje, ale cała struktura, w której przechowywane są te elementy (Item) jest jednak tworzona od początku i jakąś tam pamięć zajmuje.

Kto nigdy nie dostał outofmemory na copy w arrayliście na produkcji niech pierwszy rzuci kamień xD.
Niestety randomowość wybierania przez deweloperów implementacji często powoduj dużo problemów w przewidywalności różnego rodzaju bibliotek.

@piotrpo: tylko że tak nie wygląda funkcyjna, niemutowalna linked lista :D
Funkcyjna niemutowalna linked lista wygląda tak List.
Z czego najważniejsze jest List.Nil czyli pusta lista i List.Cons czyli komórka do dodawania nowego elementu na początek.

Fragmenty implementacja w Javie z Vavr

//Komórka Cons
private Cons(T head, List<T> tail) {
        this.head = head;
        this.tail = tail;
        this.length = 1 + tail.length();
    }

//Dodanie nowego elementu na początek, stara lista się nie zmienia ani nie jest przepisywana
@Override
  public final List<T> prepend(T element) {
      return new Cons<>(element, this);
  }

//Utworzenie listy jednoelementowej to dodanie elementu do pustej list
public static <T> List<T> of(T element) {
      return new Cons<>(element, Nil.instance());
  }

A tutaj ładny obrazek współdzielenia list niemutowalnych

GutekSan napisał(a):

I o ile taką tablicę robi się dość prosto z ArrayList metodą toArray, pewnie dlatego że w obu przypadkach pamięć jest liniowa, to już z generycznej Listy się nie da i trzeba robić kopię całej listy.

Wibowit napisał(a):

myślę, że List.toArray w javce zawsze kopiuje całą tablicę

Post Wibowita w stylu niszczymy dzieciństwo :P
I pewnie znów ma rację :D

ArrayList:

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

Arrays:

   @SuppressWarnings("unchecked")
   public static <T> T[] copyOf(T[] original, int newLength) {
       return (T[]) copyOf(original, newLength, original.getClass());
   }

  @HotSpotIntrinsicCandidate
  public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
      @SuppressWarnings("unchecked")
      T[] copy = ((Object)newType == (Object)Object[].class)
          ? (T[]) new Object[newLength]
          : (T[]) Array.newInstance(newType.getComponentType(), newLength);
      System.arraycopy(original, 0, copy, 0,
                       Math.min(original.length, newLength));
      return copy;
  }

Ja widziałem jak do listy było wstawiane kilkaset unikalnych elementów i później wyszukiwanie w tej liście liniowo (wyszukiwanie z kilkudziesięciu różnych miejsc) :)
Jak robiłem review tego kodu to się dowiedziałem od jednego z programistów, że użycie Set w tej sytuacji to premature optimization :)
Programista, który to pisał nie znał różniczy między ArrayList, LinkedList a o Set nie słyszał.
Tak więc podążając dalej tym tropem można zadać kolejne pytanie.
Czy wiesz jak utworzyć tablicę w Javie?
Ile razy tworzyłeś tablicę w Javie?
Czy to że nie wiesz jak utworzyć tablicę w Javie ma znaczenie?
Nie martw się, to że nie wiesz jak utworzyć tablicę w Javie nie ma znaczenia.
Kogo by to obchodziło, zawsze można przecież doczytać, nauczysz się w pracy.

@snakeomeister: ja widziałem jak koledzy z zespołu robili coś równie nieoptymalnego, ale nieco mniej oczywistego, czyli odpalanie metody def find(p: (A) => Boolean): Option[A] na Secie. to jest liniowa operacja, bo taka funkcja (tzn. p: (A) => Boolean) nie pozwala na szybkie wybranie elementu ze zbioru. wynik jest taki sam - liniowe przechodzenie przez kolekcję zamiast szybkiego lookupu.

Wibowit napisał(a):

@snakeomeister: ja widziałem jak koledzy z zespołu robili coś równie nieoptymalnego, ale nieco mniej oczywistego, czyli odpalanie metody def find(p: (A) => Boolean): Option[A] na Secie. to jest liniowa operacja, bo taka funkcja (tutaj: p) nie pozwala na szybkie wybranie elementu ze zbioru. wynik jest taki sam - liniowe przechodzenie przez kolekcję zamiast szybkiego lookupu.

Tak też można :) Ogólnie chodzi mi o to, że widzę taki trend, że wszystkie pytania na rozmowach są bez sensu i po prostu mnie zatrudnijcie ja jestem super programistą, który nie zna różnicy między ArrayList a LinkedList, ale chcę 15k na rękę, bo mam bardzo dobre soft skille :)

1. Codility - nie bo z algorytmów się nie korzysta, kogo tam obchodzi jak zaimplementować jakiś głupi MergeSort
2. Jakieś pytanie z frameworka z którego korzystamy w pracy - nie bo można znaleźć w internecie i to są w ogóle jakieś bezsensowne detale
3. Zadanie praktyczne - nie bo nie będę tracić czasu

Ja się w takim razie pytam, jak kogoś można zrekrutować?
Na jakiej podstawie stwierdzić czy ktoś jest dobrym programistą czy nie?

snakeomeister napisał(a):

1. Codility - nie bo z algorytmów się nie korzysta, kogo tam obchodzi jak zaimplementować jakiś głupi MergeSort
2. Jakieś pytanie z frameworka z którego korzystamy w pracy - nie bo można znaleźć w internecie i to są w ogóle jakieś bezsensowne detale
3. Zadanie praktyczne - nie bo nie będę tracić czasu

Ja się w takim razie pytam, jak kogoś można zrekrutować?
Na jakiej podstawie stwierdzić czy ktoś jest dobrym programistą czy nie?

Można poprosić o to, by wybrał jakiś projekt w którym pracował i opisał wyzwania w nim oraz rozwiązania, które stworzył dla tych problemów. Z zastrzeżeniem, że to ma być dialog - przepytywany coś tam opowiada, ale my (rekrutujący) dopytujemy o interesujące nas szczegóły i kwestie, w których jesteśmy na tyle mocni, żeby od razu wiedzieć czy koleś opowiada z sensem.

snakeomeister napisał(a):

Tak też można :) Ogólnie chodzi mi o to, że widzę taki trend, że wszystkie pytania na rozmowach są bez sensu i po prostu mnie zatrudnijcie ja jestem super programistą, który nie zna różnicy między ArrayList a LinkedList, ale chcę 15k na rękę, bo mam bardzo dobre soft skille :)

Pytania na rozmowach są bez sensu, ale z trochę innych powodów:

1. Codility - nie bo z algorytmów się nie korzysta, kogo tam obchodzi jak zaimplementować jakiś głupi MergeSort

Stres zmienia dużo. Zadania codility odrzucają sporą część kumatych kandudatów, a w rezultacie przechodzi ten, który najmniej się zdenerwował.

Jakieś pytanie z frameworka z którego korzystamy w pracy - nie bo można znaleźć w internecie i to są w ogóle jakieś bezsensowne detale

Nie jest totalnie bez sensu. Ma spore ryzyko, że zatrudnisz sprawnego klikacza. a nie dobrego inżyniera. Oczywiście zależy jeszcze, czy pytasz o @Autowire, czy np. o DynamicProxy

1. Zadanie praktyczne - nie bo nie będę tracić czasu

To jest prawda, chociaż nie jest bez sensu. Zadania prarktyczne wymagają niestety dużo czasu po obu stronach

Dodam jescze, ze taki egzamin z podstaw Javy zaczynam uważać za również pozbawiony sensu, nawet nie ze względu na to, że wiedza o czym się różni ArrayList od LinkedList jest niepotrzebna, tylko pytają o to (i parę innych rzeczy) na wszystkich rozmowach, więc przechodząc zestaw 100 pytań rekrutacyjnych można wykuć odpowiedzi. I całkiem sporo kandydatów tak robi.

Ja się w takim razie pytam, jak kogoś można zrekrutować?
Na jakiej podstawie stwierdzić czy ktoś jest dobrym programistą czy nie?

I to jest bardzo dobre pytanie na wątek w dziale kariera. Pewnie punktem wyjścia jest "co to znaczy być dobrym programistą w twoim projekcie".

W tym wątku bardziej zastanawiałem się, skąd się bierze Javowy fetysz na kolekcje, bo z mojego doświadczenia przytłaczająca większość przypadków użycia to takie, gdzie do listy wrzucane jest 20 elementów, a wszystko co się z nimi robi to iterowanie po elementach, a wszystko opakowane w operacje o mega narzucie czasowym typu komunikacja http, a jak pojawiało się coś faktycznie wymagającego optymalizacji, to java.collections nie było w stanie pomóc.
Z drugiej strony jest to pytanie lecące zaraz po "dzień dobry" na 99% rozmów kwalifikacyjnych i chciałem sprawdzić, czy moja opinia jest podzielana przez innych, czy może horyzont kończy mi się na granicy mojego grajdołka.

Pytania na rozmowach są bez sensu, ale z trochę innych powodów:

1. Codility - nie bo z algorytmów się nie korzysta, kogo tam obchodzi jak zaimplementować jakiś głupi MergeSort

Stres zmienia dużo. Zadania codility odrzucają sporą część kumatych kandudatów, a w rezultacie przechodzi ten, który najmniej się zdenerwował.

Może właśnie o to chodzi, żeby znaleźć tych, którzy są na tyle dobrzy, że tego typu zadania ich nie stresują?
Nawet jeżeli znają rozwiązanie i nie rozwiązali tego tylko ze względu na stres, to może też znaczy że się nie nadają bo w pracy programisty jednak niekiedy stresu może być dużo?
Jeżeli takie zadanie rozwiązuje się live z kandydatem wtedy można też przy okazji sprawdzić techniki komunikacji.

Nie jest totalnie bez sensu. Ma spore ryzyko, że zatrudnisz sprawnego klikacza. a nie dobrego inżyniera. Oczywiście zależy jeszcze, czy pytasz o @Autowire, czy np. o DynamicProxy

Ok, tu się zgodzę :)

To jest prawda, chociaż nie jest bez sensu. Zadania prarktyczne wymagają niestety dużo czasu po obu stronach

Może warto wymyślać zadania, które rzeczywiście można rozwiązać w 2-4h?
Np. to samo co na codility/leetcode itp, tyle że wtedy pewnie jest duże ryzyko, że ktoś zrobi copy&paste.

Dodam jescze, ze taki egzamin z podstaw Javy zaczynam uważać za również pozbawiony sensu, nawet nie ze względu na to, że wiedza o czym się różni ArrayList od LinkedList jest niepotrzebna, tylko pytają o to (i parę innych rzeczy) na wszystkich rozmowach, więc przechodząc zestaw 100 pytań rekrutacyjnych można wykuć odpowiedzi. I całkiem sporo kandydatów tak robi.

Przynajmniej wykuwając odpowiedzi czegoś się nauczą :)

Z drugiej strony jest to pytanie lecące zaraz po "dzień dobry" na 99% rozmów kwalifikacyjnych i chciałem sprawdzić, czy moja opinia jest podzielana przez innych, czy może horyzont kończy mi się na granicy mojego grajdołka.

Odpowiadając na to pytanie to mi się przytrafiły kilka(naście) razy tego typu sytuacje, gdzie to miało znaczenie, więc chyba nie za dużo.

Imho taką różnicę moim zdaniem trzeba znać, niezależnie od tego ile razy to ma realne zastosowanie, bo jest to dosyć podstawowa wiedza.