Czy istnieje implementacja listy bez duplikatów?


86

Wiem o tym SortedSet, ale w moim przypadku potrzebuję czegoś, co implementuje List, a nieSet . Więc czy jest tam implementacja, w API czy gdzie indziej?

Samo wdrożenie nie powinno być trudne, ale pomyślałem, dlaczego nie zapytać najpierw ludzi tutaj?


1
Dlaczego trzeba wdrożyć List? Zestawy są iterowalne, podobnie jak listy, więc przypuszczam, że metoda otrzymywania wymusza List z innego powodu.
Rob

@Rob Zgadza się, to żądanie zewnętrzne, a struktura danych zawiera cholernie dużo więcej niż jedną listę.
Yuval

Jeśli użytkownik chce LISTY, to jasne jest, że potrzebuje metod interfejsu LIST, których nie ma w interfejsie SET ...
marcolopes

Odpowiedzi:


92

W bibliotece standardowej nie ma kolekcji Java, która mogłaby to zrobić. LinkedHashSet<E>zachowuje jednak porządkowanie podobnie jak a List, więc jeśli zawiniesz zestaw w a, Listgdy chcesz go użyć jakoList , uzyskasz pożądaną semantykę.

Alternatywnie, kolekcje Commons (lub commons-collections4, dla wersji ogólnej) mają już plik, Listktóry robi to, co chcesz: SetUniqueList/ SetUniqueList<E>.


5
Klasa Commons jest dokładnie tym, czego potrzebuję, ale szef powiedział mi, żebym w końcu zaimplementował ją samodzielnie. W każdym razie 10x!
Yuval

5
No cóż, nie ma to jak odkrywanie na nowo koła! I tak dowiesz się teraz, czy potrzeba znowu się pojawi. collections15 to całkiem przydatna rzecz do kopania; W szczególności MultiMapy łagodzą ból związany z czymś, co często się wdraża.
Calum

19
@skaffman: właściwie nie jest idiotą, ale czasami wykonuje ruchy, które są ... cóż, dziwne. W każdym razie nie zamierzam wprowadzać błędów do produktu. Na dzisiejszym rynku jestem zadowolony ze swojej pracy i nie chcę trzaskać drzwiami i palić mostów, jeśli rozumiesz.
Yuval

3
Jestem dość zaskoczony, gdy SetUniqueList nie ma sparametryzowanego typu.
emeraldhieu

2
Jeffrey: Na platformach mobilnych system zazwyczaj usuwa nieużywane klasy, ale z pewnością istnieje wiele powodów, dla których możesz nie skorzystać z jednego z tych „normalnych” rozwiązań. Zawsze jest jakiś kompromis i żadne rozwiązanie nie naprawi wszystkich przypadków.
Calum

14

Oto co zrobiłem i to działa.

Zakładając, że muszę ArrayListpopracować z pierwszą rzeczą, którą zrobiłem, było stworzenie nowego LinkedHashMap.

LinkedHashSet<E> hashSet = new LinkedHashSet<E>()

Następnie próbuję dodać mój nowy element do LinkedHashSet. Metoda add nie zmienia LinkedHasSeti zwraca false, jeśli nowy element jest duplikatem. Jest to więc warunek, który mogę przetestować przed dodaniem do ArrayList.

if (hashSet.add(E)) arrayList.add(E);

Jest to prosty i elegancki sposób zapobiegania dodawaniu duplikatów do listy tablic. Jeśli chcesz, możesz go hermetyzować i przesłonić metodę add w klasie, która rozszerza ArrayList. Pamiętaj tylko, aby sobie z tym poradzić, addAllprzechodząc przez elementy i wywołując metodę add.


1
Tak, myślę, że jest to najlepsze rozwiązanie, możesz też po prostu użyć zwykłego HashSetu, a nie powiązanego, a następnie możesz używać swojej listy, jak chcesz, możesz także zdecydować, co robić w niektórych sytuacjach, np. dodając element wewnątrz listy przed określonym indeksem, możesz zdecydować, czy chcesz przenieść zduplikowany element w to miejsce, czy nie.
gyurix

Najlepsze rozwiązanie tutaj ... Opublikuje mój kod klasy
UniqueList

To zadziałało dla mnie, w moim algorytmie BFS Graph. Ponieważ miałem kilka węzłów, które dodałem do kolejki (LinkedList), tylko jeśli jeszcze ich nie było.
Jeancarlo Fontalvo

11

Oto co w końcu zrobiłem. Mam nadzieję, że to pomoże komuś innemu.

class NoDuplicatesList<E> extends LinkedList<E> {
    @Override
    public boolean add(E e) {
        if (this.contains(e)) {
            return false;
        }
        else {
            return super.add(e);
        }
    }

    @Override
    public boolean addAll(Collection<? extends E> collection) {
        Collection<E> copy = new LinkedList<E>(collection);
        copy.removeAll(this);
        return super.addAll(copy);
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> collection) {
        Collection<E> copy = new LinkedList<E>(collection);
        copy.removeAll(this);
        return super.addAll(index, copy);
    }

    @Override
    public void add(int index, E element) {
        if (this.contains(element)) {
            return;
        }
        else {
            super.add(index, element);
        }
    }
}   

10
Uważaj - LinkedList.contains () musi przeskanować całą listę, aby określić, czy obiekt znajduje się na liście. Oznacza to, że kiedy dodajesz obiekty do dużej listy, cała lista jest skanowana pod kątem każdej operacji dodawania (w najgorszym przypadku). To może skończyć się POWOLI.
mat b

8
Ponadto, nadpisanie addAll nie sprawdza duplikatów w kolekcji przekazywanej do addAll ().
mat b

@mattb W jaki sposób rozwiązalibyście ten problem: w systemie Android podczas wiązania obiektów z widokiem elementu listy, otrzymujemy położenie elementu w adapterze widoku. Ponieważ zestawy nie mają indeksu, jedynym sposobem jest sprawdzenie, czy obiekt istnieje podczas używania list, to iteracja i wyszukanie istniejącej kopii.
TheRealChx101

6

Dlaczego nie hermetyzować zestawu listą, posortuj jak:

new ArrayList( new LinkedHashSet() )

To pozostawia inną implementację dla kogoś, kto jest prawdziwym mistrzem Kolekcji ;-)


4
Ten konstruktor kopiuje zawartość zestawu do nowej listy, zamiast ją zawijać.
Calum

@Calum, to prawda, ale zamiast martwić się o nie dodawanie duplikatów do listy, może dodać swoje obiekty do zestawu (i pozwolić zestawowi martwić się odfiltrowaniem duplikatów) i po prostu zawinąć ten zestaw w listę podczas przekazywania go do metoda zewnętrzna.
mat b

4
Spowoduje to skopiowanie zestawu na listę, ale nie masz żadnej znanej kolejności. Ale o to w tym wszystkim chodzi.
Stycznia

4

Powinieneś poważnie rozważyć odpowiedź dhillera:

  1. Zamiast martwić się dodawaniem obiektów do listy bez duplikatów, dodaj je do zestawu (dowolnej implementacji), który z natury odfiltruje duplikaty.
  2. Kiedy musisz wywołać metodę, która wymaga listy, zawiń ją w a new ArrayList(set)(lub new LinkedList(set)cokolwiek).

Myślę, że rozwiązanie, które opublikowałeś, NoDuplicatesListma pewne problemy, głównie z contains()metodą, a Twoja klasa nie obsługuje sprawdzania duplikatów w kolekcji przekazanej do addAll()metody.


Chciałbym dowiedzieć się o tych problemach z zawartością (). Jeśli chodzi o metodę addAll (), tworzę kopię podanej kolekcji i usuwam wszystkie obiekty znajdujące się już w 'this'. Jak to nie radzi sobie z duplikatami?
Yuval

Jak wspomniałem w moim komentarzu do postu w Twojej klasie, zawiera () musi przeskanować całą listę (w najgorszym przypadku), aby sprawdzić, czy obiekt znajduje się na liście. Jeśli masz listę 1 miliona pozycji i dodasz ją indywidualnie po 10, to (w najgorszym przypadku) skanowanych jest ponad dziesięć milionów pozycji.
mat b

Jeśli chodzi o metodę addAll (), jeśli kolekcja przekazana do metody addAll zawiera same duplikaty, nie są one wykrywane. Na przykład: twoja lista {A, B, C, D} lista parametrów {B, D, E, E, E}. Tworzysz kopię parametru, a po usunięciu wszystkiego zawiera {E, E, E}.
mat b

Problem z addAll () nie jest dla mnie naprawdę istotny, ponieważ używam NoDuplicatesList w całej procedurze, a addAll () powinno otrzymywać inny NoDuplicatesList jako swój parametr. Co byś zasugerował, aby ulepszyć działanie zawiera ()?
Yuval

3

Potrzebowałem czegoś takiego, więc poszedłem do wspólnych kolekcji i użyłem SetUniqueList, ale kiedy przeprowadziłem jakiś test wydajności, stwierdziłem, że wydaje się nie zoptymalizowany w porównaniu z przypadkiem, jeśli chcę użyć a Seti uzyskać ArrayużycieSet.toArray() .

SetUniqueTestWzięło 20: 1 czas wypełnić, a następnie trawers 100000 Strings porównaniu do innych realizacji, która jest duża różnica sprawa.

Tak więc, jeśli martwisz się o wydajność, polecam ci użyć Set and Get an Array zamiast używać SetUniqueList, chyba że naprawdę potrzebujesz logiki SetUniqueList, wtedy musisz sprawdzić inne rozwiązania ...

Główna metoda testowania kodu :

public static void main(String[] args) {


SetUniqueList pq = SetUniqueList.decorate(new ArrayList());
Set s = new TreeSet();

long t1 = 0L;
long t2 = 0L;
String t;


t1 = System.nanoTime();
for (int i = 0; i < 200000; i++) {
    pq.add("a" + Math.random());
}
while (!pq.isEmpty()) {
    t = (String) pq.remove(0);
}
t1 = System.nanoTime() - t1;

t2 = System.nanoTime();
for (int i = 0; i < 200000; i++) {
    s.add("a" + Math.random());
}

s.clear();
String[] d = (String[]) s.toArray(new String[0]);
s.clear();
for (int i = 0; i < d.length; i++) {
    t = d[i];

}
t2 = System.nanoTime() - t2;

System.out.println((double)t1/1000/1000/1000); //seconds
System.out.println((double)t2/1000/1000/1000); //seconds
System.out.println(((double) t1) / t2);        //comparing results

}

Pozdrawiam, Mohammed Sleem


1

UWAGA: nie uwzględnia implementacji subList .

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Set;

public class UniqueList<T> extends ArrayList<T> {

    private static final long serialVersionUID = 1L;

    /** Unique elements SET */
    private final Set<T> set=new HashSet();

    /** Used by addAll methods */
    private Collection<T> addUnique(Collection<? extends T> col) {
        Collection<T> unique=new ArrayList();
        for(T e: col){
            if (set.add(e)) unique.add(e);
        }
        return unique;
    }

    @Override
    public boolean add(T e) {
        return set.add(e) ? super.add(e) : false;
    }

    @Override
    public boolean addAll(Collection<? extends T> col) {
        return super.addAll(addUnique(col));
    }

    @Override
    public void add(int index, T e) {
        if (set.add(e)) super.add(index, e);
    }

    @Override
    public boolean addAll(int index, Collection<? extends T> col) {
        return super.addAll(index, addUnique(col));
    }

}

0

Dokumentacja interfejsów zbiórki mówi:

Zestaw - zbiór, który nie może zawierać zduplikowanych elementów.
Lista - uporządkowana kolekcja (czasami nazywana sekwencją). Listy mogą zawierać zduplikowane elementy.

Więc jeśli nie chcesz duplikatów, prawdopodobnie nie powinieneś używać listy.


Wspomniałem konkretnie, że potrzebuję implementacji listy. Zaufaj mi, jest powód.
Yuval

Czy jest to spowodowane tym, że korzystasz z interfejsu API, który przyjmuje listę jako parametr (zamiast kolekcji)? To trochę denerwujące
Matt b

Właściwie API przyjmuje Map <AccountType, Map <AccountType, List <Account> >>, co oznacza trzymanie gdzieś w pobliżu dziesiątek do setek list ... ba.
Yuval

Konstruowanie funkcji prawdopodobieństwa z parami element-prawdopodobieństwo może obejmować brak duplikatów, chociaż zduplikowane elementy można po prostu scalić.
Al G Johnston

-1

w addmetodzie, dlaczego nie użyć HashSet.add()do sprawdzania duplikatów zamiast HashSet.consist(). HashSet.add()zwróci, truejeśli nie ma duplikatu i falseinaczej.


Co to jest HashSet#consist()?
naXa

-1

Nawiasem mówiąc, listy zezwalają na duplikaty. Możesz szybko zaimplementować UniqueArrayListi przesłonić wszystkie add/ insertfunkcje, które mają być sprawdzane contains()przed wywołaniem dziedziczonych metod. Do użytku osobistego możesz zaimplementować tylko addmetodę, której używasz, i przesłonić inne, aby zgłosić wyjątek na wypadek, gdyby przyszli programiści spróbowali użyć listy w inny sposób.


Byłem gotowy wrócić do tego pomysłu (co ostatecznie musiałem), jeśli nikt nie zasugerował czegoś lepszego = 8-). Zobacz moją własną odpowiedź powyżej.
Yuval

-3

Właśnie utworzyłem własną UniqueList w mojej własnej małej bibliotece w następujący sposób:

package com.bprog.collections;//my own little set of useful utilities and classes

import java.util.HashSet;
import java.util.ArrayList;
import java.util.List;
/**
*
* @author Jonathan
*/
public class UniqueList {

private HashSet masterSet = new HashSet();
private ArrayList growableUniques;
private Object[] returnable;

public UniqueList() {
    growableUniques = new ArrayList();
}

public UniqueList(int size) {
    growableUniques = new ArrayList(size);
}

public void add(Object thing) {
    if (!masterSet.contains(thing)) {
        masterSet.add(thing);
        growableUniques.add(thing);
    }
}

/**
 * Casts to an ArrayList of unique values
 * @return 
 */
public List getList(){
    return growableUniques;
}

public Object get(int index) {
    return growableUniques.get(index);
}

public Object[] toObjectArray() {
    int size = growableUniques.size();
    returnable = new Object[size];
    for (int i = 0; i < size; i++) {
        returnable[i] = growableUniques.get(i);
    }
    return returnable;
    }
}

Mam klasę TestCollections, która wygląda następująco:

package com.bprog.collections;
import com.bprog.out.Out;
/**
*
* @author Jonathan
*/
public class TestCollections {
    public static void main(String[] args){
        UniqueList ul = new UniqueList();
        ul.add("Test");
        ul.add("Test");
        ul.add("Not a copy");
        ul.add("Test"); 
        //should only contain two things
        Object[] content = ul.toObjectArray();
        Out.pl("Array Content",content);
    }
}

Działa w porządku. Wszystko, co robi, to dodaje do zestawu, jeśli jeszcze go nie ma i istnieje Arraylist, który jest zwrotny, a także tablica obiektów.


Tak, powinieneś dodać do niego trochę więcej metod implementacji interfejsu List.
gyurix
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.