java - 如何过滤 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() 返回一个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 作为中间步骤，这将为您提供更好的整体复杂性时间，因为 (source):

Time Complexity of HashSet Operations: The underlying data structure for HashSet is hashtable. So amortize (average or usual case) time complexity for add, remove and look-up (contains method) operation of HashSet takes O(1) time.

因此，"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())