Zastanawiam się nad wypełnieniem kolekcji dużą liczbą unikatowych obiektów. W jaki sposób koszt wstawki w zestawie (np. HashSet) jest porównywany z listą (np. ArrayList)?Wstawianie kolekcji Java: zestawienie z listą
Mam wrażenie, że duplikacja w zestawach może spowodować niewielkie obciążenie.
Nie ma "podwójnej eliminacji", takiej jak porównanie wszystkich istniejących elementów. Jeśli wstawisz do zestawu skrótu, to naprawdę słownik elementów po haśle. Nie ma duplikatu sprawdzania, chyba że istnieją już elementy z tym samym kodem mieszania. Biorąc pod uwagę rozsądną (dobrze rozłożoną) funkcję skrótu, nie jest tak źle.
Jak zauważył Will, ze względu na strukturę słownika HashSet jest prawdopodobnie nieco wolniejsza niż ArrayList (chyba że chcesz wstawić "między" istniejącymi elementami). Jest również nieco większy. Nie jestem pewien, czy to znacząca różnica.
Duplikacja eliminacji jest obecna, jest nieodłączna od struktury danych. –
Dobrze. Chodzi mi o to, że zazwyczaj nie ma duplikacji, która zawsze porównałaby nowo wstawiony element do wszystkich istniejących (chyba że zawaliłeś 'hashCode'). –
Dzięki za wyjaśnienia. Ciągłe wstawianie na listę jest zatem trochę mniej kosztowne pod względem koncepcyjnym, prawda? – Will
Trzeba porównać konkretne implementacje (np HashSet z ArrayList), ponieważ abstrakcyjne interfejsy Set/List naprawdę nie powiedzieć nic na temat wydajności.
Wstawianie do HashSet jest bardzo tanią operacją, o ile tylko wstawiany obiekt hashCode() jest w normie. Wciąż będzie nieco wolniejszy niż ArrayList, ponieważ jego wstawienie jest prostym wstawieniem do tablicy (zakładając wstawienie na końcu i wciąż jest wolna przestrzeń, nie uwzględniam zmiany rozmiaru wewnętrznej tablicy, ponieważ ten sam koszt dotyczy HashSet także).
Masz rację: ustawione struktury są z natury bardziej złożone, aby rozpoznawać i eliminować duplikaty. To, czy koszty ogólne są znaczące dla twojego przypadku, powinno zostać przetestowane za pomocą testu porównawczego.
Kolejnym czynnikiem jest wykorzystanie pamięci. Jeśli twoje obiekty są bardzo małe, obciążenie pamięci wprowadzone przez ustawioną strukturę może być znaczące. W najbardziej ekstremalnym przypadku (TreeSet<Integer> vs. ArrayList<Integer>) ustawiona struktura może wymagać więcej niż 10 razy więcej pamięci.
Jeśli jesteś pewne dane twoje dane będą unikalne, użyj listy. Możesz użyć Ustawy do wymuszania tej reguły na.
Sets are faster than Lists jeśli masz duży zestaw danych, a inverse is true dla mniejszych zestawów danych. Nie osobiście przetestowałem tego roszczenia.
Który typ listy?
Należy także rozważyć, której listy użyć. LinkedLists są szybsze przy dodawaniu, usuwaniu elementów.
ArrayLists są szybsze przy dostępie swobodnym (for pętle itp), ale można to obejść stosując Iterator o LinkedList. ArrayLists są dużo szybciej na: list.toArray().
Nie jestem pewien, czy połączone listy są szybkie do wstawienia ... Wydawało się, że czas (czas) na wyszukiwanie pozycji, a następnie stały (i niski) czas dla samego wstawienia. LinkedList nie zapewnia losowego dostępu do danych. Co więcej, iterator ** nie ** zapewnia dostęp losowy. – Agemen
W rzeczywistości podejrzewam, że wszystko zależy od implementacji, a PO może z łatwością budować własne. Interfejsy List i Set oczywiście nie zawierają żadnego konkretnego kodu, więc można zrobić szybciej niż inne. To powiedziawszy, nie jestem pewien jak, ale jestem ogromnie pod wrażeniem LinkedList i zamieniony na to po tym, jak odkryłem, że ArrayList jest zbyt wolny. Robiłem to 'add()' i iteracja – Redandwhite
Wynika to z konstrukcji listy LinkedList, a także dlatego, że regularnie musisz wykonywać kopię tablicy przy korzystaniu z add on a ArrayList. LinkedLists są naprawdę wydajne dla wstawień na początku lub na końcu, ale zdecydowanie nie dla dostępu losowego. Wstawienia nie są ograniczone do operacji dodawania. – Agemen
Jeśli celem jest niepowtarzalność elementów, należy użyć implementacji interfejsu java.util.Set.Klasa java.util.HashSet i i O (alfa) (bliska O (1) w najlepszym przypadku) złożoności dla wstawiania, usuwania i zawiera sprawdzanie.
ArrayList mieć O (n) dla przedmiotu (nie Index) zawiera kontrolę (trzeba przejść przez cały listy) oraz wprowadzenie (jeśli wstawiania nie jest końca listy, trzeba przesunąć cały tablica podkreślenia).
Można użyć LinkedHashSet, które zachowuje kolejność wstawiania i ma taki sam potencjał HashSet (zajmuje tylko nieco więcej pamięci).
Nie sądzę, aby można było wydać orzeczenie tylko na koszt budowy kolekcji. Inne rzeczy, które należy wziąć pod uwagę to:
Wszystko to może wpłynąć na wybór struktury danych.
Java Lista:
Jeśli nie ma takiego wymogu, że trzeba zachować duplikat lub nie. Następnie możesz użyć Listy zamiast Ustaw.
Lista jest interfejsem w strukturze kolekcji. Który rozszerza interfejs kolekcji. i ArrayList, LinkedList jest implementacją interfejsu List.
Kiedy używać ArrayList lub LinkedList
ArrayList: Jeśli masz taki wymóg, że w większości aplikacji praca uzyskuje dostęp do danych. Następnie powinieneś przejść do ArrayList. ponieważ ArrayList implementuje interfejs RtandomAccess, który jest interfejsem znacznika. ze względu na interfejs Markera, ArrayList ma możliwość dostępu do danych w czasie O (1). i możesz użyć ArrayList przez LinkedList, gdzie chcesz uzyskać dane zgodnie ze zleceniem reklamowym.
LinkedList: Jeśli masz taki wymóg, że twoja praca to głównie wstawianie lub usuwanie. Następnie powinieneś użyć LinkedList przez ArrayList. ponieważ w LinkedList wstawianie i usuwanie odbywa się w czasie O (1), podczas gdy w ArrayList jest to czas O (n).
Java Set:
Jeśli masz wymagania w swoim wniosku, że nie ma żadnych duplikatów. Następnie powinieneś wybrać Set zamiast List. Ponieważ Set nie przechowuje żadnych duplikatów. Ponieważ Set działa na zasadzie Hashing. Jeśli dodamy obiekt do Seta, najpierw sprawdza on kod obiektu w wiadrze, jeśli znajduje się w nim kod hash, a nie doda tego obiektu.
Jeśli masz już jakiś mechanizm, który gwarantuje wyjątkowość, po co zawracać sobie głowę zestawem? Jeśli tego nie zrobisz i musisz zagwarantować wyjątkowość, to lista zdecydowanie nie jest tym, czego potrzebujesz. – Andrew