Пишем свой Spliterator / forpes.ru

Главная
Пишем свой Spliterator

Пишем свой Spliterator +21

12.05.2015 04:12

lany 26 6531 Источник

Многие из вас уже попробовали на вкус Stream API — потоки Java 8. Наверняка у некоторых возникло желание не только пользоваться готовыми потоками от коллекций, массивов, случайных чисел, но и создать какой-то принципиально новый поток. Для этого вам потребуется написать свой сплитератор. Spliterator — это начинка потока, публичная часть его внутренней логики. В этой статье я расскажу, как и зачем я писал сплитератор.

Что же такое сплитератор

Сплитератор — это интерфейс, который содержит 8 методов, причём четыре из них уже имеют реализацию по умолчанию. Оставшиеся методы — это tryAdvance, trySplit, estimateSize и characteristics. Существуют также специальные модификации сплитератора для примитивных типов int, long и double: они добавляют несколько дополнительных методов, чтобы избежать боксинга. Сплитератор похож на обычный итератор. Основное отличие — умение разделиться (split) на две части — лежит в основе параллельной работы потоков. Также в целях оптимизации сплитератор имеет ряд флагов-характеристик и может сообщить точно или приблизительно свой размер. Наконец, сплитератор никогда не модифицирует источник данных: у него нет метода remove как у итератора. Рассмотрим методы подробнее:

tryAdvance(Consumer) — объединение методов итератора hasNext() и next(). Если у сплитератора есть следующий элемент, он должен вызвать переданную функцию с этим элементом и вернуть true, иначе функцию не вызывать и вернуть false.
trySplit() — попытаться поделиться надвое. Метод возвращает новый сплитератор, который будет пробегать по первой половине исходного набора данных, при этом сам текущий сплитератор перепрыгивает на вторую половину. Лучше всего, когда половины примерно равны, но это не обязательно. Особенно неравномерно делятся сплитераторы с бесконечным набором данных: после деления один из сплитераторов обрабатывает конечный объём, а второй остаётся бесконечным. Метод trySplit() имеет законное право не делиться и вернуть null (не случайно там try). Обычно это делается, когда в текущем сплитераторе осталось мало данных (скажем, только один элемент).
characteristics() — возвращает битовую маску характеристик сплитератора. Их на данный момент восемь:
1. ORDERED — если порядок данных имеет значение. К примеру, сплитератор от HashSet не имеет этой характеристики, потому что порядок данных в HashSet зависит от реализации. Отсутствие этой характеристики автоматически переведёт параллельный поток в неупорядоченный режим, благодаря чему он сможет работать быстрее. Раз в источнике данных порядка не было, то и дальше можно за ним не следить.
2. DISTINCT — если элементы заведомо уникальны. Любой Set или поток после операции distinct() создаёт сплитератор с такой характеристикой. Например, операция distinct() на потоке из Set выполняться не будет вообще и, стало быть, времени лишнего не займёт.
3. SORTED — если элементы сортированы. В таком случае обязательно вернуть и ORDERED и переопределить метод getComparator(), вернув компаратор сортировки или null для «естественного порядка». Сортированные коллекции (например, TreeSet) создают сплитератор с такой характеристикой, и с ней потоковая операция sorted() может быть пропущена.
4. SIZED — если известно точное количество элементов сплитератора. Такую характеристику возвращают сплитераторы всех коллекций. После некоторых потоковых операций (например, map() или sorted()) она сохраняется, а после других (скажем, filter() или distinct()) — теряется. Она полезна для сортировки или, скажем, операции toArray(): можно заранее выделить массив нужного размера, а не гадать, сколько элементов понадобится.
5. SUBSIZED — если известно, что все дочерние сплитераторы также будут знать свой размер. Эту характеристику возвращает сплитератор от ArrayList, потому что при делении он просто разбивает диапазон значений на два диапазона известной длины. А вот HashSet её не вернёт, потому что он разбивает хэш-таблицу, для которой не известно, сколько содержится элементов в каждой половине. Соответственно дочерние сплитераторы уже не будут возвращать и SIZED.
6. NONNULL — если известно, что среди элементов нет null. Эту характеристику возвращает, например, сплитератор, созданный ConcurrentSkipListSet: в эту структуру данных null поместить нельзя. Также её возвращают все сплитераторы, созданные на примитивных типах.
7. IMMUTABLE — если известно, что источник данных в процессе обхода заведомо не может измениться. Сплитераторы от обычных коллекций такую характеристику не возвращают, но её выдаёт, например, сплитератор от Collections.singletonList(), потому что этот список изменить нельзя.
8. CONCURRENT — если известно, что сплитератор остаётся рабочим после любых изменений источника. Такую характеристику сообщают сплитераторы коллекций из java.util.concurrent. Если сплитератор не имеет характеристик IMMUTABLE и CONCURRENT, то хорошо бы заставить его работать в fail-fast режиме, чтобы он кидал ConcurrentModificationException, если заметит, что источник изменился.
Насколько мне известно, последние три характеристики сейчас потоками никак не используются (в том числе в коде Java 9).
estimateSize() — метод должен возвращать количество оставшихся элементов для SIZED-сплитераторов и как можно более точную оценку в остальных случаях. Например, если мы создадим сплитератор от HashSet и разделим его с помощью trySplit(), estimateSize() будет возвращать половину от исходного размера коллекции, хотя реальное количество элементов в половине хэш-таблицы может отличаться. Если элементов бесконечное количество или посчитать их слишком трудозатратно, можно вернуть Long.MAX_VALUE.

Создать поток по имеющемуся сплитератору очень легко — надо вызвать StreamSupport.stream().

Когда сплитератор писать не надо

Главное понимать, что сам по себе сплитератор вам не нужен, вам нужен поток. Если вы можете создать поток, используя существующий функционал, то стоит сделать именно так. К примеру, хотите вы подружить потоки с XML DOM и создавать поток по NodeList. Стандартного такого метода нет, но его легко написать без дополнительных сплитераторов:

public class XmlStream {
	static Stream<Node> of(NodeList list) {
		return IntStream.range(0, list.getLength()).mapToObj(list::item);
	}
}

Аналогично можно добавить потоки к любой нестандартной коллекции (ещё пример — org.json.JSONArray), которая умеет быстро вернуть длину и элемент по порядковому номеру.

Если вам трудно или лень писать trySplit, лучше не пишите сплитератор вообще. Вот один товарищ пишет библиотеку protonpack, полностью игнорируя существование параллельных потоков. Он написал много сплитераторов, которые вообще не умеют делиться. Сплитератор, который вообще не делится — это плохой, негодный сплитератор. Не делайте так. В данном случае лучше написать обычный итератор и создать по нему сплитератор с помощью методов Spliterators.spliterator или, если вам заранее неизвестен размер коллекции, то Spliterators.spliteratorUnknownSize. Эти методы имеют хоть какую-то эвристику для деления: они обходят часть итератора, вычитывая его в массив и создавая новый сплитератор для этого массива. Если в потоке будет дальше длительная операция, то распараллеливание всё равно ускорит работу.

Если вы реализуете стандартный интерфейс Iterable или Collection, то вам совершенно бесплатно выдаётся default-метод spliterator(). Стоит, конечно, посмотреть, нельзя ли его улучшить. Так или иначе, свои сплитераторы требуется писать весьма редко. Это может пригодиться, если вы разрабатываете свою структуру данных (например, коллекцию на примитивах, как делает leventov).

И всё-таки напишем

Мы напишем новый сплитератор для решения такой задачи: по заданному потоку создать поток пар из соседних значений исходного потока. Так как общепринятого типа для представления пары значений в Java нет и возможных вариантов слишком много (использовать массив из двух значений, список из двух значений, Map.Entry с одинаковым типом ключа и значения и т. д.), мы отдадим это на откуп пользователю: пусть сам решает, как объединить два значения. То есть мы хотим создать метод с такой сигнатурой:

public static <T, R> Stream<R> pairMap(Stream<T> stream, BiFunction<T, T, R> mapper) {...}

С его помощью можно использовать любой тип для представления пары. Например, если мы хотим Map.Entry:

public static <T> Stream<Map.Entry<T, T>> pairs(Stream<T> stream) {
    return pairMap(stream, AbstractMap.SimpleImmutableEntry<T, T>::new);
}

А можно вообще сразу вычислить что-нибудь интересное, не складывая пары в промежуточный контейнер:

public static Stream<Integer> diff(Stream<Integer> stream) {
    return pairMap(stream, (a, b) -> b - a);
}

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

Мы хотим, чтобы наш pairMap выглядел как обычная промежуточная (intermediate) операция, то есть фактически никаких вычислений производиться не должно, пока дело не дойдёт до терминальной операции. Для этого надо взять spliterator у входного потока, но ничего с ним не делать, пока нас не попросят. Ещё одна маленькая, но важная вещь: при закрытии нового потока через close() надо закрыть исходный поток. В итоге наш метод может выглядеть так:

public static <T, R> Stream<R> pairMap(Stream<T> stream, BiFunction<T, T, R> mapper) {
    return StreamSupport.stream(new PairSpliterator<>(mapper, stream.spliterator()), stream.isParallel()).onClose(stream::close);
}

Исходный поток после вызова метода spliterator() становится «использованным», с ним больше каши не сваришь. Но это нормально: так происходит со всеми промежуточными потоками, когда вы добавляете новую операцию. Метод Stream.concat(), склеивающий два потока, выглядит примерно так же. Осталось написать сам PairSpliterator.

Переходим к сути дела

Самое простое — это написать метод characteristics(). Часть характеристик наследуется у исходного сплитератора, но необходимо сбросить NONNULL, DISTINCT и SORTED: мы не можем гарантировать этих характеристик после применения произвольной mapper-функции:

public int characteristics() {
    return source.characteristics() & (SIZED | SUBSIZED | CONCURRENT | IMMUTABLE | ORDERED);
}

Реализация метода tryAdvance должна быть довольно простой. Надо лишь вычитывать данные из исходного сплитератора, запоминая предыдущий элемент в промежуточном буфере, и вызывать для последней пары mapper. Стоит только помнить, находимся мы в начале потока или нет. Для этого пригодится булева переменная hasPrev, указывающая, есть ли у нас предыдущее значение.

Метод trySplit лучше всего реализовать, вызвав trySplit у исходного сплитератора. Основная сложность тут — обработать пару на стыке двух разделённых кусков исходного потока. Эту пару должен обработать сплитератор, который обходит первую половину. Соответственно, он должен хранить первое значение из второй половины и, когда доберётся до конца, сработать ещё раз, подав его в mapper вместе с последним своим значением.

Разобравшись с этим, напишем конструкторы:

class PairSpliterator<T, R> implements Spliterator<R> {
    Spliterator<T> source;
    boolean hasLast, hasPrev;
    private T cur;
    private final T last;
    private final BiFunction<T, T, R> mapper;

    public PairSpliterator(BiFunction<T, T, R> mapper, Spliterator<T> source) {
        this(mapper, source, null, false, null, false);
    }

    public PairSpliterator(BiFunction<T, T, R> mapper, Spliterator<T> source, T prev, boolean hasPrev, T last,
            boolean hasLast) {
        this.source = source; // исходный сплитератор
        this.hasLast = hasLast; // есть ли дополнительный элемент в конце (первый из следующего куска)
        this.hasPrev = hasPrev; // известен ли предыдущий элемент
        this.cur = prev; // предыдущий элемент
        this.last = last; // дополнительный элемент в конце
        this.mapper = mapper;
    }
    // ...
}

Метод tryAdvance (вместо лямбды для передачи в исходный tryAdvance воспользуемся ссылкой на сеттер):

void setCur(T t) {
    cur = t;
}

@Override
public boolean tryAdvance(Consumer<? super R> action) {
    if (!hasPrev) { // мы в самом начале: считаем один элемент из источника
        if (!source.tryAdvance(this::setCur)) {
            return false; // источник вообще пустой — выходим
        }
        hasPrev = true;
    }
    T prev = cur; // запоминаем предыдущий элемент
    if (!source.tryAdvance(this::setCur)) { // вычитываем следующий из источника
        if (!hasLast)
            return false; // совсем всё закончилось — выходим
        hasLast = false; // обрабатываем пару на стыке двух кусков
        cur = last;
    }
    action.accept(mapper.apply(prev, cur)); // передаём в action результат mapper'а
    return true;
}

А вот и метод trySplit():

public Spliterator<R> trySplit() {
    Spliterator<T> prefixSource = source.trySplit(); // пытаемся разделить источник
    if (prefixSource == null)
        return null; // не вышло — тогда мы сами тоже не делимся
    T prev = cur; // это последний считанный до сих пор элемент, если он вообще был
    if (!source.tryAdvance(this::setCur)) { // вычитываем первый элемент второй половины
        source = prefixSource; // вторая половина источника оказалась пустой — смысла делиться нет
        return null;
    }
    boolean oldHasPrev = hasPrev;
    hasPrev = true; // теперь текущий сплитератор обходит вторую половину, а для первой создаём новый
    return new PairSpliterator<>(mapper, prefixSource, prev, oldHasPrev, cur, true);
}

Написать estimateSize() несложно: если исходный сплитератор способен оценить свой размер, надо лишь проверить флаги и подправить его на единичку туда или обратно:

public long estimateSize() {
    long size = source.estimateSize();
    if (size == Long.MAX_VALUE) // источник не смог оценить свой размер — мы тоже не можем
        return size;
    if (hasLast) // этот сплитератор будет обрабатывать дополнительную пару на стыке кусков
        size++;
    if (!hasPrev && size > 0) // этот сплитератор ещё не вычитал первый элемент
        size--;
    return size;
}

В подобном виде этот сплитератор и попал в мою библиотеку StreamEx. Отличие только в том, что потребовалось сделать версии для примитивных типов, ну и pairMap — это не статический метод.

Всё это, небось, сильно тормозит?

Со скоростью всё не так плохо. Возьмём для примера вот такую задачу со StackOverflow: из заданного набора чисел Integer оставить только те, которые меньше следующего за ними числа, и сохранить результат в новый список. Сама по себе задача очень простая, поэтому существенная часть времени будет уходить на оверхед. Можно предложить две наивные реализации: через итератор (будет работать с любой коллекцией) и через доступ по номеру элемента (будет работать только со списком с быстрым случайным доступом). Вот вариант с итератором (naiveIterator):

List<Integer> result = new ArrayList<>();
Integer last = null;
for (Integer cur : input) {
    if (last != null && last < cur)
        result.add(last);
    last = cur;
}

А вот со случайным доступом (naiveGet):

List<Integer> result = new ArrayList<>();
for (int i = 0; i < input.size() - 1; i++) {
    Integer cur = input.get(i), next = input.get(i + 1);
    if (cur < next)
        result.add(cur);
}

Решение с помощью библиотеки StreamEx очень компактно и работает с любым источником данных (streamEx):

List<Integer> result = StreamEx.of(input).pairMap((a, b) -> a < b ? a : null).nonNull().toList();

Комментаторами было предложено ещё три работающих решения. Наибольшее число голосов набрало более-менее традиционное, которому на входе требуется список со случайным доступом (назовём это решение stream):

List<Integer> result = IntStream.range(0, input.size() - 1).filter(i -> input.get(i) < input.get(i + 1)).mapToObj(input::get)
                .collect(Collectors.toList());

Следующее — это reduce с побочным эффектом, который не параллелится (reduce):

List<Integer> result = new ArrayList<>();
input.stream().reduce((a, b) -> {
    if (a < b)
        result.add(a);
    return b;
});

И последнее — это свой коллектор, который также не параллелится (collector):

public static Collector<Integer, ?, List<Integer>> collectPrecedingValues() {
    int[] holder = { Integer.MAX_VALUE };
    return Collector.of(ArrayList::new, (l, elem) -> {
        if (holder[0] < elem)
            l.add(holder[0]);
        holder[0] = elem;
    }, (l1, l2) -> {
        throw new UnsupportedOperationException("Don't run in parallel");
    });
}

List<Integer> result = input.stream().collect(collectPrecedingValues());

В сравнение также попадают распараллеленные версии stream и streamEx. Опыт будем проводить на массивах случайных целых чисел длиной n = 10 000, 100 000 и 1 000 000 элементов (в результат попадёт порядка половины). Полный код JMH-бенчмарка здесь. Проверено, что все алгоритмы выдают одинаковый результирующий массив.

Замеры проводились на четырёхъядерном Core-i5. Результаты выглядят так (все времена в микросекундах на операцию, меньше — лучше):

Алгоритм	n = 10 000	n = 100 000	n = 1 000 000
naiveIterator	97.7	904.0	10592.7
naiveGet	99.8	1084.4	11424.2
collector	112.5	1404.9	14387.2
reduce	112.1	1139.5	12001.5
stream	146.4	1624.1	16600.9
streamEx	115.2	1247.1	12967.0
streamParallel	56.9	582.3	6120.5
streamExParallel	53.4	516.7	5353.4

Видно, что версия с pairMap (streamEx) обгоняет и традиционный потоковый вариант (stream), и версию с коллектором, уступая только неправильному reduce. При этом параллельная версия streamEx также быстрее параллельной версии stream и существенно обгоняет все последовательные версии даже для небольшого набора данных. Это согласуется с эмпирическим правилом из Stream Parallel Guidance: имеет смысл параллелить задачу, если она выполняется не менее 100 микросекунд.

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

Комментарии (26)

asm0dey
13.05.2015 13:59
#8415475
+1
Спасибо за статью, она отличная. Не хватает только погрешностей в бенчмарке.
1. lany Автор
  13.05.2015 14:07
  #8415491
  +1
  Добавил результаты в gist с погрешностями.
  
  Ну хоть кто-то откомментировал! :-)
  1. asm0dey
    13.05.2015 15:14
    #8415607
    Спасибо, разрыв между streamExParallel и streamParallel впечатляет. А за счёт чего он достигается?
    
    lany Автор
    13.05.2015 17:29
    #8415841
    Точно не знаю. Могу предположить, что из-за трёхкратного чтения каждого элемента из списка — слишком много проверок границ. В принципе его можно переписать, чтобы третий раз не требовался, но будет менее красиво выглядеть. В моём случае из исходного списка чтение ведётся его родным сплитератором, каждый элемент один раз.
    
    asm0dey
    13.05.2015 18:59
    #8416003
    Другими словами, когда мне придётся работать не только со следующим элементом, но и с обоими соседями — StreamEx уже не поможет?
    
    lany Автор
    13.05.2015 19:18
    #8416043
    Да, текущая реализация работает конкретно с парами. Судя по моей практике, это самое частое, что требуется. Есть мысль добавить синтаксический сахар типа такого:
    
    public static <T> StreamEx<List<T>> slide(List<T> source, int size) { return IntStreamEx.range(source.size()-size+1).mapToObj(idx -> source.subList(idx, idx+size)); }
    
    То есть поток всех подсписков данного списка длины size. Тогда, например, задача из статьи будет так решаться:
    
    slide(input, 2).filter(list -> list.get(0) < list.get(1)).map(list -> list.get(0)).toList();
    
    Но это завязка на то, что источник — список с быстрым случайным доступом. Ну и всё же помедленнее будет работать для окна 2. Сделать же сплитератор, который хорошо параллелится и работает с окном произвольной длины не так тривиально. Да и придётся всё равно складывать элементы в промежуточный контейнер типа списка, это некрасиво. В общем, тут есть над чем подумать, многое может зависеть от пожеланий пользователей и их конкретных задач.
    
    asm0dey
    13.05.2015 19:23
    #8416051
    Ага, понял, спасибо за объяснение. Как мне кажется добавить реализацию хотя бы для трёх стоит — два крайних являются контекстом для центрального.
    
    asm0dey
    13.05.2015 19:26
    #8416057
    Придётся встать второй раз всё-таки. Мне кажется суперполезным было бы StreamEx.of(ResultSet). А то до JDBC функционадбные плюшки не добрались…
    
    А, и в случае, если вы будете реализовывать slide — вероятно стоит использовать не листы, а Tuple2,3 итд. С аксессорами из серии get1, get2 итд.
    
    lany Автор
    13.05.2015 19:52
    #8416113
    +1
    С ResultSet вообще сложно. Во-первых, параллелить его нельзя. Во-вторых, там по факту один и тот же объект на каждой итерации, но в разном состоянии. Многие операции становятся бессмысленны. В-третьих, нередко его надо обязательно закрыть, то есть поток придётся оборачивать в try-with-resources. В-четвёртых, любая операция над ResultSet кидает SQLException, который checked. Вообще у JDBC интерфейс исключительно корявый. Эту проблему вроде неплохо пытается решить jOOQ, но проприетарщина.
    
    У меня есть в приватном проекте метод с такой сигнатурой:
    
    @FunctionalInterface public interface ResultSetMapper<T> { T map(ResultSet rs) throws SQLException; } public static <T> StreamEx<T> stream(Connection c, String query, ResultSetMapper<T> transformer) {...}
    
    Предполагается, что мы сразу мэпим запись в ResultSet на что-нибудь другое и уже из этого делаем поток. Но это всё равно довольно коряво. Во всяком случае, в StreamEx я не буду пихать JDBC, это слишком специфичная штука.
    
    И вот типы с туплами создавать не хочу, потому что это навязывание своих типов чужому приложению. В куче приложений и библиотек уже есть разнообразные туплы и создавать свои мне кажется коряво. По-моему, это не Java way. С pairMap я как раз обошёлся изящно — не стал новый тип создавать, а просто вызываю пользовательскую функцию, пользователь может использовать любой свой тип. А вот для троек уже пришлось бы объявлять свой функциональный интерфейс, потому что стандартного такого с тремя аргументами нет. Опять же надо чтобы была реальная задача, в которой этот функционал очень нужен, тогда будет понятнее, как его лучше реализовать. На пары самая типичная задача — получить попарные разности. Это легко решается с помощью StreamEx. А вот на тройки я пока не видел, где бы они пригодились…
    
    asm0dey
    13.05.2015 21:28
    #8416439
    +1
    Кстати, у создателей jOOQ есть такая штука, как jOOL. Там как раз есть рбота с JDBC. Но вот две библиотеки с разной реализацией функциональщины тянуть в проект не хочется…
    
    lany Автор
    14.05.2015 05:40
    #8416791
    +1
    О, спасибо, забыл совсем про jOOL. Она действительно на StreamEx похожа больше, чем protonpack, и имеет свою концепцию. Но тоже плюют на параллелизм даже там, где можно было бы не плевать. Плюс там есть вещи, которые в мою философию не вписываются. Например, метод Seq.reverse, который вычитывает поток в список и по этому списку создаёт новый поток (причём всегда последовательный вне зависимости от исходного). То есть это и не intermediate, и не terminal операция. Лучше уж коллектор написать типа toReverseList().
    
    Вот над всякими skipWhile/limitWhile я давно думаю, но с параллелизмом они не дружат, поэтому, видимо, у меня их не будет. Но вообще пару идей оттуда можно стырить :-)
    
    asm0dey
    14.05.2015 06:57
    #8416815
    +1
    Мне кажется, что универсальность библиотеки важнее чистого параллелизма. Потому что выбор между универсальной и быстрой библиотеками не очевиден, в то время каку выбор между двумя универсальными библиотеками, одна из которых ещё и паралеллится — очевиден.
    
    Кстати, ещё есть такой зверь, как javaslang. Дока там не очень, но интересные штуки есть. Хотя там всё-таки больше не про коллекции/стримы, а про монады с функторами.
    
    lany Автор
    14.05.2015 07:59
    #8416847
    +1
    Поглядел javaslang. Забавная штука. Сурово, что они свой класс назвали Stream, как бы призывая отказаться от стандартных стримов вообще.
    
    Я каждую фичу в библиотеке взвешиваю со множества позиций. Насколько она вписывается в общую концепцию? Что потеряют люди, которые её не используют (как минимум вырастет объём библиотеки, и у них увеличится размер их приложения)? Насколько она полезна в реальной жизни? Есть ли альтернативные пути решения задачи, которая решается с помощью этой фичи? Мне кажется, сперва должна быть задача, а потом уже под неё затачивать инструмент, чем придумывать универсальный швейцарский нож на 124 инструмента, который трудно держать в руке и из которых 112 инструментов никому не нужны.
    
    Вот свежий пример. Увидел, что в jOOL и в javaslang есть intersperse — вставить определённый элемент между каждой парой элементов потока. У меня в голове уже есть картинка, как это реализовать с помощью сплитератора. Будет хороший параллельный сплитератор, будет красивая intermediate-операция, которая укладывается в концепцию, супер. Но придётся писать эту операцию для четырёх типов потока (объектный и три примитивных), это увеличит итоговый jar килобайта на 3-4. А есть ли польза от этой операции? Единственное, что я могу придумать — это join строк с разделителем, но с этим легко справляется уже существующий коллектор. Если я найду в реальной жизни задачу, где intersperse полезен, или мне её кто-то покажет, я добавлю эту фичу.
    
    leventov
    14.05.2015 14:53
    #8417479
    +1
    Еще для полной картины есть такая реализация «идеи стримов с нуля»: GS collections. Посмотри API, идеи в реализации. Вот презентация, где они рассказывают, почему стримы сосут по сравнению с ними: www.slideshare.net/InfoQ/parallellazy-performance-java-8-vs-scala-vs-gs-collections
    
    lany Автор
    14.05.2015 15:51
    #8417595
    Спасибо, очень интересно.
    
    С count() в Java 8 вообще смешно. Сделайте LongStream.range(0, 1000000000).count(), и он реально будет думать! В JDK 9 это всё переписали, к счастью — отдельную операцию сделали для подсчёта. Вероятно с девяткой результаты тестов уже будут другие.
    
    Можно, кстати, попытаться переписать через forEach и LongAdder и посмотреть, сколько это займёт. Может, на восьмёрке и будет быстрее. Вообще на практике count не очень часто нужен.
    
    Поддержка кастомных ForkJoinPool'ов у меня есть =)
    
    dougrinch
    14.05.2015 16:48
    #8417745
    Но придётся писать эту операцию для четырёх типов потока
    
    А зачем? Я подобную задачу решал через генерацию. Причем, даже без непосредственно генератора. Писал одну объектную реализацию, а затем, по ней, генерил остальные.
    
    lany Автор
    14.05.2015 18:09
    #8417927
    Там не так много кода, чтобы заморачиваться с генерацией. Вон PairSpliterator гляньте, примерно такой же объём. Каждая специфичная реализация — строк 50, копипаста с заменой типов. Так что нет большой проблемы написать и поддерживать это вручную.
    
    Другое дело, что это компилируется в 5 class-файлов, которые зипуются в jar независимо, поэтому в зазипованном виде это 5.8 Кб. Настолько из-за одной фичи pairMap увеличивается размер библиотеки и размер дистрибутива приложения, которое её использует, даже если pairMap не нужен. К этому надо ответственно подходить. Одно дело дополнительный метод, который съест байт 100, над ним можно долго не думать.
    
    asm0dey
    14.05.2015 20:31
    #8418121
    Я дико извиняюсь, но кого в наше время вообще волнует итоговый размер приложения? Хоть там мегабайт пуска будет — лишь бы работало хорошо и быстро…
    
    dougrinch
    14.05.2015 20:55
    #8418149
    Это пока Вы не попытаетесь запихнуть скалу в андроид.
    
    Но в целом согласен, за исключением мобильных и embedded устройств, действительно пофиг на размер.
    
    asm0dey
    14.05.2015 21:27
    #8418179
    Со скалой всё не так просто, но дело тут вовсе не в размере. Дело там, ЕМНИП, в количестве классов, которое не умеет далвик. Раньше лечилось прогардом, думаю, что и сейчас тоже. А ежеди у вас один класс на 30 метров скомпилированного кода — то оно может и не очень хорошо, н андроид наверное справится.
    
    /me задумался, как бы зафигачить такой класс и какого же размера будут исходники…
    
    dougrinch
    14.05.2015 22:01
    #8418221
    Почти. Не классы, а методы. И не далвик, а dex. Вот и вот. Так что формально, да, дело не в размере. Но по факту, что-то мне подсказывает, что зависимость «кол-во методов от размера байткода» линейная.
    
    asm0dey
    14.05.2015 23:10
    #8418321
    Ух ты, как меня память-то подвела. Ну 65к это тоже достаточно, как мне кажется.
    
    lany Автор
    15.05.2015 11:38
    #8418991
    А пять старушек — уже пять рублей. Я ставлю вопрос по-другому: зачем добавлять фичу, которая никому не нужна? Покажите хоть один реальный пример использования аналогичной функции в любом языке. Я честно рылся на GitHub. Везде или учебные примеры, или join строк.
    
    Полезнее для практики, кстати, написать коллектор, который бы мог поток «Foo», «Bar», «Baz» собрать в строку «Foo, Bar, and Baz» со вставкой слова «and» перед последним элементом. Ещё полезно написать коллектор, который соберёт в «Foo, Bar, ...» при заданной максимальной длине строки. Думаю пока, можно ли всё это подружить с параллелизмом, какой конкретно должен быть интерфейс у методов и насколько это востребовано.
    
    lany Автор
    14.05.2015 08:16
    #8416851
    +2
    С другой стороны «под давлением общественности» я сделал foldRight/scanRight, хотя их можно начать выполнять только после того как закончатся выполняться все остальные шаги. По факту это нужно весьма редко, но раз есть foldLeft/scanLeft, то для симметрии стоило добавить. В jOOL, кстати, foldLeft ужасно реализован: они идут итератором по исходному потоку.

leventov
13.05.2015 16:43
#8415763
Еще заслуживает внимания проектик по улучшению стримов: github.com/poetix/protonpack
1. lany Автор
  13.05.2015 17:25
  #8415833
  +1
  Да, я на него в статье сослался =)
  
  Он мне совсем не нравится. Там концепции нет. Какое-то разрозненное месиво функционала. Ну и плюют на производительность и параллелизм.

Пишем свой Spliterator +21

Что же такое сплитератор

Когда сплитератор писать не надо

И всё-таки напишем

Переходим к сути дела

Всё это, небось, сильно тормозит?

Комментарии (26)

lany Автор

lany Автор

lany Автор

lany Автор

lany Автор

lany Автор

lany Автор

lany Автор

lany Автор

lany Автор

lany Автор