Java 8 Stream 混合两个元素

问题描述 投票：0回答：7

我在数组列表中有许多 Slot 类型的对象。

Slot 类如下图-

Slot{
   int start;
   int end;
}

令类型为

List<Slot>
的列表称为
slots
。时段根据开始时间排序。一个时隙的结束时间可能等于下一时隙的开始时间，但它们永远不会重叠。

是否有任何可能的方法可以使用 Java 8 流迭代此列表，如果一个槽的结束时间与下一个槽的开始时间匹配，则组合两个槽并将它们输出到

ArrayList
？

java java-8 java-stream
7个回答
5
投票

我的免费 StreamEx 库完美支持这种场景，该库增强了标准 Stream API。有一个 

intervalMap
中间操作能够将多个相邻的流元素折叠为单个元素。这是完整的示例：

// Slot class and sample data are taken from @Andreas answer
List<Slot> slots = Arrays.asList(new Slot(3, 5), new Slot(5, 7), 
                new Slot(8, 10), new Slot(10, 11), new Slot(11, 13));

List<Slot> result = StreamEx.of(slots)
        .intervalMap((s1, s2) -> s1.end == s2.start,
                     (s1, s2) -> new Slot(s1.start, s2.end))
        .toList();
System.out.println(result);
// Output: [3-7, 8-13]


intervalMap
方法有两个参数。第一个是 
BiPredicate
接受来自输入流的两个相邻元素，如果必须合并它们则返回 true（这里的条件是 
s1.end == s2.start
）。第二个参数是 
BiFunction
，它从合并的序列中获取第一个和最后一个元素并生成结果元素。

请注意，例如，如果您有 100 个相邻槽位应合并为一个，则此解决方案不会创建 100 个中间对象（如 @Misha 的答案，但这非常有趣），它会跟踪该系列中的第一个和最后一个槽位立即忘记中间一次。当然这个解决方案是并行友好的。如果您有数千个输入槽，使用 

.parallel()
可能会提高性能。

请注意，当前的实现将重新创建 

Slot
，即使它没有与任何内容合并。在这种情况下， 
BinaryOperator
会两次接收相同的 
Slot
参数。如果你想优化这种情况，你可以进行额外的检查，如
s1 == s2 ? s1 : ...
:

List<Slot> result = StreamEx.of(slots)
        .intervalMap((s1, s2) -> s1.end == s2.start,
                     (s1, s2) -> s1 == s2 ? s1 : new Slot(s1.start, s2.end))
        .toList();
5
投票

由于这类问题经常出现，我认为编写一个通过谓词对相邻元素进行分组的收集器可能是一个有趣的练习。

假设我们可以向 

Slot
类添加组合逻辑

boolean canCombine(Slot other) {
    return this.end == other.start;
}

Slot combine(Slot other) {
    if (!canCombine(other)) {
        throw new IllegalArgumentException();
    }
    return new Slot(this.start, other.end);
}


groupingAdjacent
收集器可以按如下方式使用：

List<Slot> combined = slots.stream()
    .collect(groupingAdjacent(
        Slot::canCombine,         // test to determine if two adjacent elements go together
        reducing(Slot::combine),  // collector to use for combining the adjacent elements
        mapping(Optional::get, toList())  // collector to group up combined elements
    ));

或者，第二个参数可以是 

collectingAndThen(reducing(Slot::combine), Optional::get)
，第三个参数可以是 
toList()

这是

groupingAdjacent
的来源。它可以处理 
null
元素并且是并行友好的。稍微麻烦一点，可以用 
Spliterator
来完成类似的事情。

public static <T, AI, I, AO, R> Collector<T, ?, R> groupingAdjacent(
        BiPredicate<? super T, ? super T> keepTogether,
        Collector<? super T, AI, ? extends I> inner,
        Collector<I, AO, R> outer
) {
    AI EMPTY = (AI) new Object();

    // Container to accumulate adjacent possibly null elements.  Adj can be in one of 3 states:
    // - Before first element: curGrp == EMPTY
    // - After first element but before first group boundary: firstGrp == EMPTY, curGrp != EMPTY
    // - After at least one group boundary: firstGrp != EMPTY, curGrp != EMPTY
    class Adj {

        T first, last;     // first and last elements added to this container
        AI firstGrp = EMPTY, curGrp = EMPTY;
        AO acc = outer.supplier().get();  // accumlator for completed groups

        void add(T t) {
            if (curGrp == EMPTY) /* first element */ {
                first = t;
                curGrp = inner.supplier().get();
            } else if (!keepTogether.test(last, t)) /* group boundary */ {
                addGroup(curGrp);
                curGrp = inner.supplier().get();
            }
            inner.accumulator().accept(curGrp, last = t);
        }

        void addGroup(AI group) /* group can be EMPTY, in which case this should do nothing */ {
            if (firstGrp == EMPTY) {
                firstGrp = group;
            } else if (group != EMPTY) {
                outer.accumulator().accept(acc, inner.finisher().apply(group));
            }
        }

        Adj merge(Adj other) {
            if (other.curGrp == EMPTY) /* other is empty */ {
                return this;
            } else if (this.curGrp == EMPTY) /* this is empty */ {
                return other;
            } else if (!keepTogether.test(last, other.first)) /* boundary between this and other*/ {
                addGroup(this.curGrp);
                addGroup(other.firstGrp);
            } else if (other.firstGrp == EMPTY) /* other container is single-group. prepend this.curGrp to other.curGrp*/ {
                other.curGrp = inner.combiner().apply(this.curGrp, other.curGrp);
            } else /* other Adj contains a boundary.  this.curGrp+other.firstGrp form a complete group. */ {
                addGroup(inner.combiner().apply(this.curGrp, other.firstGrp));
            }
            this.acc = outer.combiner().apply(this.acc, other.acc);
            this.curGrp = other.curGrp;
            this.last = other.last;
            return this;
        }

        R finish() {
            AO combined = outer.supplier().get();
            if (curGrp != EMPTY) {
                addGroup(curGrp);
                assert firstGrp != EMPTY;
                outer.accumulator().accept(combined, inner.finisher().apply(firstGrp));
            }
            return outer.finisher().apply(outer.combiner().apply(combined, acc));
        }
    }
    return Collector.of(Adj::new, Adj::add, Adj::merge, Adj::finish);
}
4
投票

您可以使用 reduce() 方法来完成此操作，其中 

U
是另一个 
List<Slot>
，但这比仅在 
for
循环中执行要复杂得多，除非需要并行处理。

请参阅答案末尾的测试设置。

这是 

for
循环实现：

List<Slot> mixed = new ArrayList<>();
Slot last = null;
for (Slot slot : slots)
    if (last == null || last.end != slot.start)
        mixed.add(last = slot);
    else
        mixed.set(mixed.size() - 1, last = new Slot(last.start, slot.end));

输出

[3-5, 5-7, 8-10, 10-11, 11-13]
[3-7, 8-13]

这是流减少实现：

List<Slot> mixed = slots.stream().reduce((List<Slot>)null, (list, slot) -> {
    System.out.println("accumulator.apply(" + list + ", " + slot + ")");
    if (list == null) {
        List<Slot> newList = new ArrayList<>();
        newList.add(slot);
        return newList;
    }
    Slot last = list.get(list.size() - 1);
    if (last.end != slot.start)
        list.add(slot);
    else
        list.set(list.size() - 1, new Slot(last.start, slot.end));
    return list;
}, (list1, list2) -> {
    System.out.println("combiner.apply(" + list1 + ", " + list2 + ")");
    if (list1 == null)
        return list2;
    if (list2 == null)
        return list1;
    Slot lastOf1 = list1.get(list1.size() - 1);
    Slot firstOf2 = list2.get(0);
    if (lastOf1.end != firstOf2.start)
        list1.addAll(list2);
    else {
        list1.set(list1.size() - 1, new Slot(lastOf1.start, firstOf2.end));
        list1.addAll(list2.subList(1, list2.size()));
    }
    return list1;
});

输出

accumulator.apply(null, 3-5)
accumulator.apply([3-5], 5-7)
accumulator.apply([3-7], 8-10)
accumulator.apply([3-7, 8-10], 10-11)
accumulator.apply([3-7, 8-11], 11-13)
[3-5, 5-7, 8-10, 10-11, 11-13]
[3-7, 8-13]

将其更改为并行（多线程）处理：

List<Slot> mixed = slots.stream().parallel().reduce(...

输出

accumulator.apply(null, 8-10)
accumulator.apply(null, 3-5)
accumulator.apply(null, 10-11)
accumulator.apply(null, 11-13)
combiner.apply([10-11], [11-13])
accumulator.apply(null, 5-7)
combiner.apply([3-5], [5-7])
combiner.apply([8-10], [10-13])
combiner.apply([3-7], [8-13])
[3-5, 5-7, 8-10, 10-11, 11-13]
[3-7, 8-13]

注意事项

如果 

slots
是空列表，则 
for
循环版本会产生空列表，而流版本结果是 
null
值。

测试设置

以上所有代码都使用了以下

Slot
类：

class Slot {
    int start;
    int end;
    Slot(int start, int end) {
        this.start = start;
        this.end = end;
    }
    @Override
    public String toString() {
        return this.start + "-" + this.end;
    }
}


slots
变量定义为：

List<Slot> slots = Arrays.asList(new Slot(3, 5), new Slot(5, 7), new Slot(8, 10), new Slot(10, 11), new Slot(11, 13));


slots
和结果
mixed
均使用以下方式打印：

System.out.println(slots);
System.out.println(mixed);
3
投票

这是两行：

List<Slot> condensed = new LinkedList<>();
slots.stream().reduce((a,b) -> {if (a.end == b.start) return new Slot(a.start, b.end); 
  condensed.add(a); return b;}).ifPresent(condensed::add);

如果插槽字段不可见，则必须将

a.end
更改为
a.getEnd()
等

一些带有一些边缘情况的测试代码：

List<List<Slot>> tests = Arrays.asList(
        Arrays.asList(new Slot(3, 5), new Slot(5, 7), new Slot(8, 10), new Slot(10, 11), new Slot(11, 13)),
        Arrays.asList(new Slot(3, 5), new Slot(5, 7), new Slot(8, 10), new Slot(10, 11), new Slot(12, 13)),
        Arrays.asList(new Slot(3, 5), new Slot(5, 7)),
        Collections.emptyList());
for (List<Slot> slots : tests) {
    List<Slot> condensed = new LinkedList<>();
    slots.stream().reduce((a, b) -> {if (a.end == b.start) return new Slot(a.start, b.end);
        condensed.add(a); return b;}).ifPresent(condensed::add);
    System.out.println(condensed);
}

输出：

[3-7, 8-13]
[3-7, 8-11, 12-13]
[3-7]
[]
3
投票

不需要任何新方法的干净（并行安全）解决方案：

List<Slot> condensed = slots.stream().collect(LinkedList::new,
  (l, s) -> l.add(l.isEmpty() || l.getLast().end != s.start ?
    s : new Slot(l.removeLast().start, s.end)),
  (l, l2) -> {if (!l.isEmpty() && !l2.isEmpty() && l.getLast().end == l2.getFirst().start) {
    l.add(new Slot(l.removeLast().start, l2.removeFirst().end));} l.addAll(l2);});

这使用了更合适的列表实现

LinkedList
来简化合并插槽时删除和访问列表最后一个元素的过程。

List<List<Slot>> tests = Arrays.asList(
            Arrays.asList(new Slot(3, 5), new Slot(5, 7), new Slot(8, 10), new Slot(10, 11), new Slot(11, 13)),
            Arrays.asList(new Slot(3, 5), new Slot(5, 7), new Slot(8, 10), new Slot(10, 11), new Slot(12, 13)),
            Arrays.asList(new Slot(3, 5), new Slot(5, 7)),
            Collections.emptyList());
for (List<Slot> slots : tests) {
    List<Slot> condensed = slots.stream().collect(LinkedList::new,
      (l, s) -> l.add(l.isEmpty() || l.getLast().end != s.start ?
        s : new Slot(l.removeLast().start, s.end)),
      (l, l2) -> {if (!l.isEmpty() && !l2.isEmpty() && l.getLast().end == l2.getFirst().start) {
        l.add(new Slot(l.removeLast().start, l2.removeFirst().end));} l.addAll(l2);});
    System.out.println(condensed);
}

输出：

[[3, 7], [8, 13]]
[[3, 7], [8, 11], [12, 13]]
[[3, 7]]
[]
2
投票

如果您将以下方法添加到您的

Slot
类中

public boolean join(Slot s) {
    if(s.start != end)
        return false;
    end = s.end;
    return true;
}

您可以通过以下方式使用标准 API 执行整个操作

List<Slot> result = slots.stream().collect(ArrayList::new,
    (l, s)-> { if(l.isEmpty() || !l.get(l.size()-1).join(s)) l.add(s); },
    (l1, l2)-> l1.addAll(
        l1.isEmpty()||l2.isEmpty()||!l1.get(l1.size()-1).join(l2.get(0))?
        l2: l2.subList(1, l2.size()))
);

这遵守 API 的约定（与滥用 

reduce
不同），因此可以与并行流无缝协作（尽管您需要 really 大型源列表才能从并行执行中受益）。

但是，上面的解决方案使用 

Slot
的就地连接，只有当您不再需要源列表/项目时才可以接受。否则，或者如果您仅使用不可变的 
Slot
实例，则必须创建代表关节槽的新 
Slot
实例。

一种可能的解决方案如下

BiConsumer<List<Slot>,Slot> joinWithList=(l,s) -> {
    if(!l.isEmpty()) {
        Slot old=l.get(l.size()-1);
        if(old.end==s.start) {
            l.set(l.size()-1, new Slot(old.start, s.end));
            return;
        }
    }
    l.add(s);
};
List<Slot> result = slots.stream().collect(ArrayList::new, joinWithList,
    (l1, l2)-> {
        if(!l2.isEmpty()) {
            joinWithList.accept(l1, l2.get(0));
            l1.addAll(l2.subList(1, l2.size()));
        }
    }
);
0
投票

这是一个库函数，可用于帮助进行邻居组合流操作：

/**
 * Returns a {@link Collector} that returns a list which can combine elements of
 * the incoming stream into merged elements.  (Call stream() again on the list to
 * continue stream processing.)
 * @param testNeighbors Predicate that tests the preceding and next elements, returning
 *  true if they should be combined
 * @param combineNeighbors Operator that combines two neighboring items which should
 *  be combined
 * @param <R> type of the elements
 */
public static <R> Collector<R,LinkedList<R>,LinkedList<R>> combineNeighborsCollector(
        BiPredicate<R,R> testNeighbors,
        BinaryOperator<R> combineNeighbors) {
    return Collector.of(
        LinkedList::new,
        (LinkedList<R> list1, R next) -> {
            // Can't combine if list is empty.
            if (! list1.isEmpty() && testNeighbors.test(list1.getLast(), next)) {
                R lCombined = combineNeighbors.apply(list1.getLast(), next);
                list1.removeLast();
                list1.add(lCombined);
            } else {
                list1.add(next);
            }
        },
        (LinkedList<R> list1, LinkedList<R> list2) -> {
            // Can't combine if either list is empty.
            while (! list1.isEmpty() && ! list2.isEmpty()
                    && testNeighbors.test(list1.getLast(), list2.getFirst())) {
                R last = list1.getLast();
                R next = list2.getFirst();
                list1.removeLast();
                list2.removeFirst();
                list1.add(combineNeighbors.apply(last, next));
            }
            list1.addAll(list2);
            return list1;
        });
}

测试：

record Slot(int start, int end) {
    @Override public String toString() { return "[%d,%d]".formatted(start,end); }
}

public static final Collector<Slot, LinkedList<Slot>, LinkedList<Slot>>
SLOT_COMBINING_COLLECTOR = 
    combineNeighborsCollector(
        (Slot slot1, Slot slot2) -> slot1.end == slot2.start, // Test neighbors.
        (Slot slot1, Slot slot2) -> new Slot(slot1.start, slot2.end)); // Combine neighbors.

public static void main(String[] args) {
    System.out.println(Stream.of(
            new Slot(1, 3), new Slot(4, 7), new Slot(7, 10), new Slot(10,12), new Slot(20, 25))
        .collect(SLOT_COMBINING_COLLECTOR)
        .stream()
        .map(Objects::toString)
        .collect(Collectors.joining(", ")));
}

打印：

[1,3], [4,12], [20,25]

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.