同じIDを持つ何百万ものアイテムを含む2つの巨大なリストをフィルタリングする方法[重複]

Dec 04 2020

これが数百万以上のアイテムを含む私の2つのリストです。どちらも同じIDの同じアイテムを持っています。IDは文字列です。同じIDではないアイテムだけが必要です。こうしました。しかし、私はより良い解決策と高い永続性がなければならないと確信しています:-

    List<Transaction> differentList = new ArrayList<>();

    for(Transaction tx : foundTransactions ){
        for(Transaction aTx : ArchivedTransactions) 
        {
            if(!tx.getId().equalsIgnoreCase(aTx.getId()) ){
                differentList .add(tx);
            }
        }
    }

ストリームを使おうとしましたが、できませんでした。ストリームAPIの方が良いと思います。改善点を教えてください。

回答

4 dreamcrash Dec 04 2020 at 19:34

HashMap次のような最初の変換を試すことができます。

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

はをCollectors.toSet()返しますHashSet。コードを次のように簡略化できます。

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())

IDs最初のHashSetステップを中間ステップとしてに追加すると、(ソース)以降、全体的な複雑さが大幅に改善されます。

HashSet操作の時間計算量:HashSetの基礎となるデータ構造はハッシュテーブルです。したがって、HashSetの追加、削除、およびルックアップ(メソッドを含む)操作の時間計算量(平均または通常の場合)を償却するにはO(1)時間がかかります。

その結果、全体time complexity"HashMap"溶液になりますO(N + M)。ここで、NおよびMリスト内の要素の数を開始ArchivedTransactionsし、foundTransactionsそれぞれ、。それにもかかわらず、space-wiseあなたはその余分な構造を持つことの代償を払うでしょう。

あなたのソリューションspace-wiseはより良いですが、最悪の時間計算量を伴います。場合はN = M、ソリューションの時間の複雑さがあるO(N^2)とソリューションのに対し、HashSetでしょうO(2N)、したがって、O(N)。これは大きな違いです。

ただやって

Set<Transaction> result = new LinkedHashSet<>();
result.addAll(foundTransactions);
result.addAll(ArchivedTransactions);

明示的に要求したため、単独では機能しません。

!tx.getId().equalsIgnoreCase(aTx.getId())
3 LiveandLetLive Dec 04 2020 at 19:33

私の頭に浮かぶ最も簡単な解決策は、Set重複する要素を自動的に破棄するを使用することです。

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

注:私はLinkedHashSet挿入順序を保持するために使用しました。挿入順序が重要でない場合は、を使用できますHashSet