如何过滤2个包含数百万个相同id项目的巨大列表[重复]

Question

这是我的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应该更好。请建议我有什么改进之处。

Answer 1

您可以先尝试将其转换为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()返回散列集。您可以将代码简化为：

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

首先将ID添加到hashset中作为中间步骤，将为您提供更好的总体复杂性时间，因为（源代码）：

HashSet操作的时间复杂性：HashSet的底层数据结构是Hashtable。因此，对哈希集的add、remove和look-up（contains method）操作的摊销（平均或通常情况）时间复杂度需要O（1）次。

因此，“hashmap”解决方案的总体时间复杂性将为O(N+M)，其中N和M分别从列表ArchivedTransactions和FoundTransactions中的元素数开始。尽管如此，space-wise您将为拥有这种额外的结构付出代价。

您的解决方案space-wise更好，但时间复杂度最差。如果N=m则解决方案的时间复杂度为O(N^2)，而具有哈希集的解决方案将为O(2N)，因此为O(N)。这是一个巨大的差异。

做的只是

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

光靠自己是不行的，因为你明确要求：

!tx.getId().equalsIgnoreCase(aTx.getId())