Как построить более эффективный функциональный код?Java FP

Question

, поскольку я тренируюсь с проектом Эйлера, я едва нашел способ решить проблему № 5 с функциональным подходом.

Цель состоит в том, чтобы найти число, которое делится на все целые числа от 2 до 20.

Сначала я решил ее с помощью классической Java (я знаю, что мой код не очень хороший, и мне очень жаль), затем я хотел получить результат с FP, думая, что эффективность будет выше.

Обычному старому java потребовалось 750 мс, чтобы найти результат. Поток / FP занял около 750 мс.

Есть ли у вас какие-либо идеи / объяснения о том, почему путь FP требует так много времени для завершения? Полагаю, мой код не самый лучший, ни старый Java, ни FP.

Но я бы хотел понять, где я, безусловно, сделал что-то не так.

Обратите внимание, что распараллеливание потоковой обработки выигрывает около 130 мс (750 мс -> 620 мс).

Примечание 2: было бы неплохо начать с 9699690L (то есть: 2*3*5*7*9*11*13*17*19), но кажется, что приложение (как для Plain Old Java, так и для FP) запускается ... Почему ??

Вот простой код Java:

@Test
    void test() {
        long start = System.currentTimeMillis();
        boolean foundValue = false;
        long valueToFindOut = 20L;
        List<Long> divisors = Arrays.asList(2L, 3L, 4L, 5L, 6L, 7L, 8L, 9L, 10L, 11L, 12L, 13L, 14L, 15L, 16L, 17L, 18L,
                19L, 20L);

        while (!foundValue) {
            boolean found = false;
            for (long div : divisors) {
                if (isDivisible(valueToFindOut, div)) {
                    found = true;
                } else {
                    found = false;
                    break;
                }
            }
            if (!found) {
                valueToFindOut += 20L;
            } else {
                foundValue = true;
                System.out.println("Valeur trouvée = " + valueToFindOut);
            }
        }
        for (long div : divisors) {
            assertTrue(isDivisible(valueToFindOut, div));
        }
        long end = System.currentTimeMillis();
        System.out.println("Résultat obtenu en " + (end - start) + " millisecondes");
    }

private boolean isDivisible(long toDivide, long divisor) {
        return toDivide % divisor == 0;
    }

Функциональный код следующий:

@Test
    void testLambda() {
        long start = System.currentTimeMillis();
        List<Long> divisors = Arrays.asList(2L, 3L, 4L, 5L, 6L, 7L, 8L, 9L, 10L, 11L, 12L, 13L, 14L, 15L, 16L, 17L, 18L,
                19L, 20L);
        Predicate<Long> predicate = longPredicate(divisors);
        long result = generateLongStream().filter(predicate).findFirst().get();
        long end = System.currentTimeMillis();
        System.out.println("Resultat = " + result + " obtenu en " + (end - start) + " millisecondes.");
    }

    private boolean isDivisible(long toDivide, long divisor) {
        return toDivide % divisor == 0;
    }

    private Stream<Long> generateLongStream() {
        return Stream.iterate(20L, l -> l + 20L).parallel();
    }

    private Predicate<Long> longPredicate(List<Long> longs) {
        long start = System.currentTimeMillis();
        Predicate<Long> predicate = null;
        if(!(longs.isEmpty())) {
            List<Predicate<Long>> predicates = new ArrayList<Predicate<Long>>(longs.size());
            longs.forEach(divisor -> {
                predicates.add(valueToTest -> isDivisible(valueToTest, divisor));
            });
            for(int i = 0; i < predicates.size(); i++) {
                if(i == 0) {
                    predicate = predicates.get(i);
                } else {
                    predicate = predicate.and(predicates.get(i));
                }
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("Predicate construit en " + (end - start) + " millisecondes.");
        return predicate;
    }

Заранее благодарим за все ваши советы.

Answer 1

Мы можем заменить цикл над списком вещей ...

for( Thing thing : things ){
    process(thing);
}

... с чем-то более функциональным ....

things.forEach( thing -> process( thing ) );

... но то, что на самом деле происходит, очень похоже: мы должны перебрать список, вызывая метод process для каждого элемента списка. Функциональная версия может даже быть немного медленнее, потому что есть дополнительный вызов метода лямбда перед вызовом полезного метода.

Так что я не думаю, что это удивительно, что функциональная версия требует времени, аналогичного оригиналу.

Преимущество функциональной версии может быть

• немного короче
• Возможно, вам будет легче читать
• лямбда может быть получена откуда-то еще (скажем, как метод параметр)
• лямбда нуждается в значительно меньшем количестве стандартного кода, чем анонимные внутренние классы

Но ни один из них не поможет спектаклю.

Answer 2

Сначала я отвечу на мой комментарий: вам следует избегать Long и отдавать предпочтение лонгу при работе с алгоритмом на основе long.

Вы никогда не должны игнорировать стоимость (не) боксерской операции: я переписал ваш код, используя long, long[], LongPredicate и LongStream, и на моем Ryzen 7 2700X потребовалось следующее:

┌─────────────────┬───────┐
│     Method      │ Time  │
├─────────────────┼───────┤
│ LongStream      │ 129ms │
│ Old Java (Long) │ 336ms │
│ Old Java (long) │ 273ms │
└─────────────────┴───────┘

Реализация приведена ниже (извините, если это слишком долго. Я не знаю, как прикрепить файл к Stackoverflow, и я не думаю, что pastebin подойдет).

Метод LongStream является здесь победителем, но я думаю, что тест неверен:

• Вы никогда не должны жечь, используя System::currentTimeMillis. Этот метод возвращает текущее время, которое может измениться (скажем, часы были настроены из-за NTP). Вы должны использовать System::nanoTime.
• Вы выполняете одно исполнение в какое-то случайное время. Таким образом, вы не получите четкого понимания того, что делает работу лучше.
• Вы не имеете права на жим: вы должны использовать JMH ("Java Microbenchmark Harness"). Этот учебник , который может быть устаревшим (по крайней мере, архетип мавена), может помочь вам понять, что такое эталонный тест.

Метод longPredicate выполняет слишком много работы:

• Вам не нужно преобразовывать List<Predicate>, чтобы затем преобразовать его в один Predicate.
• Вы можете просто инициализировать исходный предикат и вызвать predicate = predicate.and(...).

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

for (int i = 1; i < longs.length; ++i) {
  predicate = predicate.and(n -> isDisivisble(n, longs[i])); // fail because i is not final
}

Вы также можете создать новую локальную переменную (это делается с помощью параметра в моем методе.)

Итак, вот результат, полученный от JMH:

┌─────────────────────────────────┬────────┬───────┬───────────┬───────────┬────────┐
│ Benchmark                       │  Mode  │  Cnt  │  Score    │  Error    │  Units │
├─────────────────────────────────┼────────┼───────┼───────────┼───────────┼────────┤
│ PlainOldJavaLongPrimitive.test  │  avgt  │  10   │  188,072  │    1,002  │  ms/op │
│ PlainOldJavaLongWrapper.test    │  avgt  │  10   │  265,649  │    0,920  │  ms/op │
│ StreamLongPrimitive.testLambda  │  avgt  │  10   │   86,046  │    1,829  │  ms/op │
│ StreamLongWrapper.testLambda    │  avgt  │  10   │  230,158  │   34,122  │  ms/op │
│ PlainOldJavaLongPrimitive.test  │  ss    │  10   │  198,192  │   37,573  │  ms/op │
│ PlainOldJavaLongWrapper.test    │  ss    │  10   │  268,587  │    7,378  │  ms/op │
│ StreamLongPrimitive.testLambda  │  ss    │  10   │  116,108  │   65,161  │  ms/op │
│ StreamLongWrapper.testLambda    │  ss    │  10   │  532,534  │  335,032  │  ms/op │
└─────────────────────────────────┴────────┴───────┴───────────┴───────────┴────────┘

• Вы можете заметить, что использование примитива лучше, чем оболочки.
• Вы можете наблюдать, как Stream лучше, чем "обычная старая Java".

-

Чтобы запустить этот проект JMH:

• Убедитесь, что у вас есть Maven 3.6.1 .
• Убедитесь, что у вас Java 11
• Скомпилируйте проект: mvn install
• Запустить тест: java -jar target/microbenchmarks.jar -rff bench

Файлы:

• / pom.xml
• / SRC / главная / Java / COM / StackOverflow / nodatafound / q56622173 / PlainOldJavaLongPrimitive.java
• / SRC / главная / Java / COM / StackOverflow / nodatafound / q56622173 / PlainOldJavaLongWrapper.java
• / SRC / главная / Java / COM / StackOverflow / nodatafound / q56622173 / StreamLongPrimitive.java
• / SRC / главная / Java / COM / StackOverflow / nodatafound / q56622173 / StreamLongWrapper.java

/ pom.xml

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
  <modelVersion>4.0.0</modelVersion>
  <groupId>com.stackoverflow.nodatafound</groupId>
  <artifactId>stackoverflow-56622173</artifactId>
  <version>1</version>
  <packaging>jar</packaging>

  <properties>
    <project.build.sourceEncoding>utf-8</project.build.sourceEncoding>
    <project.reporting.outputEncoding>${project.build.sourceEncoding}</project.reporting.outputEncoding>
    <maven.compiler.release>11</maven.compiler.release>
    <maven.compiler.source>11</maven.compiler.source>
    <maven.compiler.target>11</maven.compiler.target>
  </properties>

  <dependencies>
    <dependency>
      <groupId>org.openjdk.jmh</groupId>
      <artifactId>jmh-core</artifactId>
      <version>1.21</version>
    </dependency>
    <dependency>
      <groupId>org.openjdk.jmh</groupId>
      <artifactId>jmh-generator-annprocess</artifactId>
      <version>1.21</version>
    </dependency>
  </dependencies>

  <build>
    <plugins>
      <plugin>
        <groupId>org.apache.maven.plugins</groupId>
        <artifactId>maven-enforcer-plugin</artifactId>
        <version>3.0.0-M2</version>
        <executions>
          <execution>
            <id>enforce-maven</id>
            <inherited>true</inherited>
            <goals>
              <goal>enforce</goal>
            </goals>
            <configuration>
              <rules>
                <requireMavenVersion>
                  <version>[3.6.1,)</version>
                </requireMavenVersion>
                <requireJavaVersion>
                  <version>[11.0.0,)</version>
                </requireJavaVersion>
              </rules>
            </configuration>
          </execution>
        </executions>
      </plugin>
      <plugin>
        <groupId>org.apache.maven.plugins</groupId>
        <artifactId>maven-shade-plugin</artifactId>
        <version>3.2.1</version>
        <executions>
          <execution>
            <phase>package</phase>
            <goals>
              <goal>shade</goal>
            </goals>
            <configuration>
              <finalName>microbenchmarks</finalName>
              <transformers>
                <transformer implementation="org.apache.maven.plugins.shade.resource.ManifestResourceTransformer">
                  <mainClass>org.openjdk.jmh.Main</mainClass>
                </transformer>
              </transformers>
              <filters>
                <filter>
                  <artifact>*:*</artifact>
                  <excludes>
                    <exclude>META-INF/services/javax.annotation.processing.Processor</exclude>
                  </excludes>
                </filter>
              </filters>
            </configuration>
          </execution>
        </executions>
      </plugin>
    </plugins>
  </build>
</project>

/ SRC / главная / Java / COM / StackOverflow / nodatafound / q56622173 / PlainOldJavaLongPrimitive.java

package com.stackoverflow.nodatafound.q56622173;

import java.util.concurrent.TimeUnit;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;

@State(Scope.Benchmark)
@Warmup(iterations = 2)
@Fork(1)
@Measurement(iterations = 10)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@BenchmarkMode({ Mode.AverageTime, Mode.SingleShotTime })
public class PlainOldJavaLongPrimitive {

  @Benchmark
  public Object test() {
    boolean foundValue = false;
    long valueToFindOut = 20L;
    final long[] divisors = new long[] { 2L, 3L, 4L, 5L, 6L, 7L, 8L, 9L, 10L, 11L, 12L, 13L, 14L, 15L, 16L, 17L, 18L,
        19L, 20L };
    while (!foundValue) {
      boolean found = false;
      for (final long div : divisors) {
        if (isDivisible(valueToFindOut, div)) {
          found = true;
        } else {
          found = false;
          break;
        }
      }
      if (!found) {
        valueToFindOut += 20L;
      } else {
        foundValue = true;
      }
    }
    for (final long div : divisors) {
      if (!isDivisible(valueToFindOut, div)) {
        throw new AssertionError("valueToFindOut: " + valueToFindOut + ", div: " + div);
      }
    }
    return Long.valueOf(valueToFindOut);
  }

  private boolean isDivisible(final long toDivide, final long divisor) {
    return toDivide % divisor == 0;
  }
}

/ SRC / главная / Java / COM / StackOverflow / nodatafound / q56622173 / PlainOldJavaLongWrapper.java

package com.stackoverflow.nodatafound.q56622173;

import java.util.Arrays;
import java.util.List;
import java.util.concurrent.TimeUnit;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;

@State(Scope.Benchmark)
@Warmup(iterations = 2)
@Fork(1)
@Measurement(iterations = 10)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@BenchmarkMode({ Mode.AverageTime, Mode.SingleShotTime })
public class PlainOldJavaLongWrapper {

  @Benchmark
  public Object test() {
    boolean foundValue = false;
    long valueToFindOut = 20L;
    final List<Long> divisors = Arrays.asList(2L, 3L, 4L, 5L, 6L, 7L, 8L, 9L, 10L, 11L, 12L, 13L, 14L, 15L, 16L, 17L,
        18L, 19L, 20L);
    while (!foundValue) {
      boolean found = false;
      for (final long div : divisors) {
        if (isDivisible(valueToFindOut, div)) {
          found = true;
        } else {
          found = false;
          break;
        }
      }
      if (!found) {
        valueToFindOut += 20L;
      } else {
        foundValue = true;
      }
    }
    for (final long div : divisors) {
      if (!isDivisible(valueToFindOut, div)) {
        throw new AssertionError("valueToFindOut: " + valueToFindOut + ", div: " + div);
      }
    }
    return Long.valueOf(valueToFindOut);
  }

  private boolean isDivisible(final long toDivide, final long divisor) {
    return toDivide % divisor == 0;
  }
}

/ SRC / Основной / Java / ком / StackOverflow / nodatafound / q56622173 / StreamLongPrimitive.java

package com.stackoverflow.nodatafound.q56622173;

import java.util.concurrent.TimeUnit;
import java.util.function.LongPredicate;
import java.util.stream.LongStream;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;

@State(Scope.Benchmark)
@Warmup(iterations = 2)
@Fork(1)
@Measurement(iterations = 10)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@BenchmarkMode({ Mode.AverageTime, Mode.SingleShotTime })
public class StreamLongPrimitive {
  @Benchmark
  public Object testLambda() {
    final long[] divisors = new long[] { 2L, 3L, 4L, 5L, 6L, 7L, 8L, 9L, 10L, 11L, 12L, 13L, 14L, 15L, 16L, 17L, 18L,
        19L, 20L };
    final LongPredicate predicate = longPredicate(divisors);
    return generateLongStream().filter(predicate).findFirst().getAsLong();
  }

  private LongPredicate divisiblePredicate(final long divisor) {
    return n -> n % divisor == 0;
  }

  private LongStream generateLongStream() {
    return LongStream.iterate(20L, l -> l + 20L).parallel();
  }

  private LongPredicate longPredicate(final long[] longs) {
    if (longs.length == 0) {
      throw new IllegalArgumentException("Pas de diviseurs");
    }
    LongPredicate predicate = divisiblePredicate(longs[0]);
    for (int i = 1; i < longs.length; ++i) {
      predicate = predicate.and(divisiblePredicate(longs[i]));
    }
    return predicate;
  }
}

/ SRC / главная / Java / COM / StackOverflow / nodatafound / q56622173 / StreamLongWrapper.java

package com.stackoverflow.nodatafound.q56622173;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.TimeUnit;
import java.util.function.Predicate;
import java.util.stream.Stream;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;

@State(Scope.Benchmark)
@Warmup(iterations = 2)
@Fork(1)
@Measurement(iterations = 10)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@BenchmarkMode({ Mode.AverageTime, Mode.SingleShotTime })
public class StreamLongWrapper {
  @Benchmark
  public Object testLambda() {
    final List<Long> divisors = Arrays.asList(2L, 3L, 4L, 5L, 6L, 7L, 8L, 9L, 10L, 11L, 12L, 13L, 14L, 15L, 16L, 17L,
        18L, 19L, 20L);
    final Predicate<Long> predicate = longPredicate(divisors);
    return generateLongStream().filter(predicate).findFirst().get();
  }

  private boolean isDivisible(final long toDivide, final long divisor) {
    return toDivide % divisor == 0;
  }

  private Stream<Long> generateLongStream() {
    return Stream.iterate(20L, l -> l + 20L).parallel();
  }

  private Predicate<Long> longPredicate(final List<Long> longs) {
    if (longs.isEmpty()) {
      throw new IllegalArgumentException("Pas de diviseurs");
    }
    final List<Predicate<Long>> predicates = new ArrayList<>(longs.size());
    longs.forEach(divisor -> {
      predicates.add(valueToTest -> isDivisible(valueToTest, divisor));
    });
    Predicate<Long> predicate = predicates.get(0);
    for (int i = 1; i < predicates.size(); i++) {
      predicate = predicate.and(predicates.get(i));
    }
    return predicate;
  }
}