Потоки guava :: реализация findLast - PullRequest
Новая
       25

Потоки guava :: реализация findLast

3 голосов
/ 03 апреля 2019

Я смотрю на реализацию Streams::findLast из гуавы и, пытаясь понять это, была пара вещей, которые я просто не мог понять.Вот его реализация: 

public static <T> java.util.Optional<T> findLast(Stream<T> stream) {
    class OptionalState {

        boolean set = false;
        T value = null;

        void set(@Nullable T value) {
            set = true;
            this.value = value;
        }

        T get() {
            checkState(set);
            return value;
        }
    }
    OptionalState state = new OptionalState();

    Deque<Spliterator<T>> splits = new ArrayDeque<>();
    splits.addLast(stream.spliterator());

    while (!splits.isEmpty()) {
        Spliterator<T> spliterator = splits.removeLast();

        if (spliterator.getExactSizeIfKnown() == 0) {
            continue; // drop this split
        }

        // Many spliterators will have trySplits that are SUBSIZED even if they are not themselves
        // SUBSIZED.
        if (spliterator.hasCharacteristics(Spliterator.SUBSIZED)) {
            // we can drill down to exactly the smallest nonempty spliterator
            while (true) {
                Spliterator<T> prefix = spliterator.trySplit();
                if (prefix == null || prefix.getExactSizeIfKnown() == 0) {
                    break;
                } else if (spliterator.getExactSizeIfKnown() == 0) {
                    spliterator = prefix;
                    break;
                }
            }

            // spliterator is known to be nonempty now
            spliterator.forEachRemaining(state::set);
            return java.util.Optional.of(state.get());
        }

        Spliterator<T> prefix = spliterator.trySplit();
        if (prefix == null || prefix.getExactSizeIfKnown() == 0) {
            // we can't split this any further
            spliterator.forEachRemaining(state::set);
            if (state.set) {
                return java.util.Optional.of(state.get());
            }
            // fall back to the last split
            continue;
        }
        splits.addLast(prefix);
        splits.addLast(spliterator);
    }
    return java.util.Optional.empty();
}

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

Первое - это создание класса OptionalState, его можно было бы заменить массивомодного элемента: 

T[] state = (T[]) new Object[1];

и используется так же просто, как: 

spliterator.forEachRemaining(x -> state[0] = x);

Тогда весь метод можно разбить на 3 части:

1), когдаопределенный Spliterator, как известно, пустой: 

if (spliterator.getExactSizeIfKnown() == 0)

В этом случае это просто - просто отбросьте его.

2) тогда, если известно, что Spliterator равен SUBSIZED.Это сценарий «счастливого пути»;как в этом случае мы можем разделить это, пока мы не дойдем до последнего элемента.По сути, реализация гласит: split до тех пор, пока prefix не станет равным null или не станет пустым (в этом случае используется «правильный» сплитератор), или если после разделения известно, что «правый» сплитератор пуст, используйте prefix один.Это делается с помощью: 

// spliterator is known to be nonempty now
spliterator.forEachRemaining(state::set);
return java.util.Optional.of(state.get());

Второй вопрос, который у меня есть, на самом деле об этом комментарии: 

// Many spliterators will have trySplits that are SUBSIZED 
// even if they are not themselves SUBSIZED.

Это очень интересно, но я не смог найти такойНапример, был бы признателен, если бы кто-то познакомил меня с одним.Фактически, поскольку этот комментарий существует, код в следующей (3-й части метода не может быть выполнен с while(true), как во втором), потому что он предполагает, что после trySplit мы могли бы получитьSpliterator, то есть SUBSIZED, даже если наш начальный не был, поэтому он должен перейти к самому началу findLast.

3) эта часть метода - это когда Spliteratorизвестно, что не равно SUBSIZED, и в этом случае он не имеет известного размера;таким образом, он зависит от того, как реализован Spliterator из источника, и в этом случае на самом деле findLast не имеет особого смысла ... например, Spliterator из HashSet вернет то, что последняя запись находится в последнем сегменте...

1 Ответ

4 голосов
/ 03 апреля 2019

  1. Когда вы повторяете Spliterator неизвестного размера, вы должны отслеживать, был ли обнаружен элемент. Это можно сделать, вызвав tryAdvance и используя возвращаемое значение или используя forEachRemaining с Consumer, который записывает, был ли обнаружен элемент. Когда вы идете по последнему маршруту, выделенный класс проще, чем массив. И если у вас есть специальный класс, почему бы не использовать его и для SIZED spliterator.

    Что странно для меня, это то, что этот локальный класс, который существует только для использования в качестве Consumer, не реализует Consumer, но требует привязки через state::set.

  2. Рассмотрим 

    Stream.concat(
    Stream.of("foo").filter(s -> !s.isEmpty()),
    Stream.of("bar", "baz"))

    Spliterator, представляющий весь поток, не может иметь характеристику SIZED. Но при разделении первого подпотока с неизвестным размером оставшийся поток имеет известный размер.

    Тестовый код: 

    Spliterator<String> sp = Stream.concat(
    Stream.of("foo").filter(s -> !s.isEmpty()),
    Stream.of("bar", "baz"))
    .spliterator();
do {
    System.out.println(
          "SIZED: "+sp.hasCharacteristics(Spliterator.SIZED)
        + ", SUBSIZED: "+sp.hasCharacteristics(Spliterator.SUBSIZED)
        + ", exact size if known: "+sp.getExactSizeIfKnown());
} while(sp.trySplit() != null);

    Результат: 

    SIZED: false, SUBSIZED: false, exact size if known: -1
SIZED: true, SUBSIZED: true, exact size if known: 2
SIZED: true, SUBSIZED: true, exact size if known: 1

    Но для меня это выглядит странно, когда кто-то говорит в комментарии знать, что расщепление может изменить характеристики, а затем выполнить предварительное тестирование с SUBSIZED вместо того, чтобы просто выполнить расщепление и проверить, есть ли у результата известный размер. В конце концов, код в любом случае выполняет разбиение в альтернативной ветви, когда характеристика отсутствует. В моем старом ответе я провел предварительное тестирование, чтобы избежать выделения структур данных, но здесь ArrayDeque всегда создается и используется. Но я думаю, что даже мой старый ответ может быть упрощен.

  3. Я не уверен, к чему вы стремитесь. Когда Spliterator имеет характеристику ORDERED, порядок обхода и разбиения четко определен. Поскольку HashSet не упорядочен, термин «последний» не имеет смысла. Если вы радикальны, вы можете оптимизировать операцию, чтобы просто вернуть первый элемент для неупорядоченных потоков; это действительно и намного быстрее.

    Что странно, это условие: 

    if (prefix == null || prefix.getExactSizeIfKnown() == 0) {
    // we can't split this any further

    (и аналогичное завершение цикла в пути SUBSIZED)

    То, что один префикс имеет известный нулевой размер, не означает, что суффикс не может быть разделен дальше. Ничто в спецификации не говорит об этом.

    Как следствие этого условия, Stream.concat(Stream.of("foo"), Stream.of("bar","baz")) может обрабатываться оптимально, в то время как для Stream.concat(Stream.of(), Stream.of("bar", "baz")) он возвращается к обходу, поскольку первый префикс имеет известный размер, равный нулю.

...