时间戳

首页 > 解决方案 > 如何使用流代替循环并从中受益

java - 如何使用流代替循环并从中受益

问题描述

我有两个对象数组data1和data2. 我使用 for 循环过滤我的数据，如下所示：

for (int i = 0; i < data1.size(); i++) {

            for (int j = 0; j < data2.size(); j++) {

                if (data1.get(i).getId().equals(data2.get(j).getID())) {

                    data1.get(i).setHome(data2.get(j).getHome());

                }

            }

        }

Everting 工作得很好，但我想优化我想使用streamfor 循环的代码。

标签： javajava-stream

解决方案

我想优化代码。我想使用流而不是 for 循环。

这两件事不一定相同。

  • 在这种情况下，简单的嵌套循环可能比使用流的直接等效公式更快、更有效。

  • 如果您parallel在流公式中使用，流公式可能会更快，但不会更有效。（与非并行情况相比，每完成一个工作单元您将使用更多的 CPU 周期。）

让我们退后一步，看看实际的算法：

  • 您当前的算法是将一个列表的每个元素与另一个列表的每个元素进行比较。这就是复杂性O(MN)，其中 M 和 N 是列表大小。

  • 对于流（非并行），复杂性是相同的。

  • 使用流和并行性，可能会有一个P加速因素，即P物理处理器的数量。但这假设：

    1. 处理器在P处理过程中都可用和使用，
    2. 列表大小足够大，以至于并行化的开销（例如，对列表进行分区）是微不足道的，并且
    3. 没有令人困惑的二阶效应，例如内存总线争用或垃圾收集。

  • 如果我们假设列表中对象的 id 是唯一的，那么您可以break在获得匹配项时跳出内部循环。这大致表明性能提高了 2 倍。

  • Map我们可以使用从列表之一构建的 E 元素的(TreeMap orHashMap`) 查找替换内部循环。

    • 有了 a TreeMap，查找O(log E)的复杂度是 ，构建地图的复杂度是O(ElogE)。总体复杂度将是“O(N'logM')”，其中 N' 是 M 和 N 中的较大者，而 M' 是较小的。
    • 有了 a HashMap，查找O(1)的复杂度是 ，构建地图的复杂度是O(E)。总体复杂性将是O(N')其中 N' 是 M 和 N 中的较大者。
    • 对于足够大的 M 和 N，使用映射会更有效。
    • 如果您可以用地图完全替换其中一个列表，那么您可以避免“每次”运行代码时都必须重新构建地图。
    • 然而，两者都需要O(M')额外的空间来表示地图。

  • 使用 Map 的替代方法是对两个列表进行就地排序，以使它们按 id 顺序排列。然后，您使用合并算法遍历这两个列表，并在条目匹配时进行所需的更改。这具有大致O(N'logN')复杂性，其中 N' 是 M 和 N 中的较大者，并且它不使用额外的空间。（假设排序是真正就地的。）但这也更复杂。

所以这是我基于上述的优化：

// This assumes `list2` is the smaller of the lists.  If you don't know
// which one is likely to be smaller, you may need two versions of the code.

Map<Id, Record> map = new HashMap<>();
for (Record record: list2) {
    map.put(record.getId(), record);
}

for (Record record: list1) {
    Record record2 = map.get(record.getId());
    if (record2 != null) {
        record.setHome(record2.getHome());
    }
}

推荐阅读