Итерации, необходимые при цепочке промежуточных операций потока

avatar
Gayan Weerakutti
1 июля 2021 в 17:36
115
1
0

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

Например, следующие два примера делают одно и то же. Но во втором примере две промежуточные операции объединяются в одну.

myStream
     .map(s -> methodA(s))
     .map(s -> methodB(s))
     .collect(Collectors.joining());

myStream
     .map(s -> methodB(methodA(s)))
     .collect(Collectors.joining());

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

Источник
ernest_k
1 июля 2021 в 17:43
2

Вы имеете в виду сложность времени... не производительность или время выполнения? Очевидно, что временная сложность здесь будет такой же.

Gayan Weerakutti
1 июля 2021 в 17:44
0

Да, временная сложность. Как 2н, 3н. Не время выполнения.

luk2302
1 июля 2021 в 17:45
3

Время complexity не меняется, может быть, один раз вы запускаете N операций, другой раз N+N=2*N операций, но они по-прежнему O(N). Если вы разделите его на 100 операций, вы выполните 100 * N операций, что по-прежнему равно O (N).

Henry Twist
1 июля 2021 в 17:49
4

Говоря о сложности, O(2n), O(3n) и т. д. не имеют значения. Они оба просто O(n). Он представляет собой рост, а не фактическое время выполнения.

Gayan Weerakutti
1 июля 2021 в 17:51
0

@jrook Мой немного конкретнее. Я хочу знать, есть ли разница в количестве требуемых итераций.

Henry Twist
1 июля 2021 в 17:54
0

Количество итераций (время) сильно отличается от порядка, о чем вы говорите O(n) (рост) @GayanWeerakutti. Какой из них вы пытаетесь узнать?

Ole V.V.
1 июля 2021 в 17:58
1

Вы измеряли, сколько времени занимает каждый? Отвечает ли это на ваш вопрос? Как написать правильный микротест на Java?

jrook
1 июля 2021 в 18:04
1

@GayanWeerakutti Вот еще один ответ, говорит то же самое. Между оптимизацией горячих точек и другими окружающими условиями практически невозможно узнать теоретические аргументы.

Holger
1 июля 2021 в 18:08
4

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

Gayan Weerakutti
1 июля 2021 в 18:11
0

@Holger Я обновил вопрос. Меня больше интересует количество итераций.

Holger
1 июля 2021 в 18:12
2

Отвечая на ваш обновленный вопрос, оба варианта эквивалентны одному циклу.

Gayan Weerakutti
1 июля 2021 в 18:12
0

@jrook Спасибо. Это должно ответить на мой вопрос.

Gayan Weerakutti
1 июля 2021 в 18:29
0

@Holger Приятно знать. Ваш другой ответ - при использовании операций фильтра. Если у вас есть другой ответ на этот вопрос, с упором на количество итераций и тому подобное, я был бы рад снова открыть этот вопрос.

Ole V.V.
1 июля 2021 в 18:57
0

@GayanWeerakuttiI полагаю, что будет лучше задать новый вопрос только с той частью, на которую нет ответа в оригинале, на который есть ссылка. В свой новый вопрос включите ссылку на этот вопрос и/или на этот, чтобы прояснить разницу.

Gayan Weerakutti
2 июля 2021 в 05:06
0

@ОлеВ.В. Думаю, вопрос уже совсем в другом. Я несколько раз перефразировал. Но я не уверен, будет ли ответ таким же или нет. Могу ли я снова открыть его?

Gayan Weerakutti
2 июля 2021 в 05:26
0

В основном, я спрашиваю о количестве итераций. Как упомянул @Holger, это одинаково для обоих вариантов.

Ответы (1)

avatar
WJS
2 июля 2021 в 18:02
1

Я знаю, что промежуточные потоковые операции в Java ленивы и не выполняются до тех пор, пока не будет вызвана терминальная операция. Однако я не уверен, увеличивает ли цепочка промежуточных операций количество требуемых итераций. ... Разве количество итераций не одинаково в обоих случаях?

Следующее, похоже, подтверждает ваши (и другие) выводы. Я использовал AtomicInteger, поскольку при использовании параллельных потоков счет будет отключен. Ни в одном случае общее количество вызовов методов не отличалось. Однако, поскольку два метода возвращают разные значения, суммы будут отличаться из-за порядка карт. В первом случае MethodA обрабатывается последним, поэтому его значение будет суммироваться. Во втором случае MethodB обрабатывается последним, поэтому его значение будет суммироваться.

static AtomicInteger count = new AtomicInteger(0);
Random r = new Random();
for (int i = 0; i < 10000; i++) {
    count.set(0);
    List<Integer> list = IntStream.generate(
            () -> 1)
            .limit(r.nextInt(10) + 1).boxed().toList();
    
    int sum1 = list.stream().mapToInt(s -> methodB(s)).map(s -> methodA(s))
            .sum();
    
    int save = count.get();
    
    count.set(0);
    int sum2 = list.stream().mapToInt(s -> methodB(methodA(s)))
              .sum();
    if (save != count.get()) {
        System.out.println(
                "Inconsistent counts: " + save + " " + count);
    }
}
    
public static int methodA(int v) {
    count.incrementAndGet();
    return 1;
}

    
public static int methodB(int v) {
    count.incrementAndGet();
    return 2;
}