Apakah tidak ada penerapan Daftar duplikat di luar sana?

87

Saya tahu tentang SortedSet, tetapi dalam kasus saya, saya membutuhkan sesuatu yang mengimplementasikan List, dan tidak Set. Jadi apakah ada implementasi di luar sana, di API atau di tempat lain?

Seharusnya tidak sulit untuk menerapkan diri saya sendiri, tetapi saya pikir mengapa tidak bertanya kepada orang-orang di sini dulu?

Yuval
sumber
1
Mengapa perlu mengimplementasikan List? Set dapat diulang, seperti daftar, jadi saya kira metode penerimaan menerapkan Daftar karena beberapa alasan lain.
Rob
@Rob Benar, ini adalah permintaan eksternal, dan struktur datanya mencakup lebih dari satu Daftar.
Yuval
Jika pengguna menginginkan DAFTAR, maka jelas bahwa membutuhkan metode antarmuka LIST yang tidak ada pada antarmuka SET ...
marcolopes

Jawaban:

94

Tidak ada koleksi Java di pustaka standar untuk melakukan ini. LinkedHashSet<E>mempertahankan pengurutan mirip dengan a List, jadi jika Anda membungkus set Anda di Listsaat Anda ingin menggunakannya sebagai, ListAnda akan mendapatkan semantik yang Anda inginkan.

Atau, Koleksi Commons (atau commons-collections4, untuk versi generik) memiliki Listmana yang sudah melakukan apa yang Anda inginkan: SetUniqueList/ SetUniqueList<E>.

Calum
sumber
5
Kelas Commons persis seperti yang saya butuhkan, tetapi bos saya menyuruh saya untuk menerapkannya sendiri pada akhirnya. 10x pula!
Yuval
5
Ah, tidak ada yang seperti menemukan kembali roda! Anda akan tahu sekarang jika kebutuhan itu muncul lagi. collections15 adalah hal yang cukup berguna untuk dinikmati; MultiMaps secara khusus meringankan rasa sakit dari sesuatu yang akhirnya sering diimplementasikan sendiri.
Calum
19
@skaffman: dia sebenarnya bukan idiot, tapi terkadang dia membuat gerakan yang ... yah, aneh. Bagaimanapun, saya tidak akan memasukkan bug ke dalam produk. Di pasar saat ini, saya senang dengan pekerjaan saya dan tidak ingin membanting pintu dan membakar jembatan, jika Anda mengerti maksud saya.
Yuval
3
Saya cukup terkejut ketika SetUniqueList tidak memiliki tipe berparameter.
emeraldhieu
2
Jeffrey: Pada platform seluler, sistem biasanya akan menghapus kelas yang tidak digunakan, tetapi tentu saja, ada banyak alasan mengapa Anda tidak dapat menggunakan salah satu solusi "normal" ini. Selalu ada pertukaran yang harus dilakukan, dan tidak ada solusi yang akan memperbaiki semua kasus.
Calum
14

Inilah yang saya lakukan dan berhasil.

Dengan asumsi saya harus ArrayListbekerja dengan hal pertama yang saya lakukan adalah membuat yang baru LinkedHashMap.

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

Kemudian saya mencoba menambahkan elemen baru saya ke LinkedHashSet. Metode add tidak mengubah LinkedHasSetdan mengembalikan false jika elemen baru adalah duplikat. Jadi ini menjadi kondisi yang bisa saya uji sebelum menambahkan ArrayList.

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

Ini adalah cara sederhana dan elegan untuk mencegah duplikat ditambahkan ke daftar array. Jika mau, Anda bisa merangkumnya dan mengganti metode add dalam kelas yang memperluas ekstensi ArrayList. Ingatlah untuk menangani dengan addAllmengulang melalui elemen dan memanggil metode add.

pengguna3570018
sumber
1
Ya, menurut saya, ini adalah solusi terbaik untuk itu, Anda juga dapat menggunakan HashSet biasa, bukan Linked, dan kemudian Anda dapat menggunakan daftar Anda sesuai keinginan, Anda juga dapat memutuskan apa yang harus dilakukan dalam beberapa situasi, seperti di menambahkan elemen di dalam daftar sebelum indeks tertentu, Anda dapat memutuskan bahwa Anda ingin memindahkan item duplikat ke posisi ini atau tidak.
gyurix
Solusi terbaik di sini ... Akan posting kode kelas UniqueList saya
marcolopes
Ini berhasil untuk saya, dalam algoritma Grafik BFS saya. Karena saya memiliki beberapa node yang saya tambahkan ke Queue (LinkedList) hanya jika mereka belum masuk.
Jeancarlo Fontalvo
11

Jadi, inilah yang akhirnya saya lakukan. Saya harap ini membantu orang lain.

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
sumber
10
Hati-hati - LinkedList.contains () perlu memindai seluruh daftar untuk menentukan apakah suatu objek terdapat dalam Daftar. Ini berarti bahwa ketika Anda menambahkan objek ke Daftar yang besar, seluruh Daftar dipindai untuk setiap operasi penambahan (dalam kasus terburuk). Ini bisa menjadi LAMBAT.
matt b
8
Selain itu, addAll override Anda tidak memeriksa duplikat dalam koleksi yang diteruskan ke addAll ().
matt b
@mattb Bagaimana Anda memecahkan masalah ini kemudian: Di Android, saat mengikat objek ke tampilan item daftar, kita diberi posisi item dalam adaptor tampilan. Karena set tidak memiliki indeks, satu-satunya cara adalah memeriksa apakah objek ada atau tidak saat menggunakan daftar adalah dengan mengulang dan mencari salinan yang sudah ada.
TheRealChx101
6

Mengapa tidak merangkum satu set dengan daftar, urutkan seperti:

new ArrayList( new LinkedHashSet() )

Ini meninggalkan implementasi lain untuk seseorang yang merupakan master Koleksi yang sebenarnya ;-)

Daniel Hiller
sumber
4
Konstruktor ini menyalin konten Set ke dalam Daftar baru, bukan membungkusnya.
Calum
@Calum, itu benar, tetapi alih-alih khawatir tentang tidak menambahkan duplikat ke Daftar, dia dapat menambahkan objeknya ke Set (dan membiarkan Set khawatir tentang menyaring duplikat) dan hanya membungkus Set itu dalam Daftar saat meneruskannya ke metode eksternal.
matt b
4
Ini menyalin satu set ke daftar tetapi Anda tidak memiliki urutan terkenal. Tapi inilah pertanyaannya.
Janning
4

Anda harus secara serius mempertimbangkan jawaban dhiller:

  1. Alih-alih khawatir tentang menambahkan objek Anda ke Daftar tanpa duplikat, tambahkan objek tersebut ke Set (implementasi apa pun), yang secara alami akan menyaring duplikat.
  2. Saat Anda perlu memanggil metode yang membutuhkan List, bungkus dengan a new ArrayList(set)(atau a new LinkedList(set), apa saja).

Saya pikir solusi yang Anda posting dengan NoDuplicatesListmemiliki beberapa masalah, sebagian besar dengan contains()metode, ditambah kelas Anda tidak menangani pemeriksaan duplikat dalam Collection yang diteruskan ke addAll()metode Anda .

matt b
sumber
Saya ingin mempelajari masalah berisi () ini. Adapun addAll (), saya membuat salinan dari koleksi yang diberikan dan menghapus semua objek yang sudah ada di 'ini'. Bagaimana itu tidak menangani duplikat?
Yuval
Seperti yang saya sebutkan dalam komentar saya untuk posting kelas Anda, berisi () harus memindai seluruh daftar (dalam kasus terburuk) untuk menemukan apakah objek tersebut terdapat dalam daftar. Jika Anda memiliki daftar 1 juta item dan menambahkan 10 item satu per satu, maka (dalam kasus terburuk) lebih dari sepuluh juta item dipindai.
matt b
Adapun addAll (), jika Collection diteruskan ke addAll berisi duplikatnya sendiri, mereka tidak terdeteksi. Misalnya: daftar parameter {A, B, C, D} Anda {B, D, E, E, E}. Anda membuat salinan parameter, dan setelah removeAll berisi {E, E, E}.
matt b
Masalah addAll () tidak terlalu relevan bagi saya, karena saya menggunakan NoDuplicatesList di seluruh prosedur, dan addAll () harus menerima NoDuplicatesList lain sebagai parameternya. Apa yang akan Anda sarankan untuk meningkatkan kinerja berisi ()?
Yuval
3

Saya membutuhkan sesuatu seperti itu, jadi saya pergi ke koleksi commons dan menggunakan SetUniqueList, tetapi ketika saya menjalankan beberapa tes kinerja, saya menemukan bahwa tampaknya tidak dioptimalkan dibandingkan dengan kasus jika saya ingin menggunakan Setdan mendapatkan Arraymenggunakan Set.toArray()metode tersebut.

Diperlukan SetUniqueTestwaktu 20: 1 untuk mengisi dan kemudian melintasi 100.000 String dibandingkan dengan implementasi lainnya, yang merupakan perbedaan besar.

Jadi, jika Anda khawatir tentang kinerjanya, saya sarankan Anda untuk menggunakan Set dan Dapatkan Array daripada menggunakan SetUniqueList, kecuali jika Anda benar-benar membutuhkan logika SetUniqueList, maka Anda harus memeriksa solusi lain ...

Menguji metode utama kode :

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

}

Hormat kami, Mohammed Sleem

Grandtour
sumber
1

CATATAN: ini tidak memperhitungkan implementasi 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));
    }

}
marcolopes
sumber
0

The dokumentasi untuk antarmuka koleksi mengatakan:

Set - koleksi yang tidak dapat berisi elemen duplikat.
Daftar - koleksi yang dipesan (terkadang disebut urutan). Daftar dapat berisi elemen duplikat.

Jadi, jika Anda tidak ingin duplikat, Anda mungkin tidak boleh menggunakan daftar.

Hauch
sumber
Saya secara khusus menyebutkan bahwa saya memerlukan implementasi Daftar. Percayalah, ada alasannya.
Yuval
Apakah alasannya karena Anda berinteraksi dengan API yang menggunakan List sebagai parameter (bukan Collection)? Agak menjengkelkan harus berurusan dengan
matt b
Sebenarnya API menggunakan Map <AccountType, Map <AccountType, List <Account> >>, yang berarti memegang suatu tempat di sekitar lusinan hingga ratusan daftar ... bah.
Yuval
Membangun fungsi probabilitas dengan pasangan elemen-probabilitas dapat melibatkan tidak memiliki duplikat, meskipun elemen duplikat hanya dapat digabungkan.
Al G Johnston
-1

Dalam addmetode, mengapa tidak menggunakan HashSet.add()untuk memeriksa duplikat, bukan HashSet.consist(). HashSet.add()akan kembali truejika tidak ada duplikat dan falsesebaliknya.

lebih kontras
sumber
Apa HashSet#consist()?
naXa
-1

Di luar kepala saya, daftar memungkinkan duplikat. Anda dapat dengan cepat mengimplementasikan UniqueArrayListdan mengganti semua add/ insertfunctions yang akan diperiksa contains()sebelum Anda memanggil metode yang diwariskan. Untuk penggunaan pribadi, Anda hanya dapat mengimplementasikan addmetode yang Anda gunakan, dan menimpa yang lain untuk memberikan pengecualian jika programmer masa depan mencoba menggunakan daftar dengan cara yang berbeda.

Kieveli
sumber
Saya siap untuk kembali ke ide ini (yang akhirnya harus saya lakukan) jika tidak ada yang menyarankan sesuatu yang lebih baik = 8-) Lihat jawaban saya sendiri di atas.
Yuval
-3

Saya baru saja membuat UniqueList saya sendiri di perpustakaan kecil saya sendiri seperti ini:

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

Saya memiliki kelas TestCollections yang terlihat seperti ini:

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

Bekerja dengan baik. Yang dilakukannya hanyalah menambahkan ke set jika belum memilikinya dan ada Arraylist yang dapat dikembalikan, serta array objek.

Jonathan
sumber
Ya, Anda harus menambahkan lebih banyak metode untuk itu untuk mengimplementasikan antarmuka Daftar.
gyurix