同じIDを持つ何百万ものアイテムを含む2つの巨大なリストをフィルタリングする方法[重複]
これが数百万以上のアイテムを含む私の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の方が良いと思います。改善点を教えてください。
回答
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())
私の頭に浮かぶ最も簡単な解決策は、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
。