Список обрезки потока Java

Question

У меня есть следующая реализация для обрезки списка элементов на основе заданного предиката (то есть - удаления начальных и конечных пустых элементов).

Я хотел бы сделать реализацию более читабельной, желательно с использованием JavaAPI потока.

/**
 * 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

Ваш оригинальный код довольно читабелен и эффективен.рекомендуется.

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;
}

потоковая версия с использованием 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 2

Если вы заботитесь об эффективности, вам следует избегать повторяющихся одиночных операций 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 это подразумевает только одну операцию копирования для удаления всего диапазона.Таким образом, мы только выполняем итерацию без удаления, чтобы определить диапазон, а затем выполняем одну операцию удаления.

Поскольку удаление в конце не требует дополнительных затрат, так как нет оставшихся элементов для копирования, это решение сначала удаляет совпаденияв конце, чтобы потенциально уменьшить количество оставшихся элементов для последующего удаления совпадений в начале списка.

Для операции на месте, которая будет непосредственно изменять список, нет потокарешение, которое улучшит его.

Даже если вы хотите вернуть новый список, одно из самых эффективных решений будет основано на 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));
}

Answer 3

Немного хакерства делает это возможным, но я не уверен, что это понятнее.

/**
 * 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;
}