Почему фильтрация несортированного списка быстрее, чем фильтрация отсортированного списка

играл с Java 8Streams - API и я решил микробенчмаркstream() а такжеparallelStream() потоки. Как и ожидалосьparallelStream() был в два раза быстрее, но всплыло что-то еще - если я отсортирую данные, прежде чем передать ихfilter требуется в 5-8 раз больше времениfilter->map->collect результат, чем прохождение несортированного списка.

несортированный
(Stream) Elapsed time [ns] : 53733996 (53 ms)
(ParallelStream) Elapsed time [ns] : 25901907 (25 ms)
отсортированный
(Stream) Elapsed time [ns] : 336976149 (336 ms)
(ParallelStream) Elapsed time [ns] : 204781387 (204 ms)
Вот код
package com.github.svetlinzarev.playground.javalang.lambda;

import static java.lang.Long.valueOf;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;

import com.github.svetlinzarev.playground.util.time.Stopwatch;

public class MyFirstLambda {
    private static final int ELEMENTS = 1024 * 1024 * 16;

    private static List getRandom(int nElements) {
        final Random random = new Random();
        final List data = new ArrayList(nElements);
        for (int i = 0; i < MyFirstLambda.ELEMENTS; i++) {
            data.add(random.nextInt(MyFirstLambda.ELEMENTS));
        }
        return data;
    }

    private static void benchStream(List data) {
        final Stopwatch stopwatch = new Stopwatch();
        final List smallLongs = data.stream()
                .filter(i -> i.intValue() < 16)
                .map(Long::valueOf)
                .collect(Collectors.toList());
        stopwatch.log("Stream");
        System.out.println(smallLongs);
    }

    private static void benchParallelStream(List data) {
        final Stopwatch stopwatch = new Stopwatch();
        final List smallLongs = data.parallelStream()
                .filter(i -> i.intValue() < 16)
                .map(Long::valueOf)
                .collect(Collectors.toList());
        stopwatch.log("ParallelStream");
        System.out.println(smallLongs);
    }

    public static void main(String[] args) {
        final List data = MyFirstLambda.getRandom(MyFirstLambda.ELEMENTS);
        // Collections.sort(data, (first, second) -> first.compareTo(second)); //

Ответы на вопрос(1)

Ваш ответ на вопрос