Bagaimana cara memfilter 2 list besar dengan jutaan item didalamnya dengan id yang sama [duplikat]
Berikut adalah 2 daftar saya dengan lebih dari jutaan item. Keduanya memiliki item yang sama dengan ID yang sama. ID ada dalam String. Saya hanya membutuhkan barang yang tidak sama ID. Saya melakukan ini. Tapi saya yakin pasti ada solusi yang lebih baik dan dengan ketetapan yang tinggi: -
List<Transaction> differentList = new ArrayList<>();
for(Transaction tx : foundTransactions ){
for(Transaction aTx : ArchivedTransactions)
{
if(!tx.getId().equalsIgnoreCase(aTx.getId()) ){
differentList .add(tx);
}
}
}
Saya mencoba menggunakan streaming tetapi saya tidak bisa melakukannya. Saya kira dengan API streaming seharusnya lebih baik. Tolong sarankan saya perbaikan apa pun.
Jawaban
Anda dapat mencoba mengubahnya menjadi yang HashMap
pertama, seperti:
Set<String> collect = ArchivedTransactions.stream().map(i -> i.getId().toLowerCase())
.collect(Collectors.toSet());
for(Transaction tx : foundTransactions )
if(!collect.contains(tx.getId()))
differentList.add(tx);
Hasil Collectors.toSet()
a HashSet
. Anda dapat menyederhanakan kode menjadi:
Set<String> collect = ArchivedTransactions.stream().map(i -> i.getId().toLowerCase())
.collect(Collectors.toSet());
List<Transaction> differentList = foundTransactions.stream()
.filter(tx -> !collect.contains(tx.getId()))
.collect(Collectors.toList())
Menambahkan yang IDs
pertama ke dalam HashSet
sebagai langkah perantara akan memberi Anda waktu kompleksitas keseluruhan yang jauh lebih baik karena ( sumber ):
Kompleksitas Waktu Operasi HashSet: Struktur data yang mendasari HashSet adalah hashtable. Jadi amortisasi (rata-rata atau kasus biasa) kompleksitas waktu untuk menambah , menghapus dan mencari (berisi metode) operasi HashSet membutuhkan O (1) waktu.
Akibatnya, keseluruhan time complexity
dari "HashMap"
solusi akan O(N + M)
, di mana N
dan M
mulai jumlah elemen dalam daftar ArchivedTransactions
dan foundTransactions
masing-masing. Meskipun demikian, space-wise
Anda akan membayar harga untuk memiliki struktur ekstra itu.
Solusi Anda space-wise
lebih baik, tetapi dengan kerumitan waktu terburuk. Jika N = M
kompleksitas waktu solusi Anda adalah O(N^2)
, sedangkan solusi dengan HashSet
jadinya O(2N)
, maka O(N)
. Ini adalah perbedaan yang sangat besar.
Melakukan yang adil
Set<Transaction> result = new LinkedHashSet<>();
result.addAll(foundTransactions);
result.addAll(ArchivedTransactions);
saja tidak akan berfungsi, karena Anda secara eksplisit meminta:
!tx.getId().equalsIgnoreCase(aTx.getId())
Solusi paling sederhana yang muncul di benak saya adalah dengan menggunakan Setyang secara otomatis membuang elemen duplikat.
Set<Transaction> result = new LinkedHashSet<>();
result.addAll(foundTransactions);
result.addAll(ArchivedTransactions);
//If you want to get a List<Transaction>
List<Transaction> differentList = new ArrayList<>(result);
Catatan: Saya telah terbiasa LinkedHashSet
mempertahankan urutan penyisipan. Jika urutan penyisipan tidak penting bagi Anda, Anda dapat menggunakan HashSet
.