Gibt es da draußen eine No-Duplicate-List-Implementierung?

85

Ich weiß Bescheid SortedSet, aber in meinem Fall brauche ich etwas, das implementiert wird List, und nicht Set. Gibt es da draußen eine Implementierung, in der API oder anderswo?

Es sollte nicht schwer sein, mich selbst zu implementieren, aber ich dachte mir, warum nicht zuerst die Leute hier fragen?

Yuval
quelle
1
Warum muss List implementiert werden? Sets sind wie Listen iterierbar, daher erzwingt die Empfangsmethode vermutlich List aus einem anderen Grund.
Rob
@Rob Das stimmt, es ist eine externe Anforderung, und die Datenstruktur enthält verdammt viel mehr als eine Liste.
Yuval
Wenn der Benutzer eine LISTE wünscht, ist klar, dass Methoden der LIST-Schnittstelle benötigt werden, die in der SET-Schnittstelle nicht vorhanden sind ...
marcolopes

Antworten:

91

Es gibt keine Java-Sammlung in der Standardbibliothek, um dies zu tun. LinkedHashSet<E>Die Reihenfolge bleibt jedoch ähnlich wie bei a erhalten. ListWenn Sie also Ihr Set in a einschließen, wenn Sie Listes als a verwenden möchten, Listerhalten Sie die gewünschte Semantik.

Alternativ haben die Commons-Sammlungen (oder commons-collections4für die generische Version) eine, die Listdas tut, was Sie bereits wollen: SetUniqueList/ SetUniqueList<E>.

Calum
quelle
5
Die Commons-Klasse ist genau das, was ich brauche, aber mein Chef sagte mir, ich solle sie irgendwann selbst implementieren. 10x sowieso!
Yuval
5
Na ja, nichts wie das Rad neu zu erfinden! Sie werden jetzt sowieso wissen, ob die Notwendigkeit wieder auftaucht. Sammlungen15 ist eine ziemlich nützliche Sache, um herumzutreten; Insbesondere MultiMaps lindern den Schmerz von etwas, das man sich selbst sehr oft implementiert.
Calum
19
@skaffman: Er ist eigentlich kein Idiot, aber manchmal macht er Bewegungen, die ... na ja, seltsam sind. Wie auch immer, ich werde keine Fehler in das Produkt einführen. Auf dem heutigen Markt bin ich mit meiner Arbeit zufrieden und möchte keine Türen zuschlagen und Brücken verbrennen, wenn Sie meinen Standpunkt verstehen.
Yuval
3
Ich bin ziemlich überrascht, wenn SetUniqueList keinen parametrisierten Typ hat.
Smaragdhieu
2
Jeffrey: Auf mobilen Plattformen entfernt das System normalerweise nicht verwendete Klassen, aber es gibt viele Gründe, warum Sie möglicherweise nicht auf eine dieser "normalen" Lösungen verzichten. Es muss immer ein Kompromiss geschlossen werden, und keine Lösung wird alle Fälle beheben.
Calum
14

Hier ist was ich getan habe und es funktioniert.

Angenommen, ich muss ArrayListmit dem ersten arbeiten, was ich getan habe, ist ein neues erstellt LinkedHashMap.

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

Dann versuche ich mein neues Element zum hinzuzufügen LinkedHashSet. Die add-Methode ändert das nicht LinkedHasSetund gibt false zurück, wenn das neue Element ein Duplikat ist. Dies wird also zu einer Bedingung, die ich testen kann, bevor ich sie hinzufüge ArrayList.

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

Dies ist eine einfache und elegante Methode, um zu verhindern, dass Duplikate zu einer Array-Liste hinzugefügt werden. Wenn Sie möchten, können Sie es in die add-Methode in einer Klasse einkapseln und überschreiben, die das erweitert ArrayList. Denken Sie daran, addAlldie Elemente zu durchlaufen und die add-Methode aufzurufen.

user3570018
quelle
1
Ja, ich denke, dies ist die beste Lösung dafür. Sie können auch einfach ein normales HashSet verwenden, kein verknüpftes, und dann können Sie Ihre Liste verwenden, wie Sie möchten. Sie können auch entscheiden, was in bestimmten Situationen zu tun ist, z Wenn Sie ein Element in einer Liste vor einem bestimmten Index hinzufügen, können Sie festlegen, ob Sie das duplizierte Element an diese Position verschieben möchten oder nicht.
Gyurix
Beste Lösung hier ... Wird meinen UniqueList-Klassencode veröffentlichen
marcolopes
Dies funktionierte bei mir in meinem BFS-Graph-Algorithmus. Weil ich einige Knoten hatte, die ich einer Warteschlange (LinkedList) hinzugefügt habe, nur wenn sie nicht bereits vorhanden waren.
Jeancarlo Fontalvo
11

Also hier ist, was ich schließlich getan habe. Ich hoffe das hilft jemand anderem.

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);
        }
    }
}   
Yuval
quelle
10
Seien Sie vorsichtig - LinkedList.contains () muss die gesamte Liste scannen, um festzustellen, ob ein Objekt in der Liste enthalten ist. Dies bedeutet, dass beim Hinzufügen von Objekten zu einer großen Liste die gesamte Liste für jeden Hinzufügenvorgang gescannt wird (im schlimmsten Fall). Dies kann langsam werden.
Matt B
8
Außerdem sucht Ihre addAll-Überschreibung nicht nach Duplikaten in der Sammlung, die an addAll () übergeben wird.
Matt B
@mattb Wie würden Sie dieses Problem dann lösen: Unter Android erhalten wir beim Binden von Objekten an eine Listenelementansicht die Position des Elements im Ansichtsadapter. Da Mengen keinen Index haben, besteht die einzige Möglichkeit zu überprüfen, ob das Objekt bei Verwendung von Listen vorhanden ist oder nicht, darin, eine vorhandene Kopie zu durchlaufen und nach ihr zu suchen.
TheRealChx101
6

Warum kapseln Sie ein Set nicht mit einer Liste? Sortieren Sie wie folgt:

new ArrayList( new LinkedHashSet() )

Damit bleibt die andere Implementierung für jemanden, der ein echter Meister der Sammlungen ist ;-)

Daniel Hiller
quelle
3
Dieser Konstruktor kopiert den Inhalt des Sets in die neue Liste, anstatt ihn zu verpacken.
Calum
@Calum, das ist richtig, aber anstatt sich Gedanken darüber zu machen, dass keine Duplikate zu einer Liste hinzugefügt werden, kann er seine Objekte zu einem Set hinzufügen (und das Set sich Gedanken über das Herausfiltern von Duplikaten machen lassen) und dieses Set einfach in eine Liste einschließen, wenn es an übergeben wird die externe Methode.
Matt B
4
Dadurch wird ein Satz in eine Liste kopiert, Sie haben jedoch keine bekannte Reihenfolge. Aber darum geht es in der Frage.
Janning
4

Sie sollten ernsthaft über Dhillers Antwort nachdenken:

  1. Anstatt sich Gedanken über das Hinzufügen Ihrer Objekte zu einer Liste ohne Duplikate zu machen, fügen Sie sie einem Set (einer beliebigen Implementierung) hinzu, wodurch die Duplikate von Natur aus herausgefiltert werden.
  2. Wenn Sie die Methode aufrufen müssen, für die eine Liste erforderlich ist, schließen Sie sie in eine new ArrayList(set)(oder eine new LinkedList(set), was auch immer) ein.

Ich denke, dass die Lösung, die Sie mit veröffentlicht NoDuplicatesListhaben, einige Probleme hat, hauptsächlich mit der contains()Methode, und dass Ihre Klasse nicht nach Duplikaten in der Sammlung sucht, die an Ihre addAll()Methode übergeben wurde.

matt b
quelle
Ich würde gerne davon erfahren, enthält () Probleme. Für addAll () erstelle ich eine Kopie der angegebenen Sammlung und entferne alle Objekte, die sich bereits in 'this' befinden. Wie geht das nicht mit Duplikaten um?
Yuval
Wie ich in meinem Kommentar zu Ihrem Klassenbeitrag erwähnt habe, muss includes () die gesamte Liste (im schlimmsten Fall) scannen, um festzustellen, ob das Objekt in der Liste enthalten ist. Wenn Sie eine Liste mit 1 Million Elementen haben und 10 einzeln hinzufügen, werden (im schlimmsten Fall) über zehn Millionen Elemente gescannt.
Matt B
Wenn bei addAll () die an addAll übergebene Sammlung selbst Duplikate enthält, werden diese nicht erkannt. Zum Beispiel: Ihre Liste {A, B, C, D} Parameterliste {B, D, E, E, E}. Sie erstellen eine Kopie des Parameters und nach removeAll enthält er {E, E, E}.
Matt B
Das Problem mit addAll () ist für mich nicht wirklich relevant, da ich NoDuplicatesList während der gesamten Prozedur verwende und addAll () eine andere NoDuplicatesList als Parameter erhalten sollte. Was würden Sie vorschlagen, um die Leistung von includes () zu verbessern?
Yuval
3

Ich brauchte so etwas, also ging ich zu den Commons-Sammlungen und benutzte die SetUniqueList, aber als ich einen Leistungstest durchführte, stellte ich fest, dass es im Vergleich zum Fall nicht optimiert zu sein scheint, wenn ich eine verwenden Setund eine Arraymit der Set.toArray()Methode erhalten möchte .

Das Ausfüllen und anschließende Durchlaufen von 100.000 Strings im Vergleich zur anderen Implementierung SetUniqueTestdauerte 20: 1 , was einen großen Unterschied darstellt.

Wenn Sie sich also Gedanken über die Leistung machen, empfehle ich Ihnen, Set and Get a Array anstelle von zu verwenden SetUniqueList, es sei denn, Sie benötigen wirklich die Logik von SetUniqueList, dann müssen Sie andere Lösungen überprüfen ...

Hauptmethode zum Testen des Codes :

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

}}

Grüße, Mohammed Sleem

Große Tour
quelle
1

HINWEIS: Die Implementierung der Unterliste wird nicht berücksichtigt.

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));
    }

}
marcolopes
quelle
0

Die Dokumentation für Sammlungsschnittstellen lautet:

Set - eine Sammlung, die keine doppelten Elemente enthalten darf.
Liste - eine geordnete Sammlung (manchmal auch als Sequenz bezeichnet). Listen können doppelte Elemente enthalten.

Wenn Sie also keine Duplikate möchten, sollten Sie wahrscheinlich keine Liste verwenden.

Hauch
quelle
Ich habe ausdrücklich erwähnt, dass ich eine List-Implementierung benötige. Vertrau mir, es gibt einen Grund.
Yuval
Liegt der Grund darin, dass Sie mit einer API interagieren, die eine Liste als Parameter verwendet (anstelle einer Sammlung)? Es ist ein bisschen ärgerlich, sich damit auseinandersetzen zu müssen
matt b
Tatsächlich verwendet die API eine Map <AccountType, Map <AccountType, List <Account> >>, was bedeutet, dass sie sich in der Nähe von Dutzenden bis Hunderten von Listen befindet ... bah.
Yuval
Das Konstruieren von Wahrscheinlichkeitsfunktionen mit Element-Wahrscheinlichkeits-Paaren kann beinhalten, dass keine Duplikate vorhanden sind, obwohl doppelte Elemente einfach zusammengeführt werden könnten.
Al G Johnston
-1

in der addMethode, warum nicht verwenden HashSet.add(), um Duplikate anstelle von zu überprüfen HashSet.consist(). HashSet.add()wird zurückgegeben, truewenn kein Duplikat und falsesonst.

neoreeprast
quelle
Was ist HashSet#consist()?
NaXa
-1

Listen erlauben Duplikate. Sie können a schnell implementieren UniqueArrayListund alle zu überprüfenden add/ insertFunktionen überschreiben, contains()bevor Sie die geerbten Methoden aufrufen. Für den persönlichen Gebrauch können Sie die von addIhnen verwendete Methode nur implementieren und die anderen überschreiben, um eine Ausnahme auszulösen, falls zukünftige Programmierer versuchen, die Liste auf andere Weise zu verwenden.

Kieveli
quelle
Ich war bereit, auf diese Idee zurückzugreifen (was ich schließlich tun musste), wenn niemand etwas Besseres vorschlug = 8-) Siehe meine eigene Antwort oben.
Yuval
-3

Ich habe gerade meine eigene UniqueList in meiner eigenen kleinen Bibliothek erstellt:

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;
    }
}

Ich habe eine TestCollections-Klasse, die so aussieht:

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);
    }
}

Funktioniert gut. Alles, was es tut, ist, es zu einem Set hinzuzufügen, wenn es es noch nicht hat und es eine Arraylist gibt, die zurückgegeben werden kann, sowie ein Objektarray.

Jonathan
quelle
Ja, Sie sollten ein bisschen mehr Methoden hinzufügen, um die List-Schnittstelle zu implementieren.
Gyurix