Java 流 trim 列表

Question

我有以下实现，用于根据给定谓词修剪元素列表（即 - 删除前导和尾随空元素）。

我想让实现更具可读性，最好使用 Java 的流 API。

/**
 * Trim a List based on a given predicate, that is, remove leading
 * and trailing elements that match the predicate (but not in-between
 * non-matching elements).
 *
 * @param list the list to trim
 * @param trimPredicate the predicate for trimming
 * @param <T> type of the list
 * @return the same list minus the trimmed elements.
 * @throws NullPointerException if the list is {@code null}
 * @throws UnsupportedOperationException if the {@code remove}
 *      operation is not supported by the list iterator
 */
public static <T> List<T> trim(List<T> list, Predicate<T> trimPredicate)
        throws NullPointerException, UnsupportedOperationException {
    if (list == null) throw new NullPointerException("list is null");
    ListIterator<T> it = list.listIterator();
    while (it.hasNext() && trimPredicate.test(it.next())) it.remove();
    it = list.listIterator(list.size());
    while (it.hasPrevious() && trimPredicate.test(it.previous())) it.remove();

    return list;
}

有什么建议吗？

举个例子，让事情更清楚：

对于List<Integer>，考虑到0为空值，列表如下：

[0, 0, 3, 5, 0, 4, 0, -3, 0, 0]

将被修剪为：

[3, 5, 0, 4, 0, -3]

（而且这里至少有两个不同的读者弄错了这一事实，证明了我关于代码可读性的观点:)。

Answer 1

一点 hackery 使它成为可能，但我不确定它是否更清楚。

/**
 * Stateful predicate to only match until matching fails.
 * It seems this is not necessary in Java 9.
 */
static class MatchWhile<T> implements Predicate<T> {
    final Predicate<T> matcher;
    boolean match = true;

    MatchWhile(Predicate<T> matcher) {
        this.matcher = matcher;
    }

    @Override
    public boolean test(T t) {
        return match && (match = matcher.test(t));
    }
}

// Hides the horrible stuff.
static <T> Stream<T> asStream(Iterator<T> it) {
    return StreamSupport.stream(Spliterators.spliteratorUnknownSize(it,Spliterator.ORDERED), false);
}

<T> List<T> trim2(List<T> list, Predicate<T> isEmpty) {
    // Trim right using a Deque to reverse it.
    Deque<T> reversedAndTrimmedAtEnd = asStream(new ArrayDeque<>(list).descendingIterator())
            .filter(new MatchWhile<>(isEmpty).negate())
            .collect(Collectors.toCollection(ArrayDeque::new));
    // Reverse it again to trim left.
    List<T> leftTrimmed = asStream(reversedAndTrimmedAtEnd.descendingIterator())
            .filter(new MatchWhile<>(isEmpty).negate())
            .collect(Collectors.toList());

    return leftTrimmed;
}

Answer 2

您的原始代码非常易读且高效。推荐。

static <T> List<T> trim2(List<T> list, Predicate<T> isEmpty) {
    ListIterator<T> it = list.listIterator();
    while (it.hasNext() && isEmpty.test(it.next())) {
        it.remove();
    }
    it = list.listIterator(list.size());
    while (it.hasPrevious() && isEmpty.test(it.previous())) {
        it.remove();
    }
    return list;
}

stream 版本使用 java 9. 仅供参考，不推荐。

static <T> List<T> trim3(List<T> list, Predicate<T> isEmpty) {
    Collection<T> ltrimreverse = list.stream().dropWhile(isEmpty)
        .collect(ArrayDeque::new, ArrayDeque::push, ArrayDeque::addAll);
    Collection<T> rtrim = ltrimreverse.stream().dropWhile(isEmpty)
        .collect(ArrayDeque::new, ArrayDeque::push, ArrayDeque::addAll);
    return new ArrayList<>(rtrim);
}

Answer 3

如果你关心效率，你应该避免重复单个remove操作，特别是在List的开头，因为最常用的实现，ArrayList，不在这方面表现非常好，因为当您删除条目时，它必须复制其内部数组中的所有剩余元素。

最坏的情况，即以这种方式删除所有元素，将具有二次时间复杂度。

public static <T> List<T> trim(List<T> list, Predicate<T> trimPredicate) {

    Objects.requireNonNull(list, "list is null");
    Objects.requireNonNull(trimPredicate, "trimPredicate is null");

    int lastMatch;

    for(ListIterator<T> it = list.listIterator(lastMatch = list.size());
        it.hasPrevious() && trimPredicate.test(it.previous());) lastMatch = it.nextIndex();

    if(lastMatch < list.size()) list.subList(lastMatch, list.size()).clear();

    for(ListIterator<T> it = list.listIterator(lastMatch = 0);
        it.hasNext() && trimPredicate.test(it.next()); ) lastMatch = it.previousIndex();

    if(lastMatch > 0) list.subList(0, lastMatch+1).clear();

    return list;
}

List.subList(…).clear() 是有效删除一系列项目的正确习惯用法。在 ArrayList 的情况下，它意味着整个范围删除只需要一个复制操作。所以我们只迭代不移除，确定范围，然后进行单次移除操作。

由于在最后删除没有额外的成本，因为没有剩余的元素要复制，这个解决方案首先删除最后的匹配项，以潜在地减少剩余元素的数量，以便随后删除匹配项列表的前面。

对于将直接修改列表的就地操作，没有可以改进它的 Stream 解决方案。

即使您想 return 一个新列表，最有效的解决方案之一也是基于 subList:

public static <T> List<T> trim(List<T> list, Predicate<T> trimPredicate) {

    Objects.requireNonNull(list, "list is null");
    Objects.requireNonNull(trimPredicate, "trimPredicate is null");

    int firstToKeep = 0, lastToKeep = list.size();
    for(T t: list) if(trimPredicate.test(t)) firstToKeep++; else break;
    for(ListIterator<T> it = list.listIterator(lastToKeep);
        lastToKeep > firstToKeep && it.hasPrevious() && trimPredicate.test(it.previous());)
        lastToKeep = it.nextIndex();

    return new ArrayList<>(list.subList(firstToKeep, lastToKeep));
}

Java 流 trim 列表

Java stream trim list

java

trim

java-stream