Diskusia – 4. diel - Spojový zoznam v Jave

Späť

Upozorňujeme, že diskusie pod našimi online kurzami sú nemoderované a primárne slúžia na získavanie spätnej väzby pre budúce vylepšenie kurzov. Pre študentov našich rekvalifikačných kurzov ponúkame možnosť priameho kontaktu s lektormi a študijným referentom pre osobné konzultácie a podporu v rámci ich štúdia. Toto je exkluzívna služba, ktorá zaisťuje kvalitnú a cielenú pomoc v prípade akýchkoľvek otázok alebo projektov.

Komentáre

Pavel Javorek

Člen

Pavel Javorek:10.2.2021 23:32

Ahoj
Výborně napsané
Měl bych akorát otázku která z těchto dvou kolekcí bude lepší pokud například v kolekci o 1000 prvcích budu hledat prvek pomocí indexOf(), linked nebo array. Jestli dobře chápu tak ideálnější by byl Array, ale není mi úplně jasné proč?

Odpovedať

10.2.2021 23:32

Petr Štechmüller

Tvůrce

Petr Štechmüller:11.2.2021 7:24

Ahoj, zdání někdy může klamat.
Podíváš-li se do zdrojového kódu, budeš překvapen, že implementace metody indexOf je v obou případech "stejná".

ArrayList

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

LinkedList

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

Pokud bys chtěl vyhledávat v kolekci, se kterou už dále nebudeš pracovat, je vhodné si ji převést na pole a použít binární vyhledávání.

Odpovedať

11.2.2021 7:24

Pokud spolu kód a komentář nekorespondují, budou patrně oba chybné

Pavel Javorek

Člen

Pavel Javorek:13.2.2021 22:46

Super
Diky za rychlou odpoved

Odpovedať

13.2.2021 22:46

Lubor Pešek

Člen

Lubor Pešek:18.4.2021 11:14

Čistě jen na diskuzi. Vytvořil jsem si velmi jednoduchý porovnávač obou kolekcí. Tak když tak poprosím Peťu Štechmüllera, aby to nějak okomentoval (třeba tam na něco zapomínám, nebo zátěž není dostatečná), ale rozdíl mezi vkládáním jednoho prvku mi vychází v průměru okolo 10 milisekund pro ArrayList. Linked list to vkládá skutečně okamžitě.
Ale jak píšeš úplně na konci, že by bylo "hodně" pomalé, tak bych u jednoho prvku očekával aspoň takových 200 milisekund.
Nebo i těch 10 může být v některých případech problém?

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class DiffList {

    private static Long time, arrayTime, linkedTime;

    public static void main(String[] args) {
        final List<Integer> array = new ArrayList<>();
        final LinkedList<Integer> linked = new LinkedList<>();

        createNewList(1000, array, linked);
        insertIntoList(array, linked, 50);
        insertIntoList(array, linked, 654);

        System.out.println();

        createNewList(10000000, array, linked);
        insertIntoList(array, linked, 50);
        insertIntoList(array, linked, 654);
        insertIntoList(array, linked, 777856);
    }

    public static void createNewList(int countOfElements, List array, List linked) {
        array.clear();
        linked.clear();
        System.out.println(String.format("Porovnání vytváření obou kolekcí pro %d prvků", countOfElements));

        // array time
        time = System.currentTimeMillis();
        for (int i = 1; i <= countOfElements; i++) {
            array.add(i);
        }
        arrayTime = System.currentTimeMillis() - time;

        // linked time
        time = System.currentTimeMillis();
        for (int i = 1; i <= countOfElements; i++) {
            linked.add(i);
        }
        linkedTime = System.currentTimeMillis() - time;

        ouptut(arrayTime, linkedTime);
    }

    public static void insertIntoList(List array, List linked, int index) {
        System.out.println(String.format("Vložení prvku na index č.%d", index));
        // array time
        time = System.currentTimeMillis();
        array.add(index, 100);
        arrayTime = System.currentTimeMillis() - time;

        // linked time
        time = System.currentTimeMillis();
        linked.add(index, 100);
        linkedTime = System.currentTimeMillis() - time;

        ouptut(arrayTime, linkedTime);
    }

    private static void ouptut(Long arrayTime, Long linkedTime) {
        System.out.println(String.format("Array : Linked = %d ms : %d ms", arrayTime, linkedTime));
    }
}

Odpovedať

18.4.2021 11:14

Existují dva způsoby, jak vyřešit problém. Za prvé vyhoďte počítač z okna. Za druhé vyhoďte okna z počítače.

Petr Štechmüller

Tvůrce

Petr Štechmüller:18.4.2021 11:47

Ahoj,

je otázka, na jak výkonném stroji jsi tohle měřil. Samozřejmě na něčem hodně výkonném to "poletí".

Primárně bych se asi zaměřil na účelu použití té datové struktury. Výhody a nevýhody pole a spojového seznamu jsou například pěkně popsány zde

Když z toho vytáhnu pro naši diskuzi podstatné věci, tak platí, že:

ArrayList
- přístup k prvku - get(i) = O(1)
- vložení prvku - add(obj) = O(n) - pro nejhorší případ, kdy je potřeba celé pole překopírovat do většího uceleného celku
LinkedList
- přístup k prvku - O(n)
- vložení prvku - O(1)

Z toho je celkem dobře patrné, že LinkedList budeš používat přimárně tam, kde budeš chtít často vkládat prvky, ale nebudeš k nim chtít náhodně přistupovat.

Naopak ArrayList použiješ v případě, že k prvkům budeš chtít velmi často náhodně přistupovat, ale nebudeš je moc často vkládat.

Odpovedať

18.4.2021 11:47

Pokud spolu kód a komentář nekorespondují, budou patrně oba chybné

Jan Trnka

Člen

Jan Trnka:16.1.2023 12:56

Zase velmi dobře napsaná lekce.

Odpovedať

16.1.2023 12:56

Niki Vávrová

Člen

Niki Vávrová:2.2.2023 16:30

Velmi dobře napsaná a pochopitelná lekce.

Odpovedať

2.2.2023 16:30

ing. SARNOVSKÝ Petr

Člen

ing. SARNOVSKÝ Petr:21.11.2023 18:12

Obrázek je celý špatně :-)

Editované 21.11.2023 18:15

Odpovedať

21.11.2023 18:12

Jiří Šála

Člen

Jiří Šála:8. februára 14:26

Upozorňuji na chybu v textu této stránky:?? Poslední kód.
Aby vystup odpovídal, v kódu by mělo byt "seznam.remove(3);"

Odpovedať

8. februára 14:26

Atrament

Člen IT Redactor Gang

Atrament:8. februára 23:46

To určitě ne, protože pak by ten výstup byl 1, 2, 3, 32, 4, 5

Odpovedať

8. februára 23:46

Robíme čo je v našich silách, aby bola tunajšia diskusia čo najkvalitnejšia. Preto do nej tiež môžu prispievať len registrovaní členovia. Pre zapojenie sa do diskusie sa zaloguj. Ak ešte nemáš účet, zaregistruj sa, je to zadarmo.

Zatiaľ nikto nevložil komentár - buď prvý!

Najčastejšie vyhľadávané

Diskusia – 4. diel - Spojový zoznam v Jave