3
\$\begingroup\$

I am reading "Java 8 In Action" (by Raoul-Gabriel Urma, Mario Fusco and Alan Mycroft), section 5.6.3, pages 116 and 117. The code that is presented handles calculating so-called "Pythagorean Triples". Page 116 shows the first attempt, and page 117 shows an improved attempt to generate these triples, where both use the .rangeClosed() method.

I have found some optimizations that go beyond the book and I would like to share them here. I did some simple System.currentTimeMillis() calculations to see if my modifications were improvements, and they appeared to be marginally better than that found in the book. Can you provide better improvements, explanations or metrics for this code?

public void test() {

    long time1 = System.currentTimeMillis();

    /*
     * From text, page 116
     */
    IntStream.rangeClosed(1,  100).boxed()
        .flatMap(a -> IntStream.rangeClosed(a, 100)
                .filter(b -> Math.sqrt(a*a + b*b) % 1 == 0)
                .mapToObj(b -> new int[]{a, b, (int)Math.sqrt(a*a + b*b)})
        )
        .forEach(c -> System.out.println("["+c[0]+" "+c[1]+" "+c[2]+"]"));

    long time2 = System.currentTimeMillis();

    System.out.println();

    long time3 = System.currentTimeMillis();

    /*
     * From text, page 117, I added "map(...)" so that end result are ints, not doubles
     */
    IntStream.rangeClosed(1, 100).boxed()
        .flatMap(a -> IntStream.rangeClosed(a, 100)
                .mapToObj(b -> new double[]{a, b, Math.sqrt(a*a + b*b)})
                .filter(t -> t[2] % 1 == 0)
                .map(b -> new int[]{(int)b[0], (int)b[1], (int)b[2]})
        )
        .forEach(c -> System.out.println("["+c[0]+" "+c[1]+" "+c[2]+"]"));

    long time4 = System.currentTimeMillis();

    System.out.println();

    long time5 = System.currentTimeMillis();

    /*
     * My optimization attempt #1: now mapToObj(...) has c%1!=0 conditional, filter checks array element not null
     */
    IntStream.rangeClosed(1, 100).boxed()
    .flatMap(a -> IntStream.rangeClosed(a, 100)
                .mapToObj(b -> {
                    double c = Math.sqrt(a*a + b*b);
                    return new Object[]{a, b, c % 1 == 0 ? (int)c : null};
                })
                .filter(d -> d[2] != null)
                .map(e -> new int[]{(int)e[0], (int)e[1], (int)e[2]})
    )
    .forEach(f -> System.out.println("["+f[0]+" "+f[1]+" "+f[2]));

    long time6 = System.currentTimeMillis();

    System.out.println();

    long time7 = System.currentTimeMillis();

    /*
     * My optimization attempt #2: now mapToObj(...) has c%1!=0 conditional, filter checks "array element" not 0
     */
    IntStream.rangeClosed(1, 100).boxed()
        .flatMap(a -> IntStream.rangeClosed(a, 100)
                .mapToObj(b -> {
                    double c = Math.sqrt(a*a + b*b);
                    return new int[]{a, b, c % 1 == 0 ? (int)c : 0 };
                })
                .filter(t -> t[2] != 0)
        )
        .forEach(d -> System.out.println("["+d[0]+" "+d[1]+" "+d[2]+"]"));

    long time8 = System.currentTimeMillis();

    System.out.println();

    long time9 = System.currentTimeMillis();

    /*
     * My optimization attempt #3: now mapToObj(...) has c%1!=0 conditional, filter checks "collection element" not null
     */
    IntStream.rangeClosed(1, 100).boxed()
        .flatMap(a -> IntStream.rangeClosed(a, 100)
                .mapToObj(b -> {
                    double c = Math.sqrt(a*a + b*b);
                    return (c % 1 != 0) ? null : new int[]{a, b, (int)c};
                })
                .filter(t -> t != null)
        )
        .forEach(d -> System.out.println("["+d[0]+" "+d[1]+" "+d[2]+"]"));

    long time10 = System.currentTimeMillis();

    System.out.println();

    long timeDelta1 = time2 - time1;
    long timeDelta2 = time4 - time3;
    long timeDelta3 = time6 - time5;
    long timeDelta4 = time8 - time7;
    long timeDelta5 = time10 - time9;

    System.out.println("timeDelta1: " + timeDelta1 + ", timeDelta2: " + timeDelta2 + ", timeDelta3: " + timeDelta3 + ", timeDelta4: " + timeDelta4 + ", timeDelta5: " + timeDelta5);

}

public static void main(String[] args){
    ReduceTest reduceTest = new ReduceTest();
    reduceTest.test();
}

NOTE: It appears that you can use return in a .forEach() method, but not in a .mapToInt() method. Using return in the lambda passed into the .mapToInt() method would remove the need to have the .filter() method. It seems like that would be an improvement to the streams API.

\$\endgroup\$
2
\$\begingroup\$

What the original code does is, that it calculates the (relatively expensive) Math.sqrt(a * a + b * b) twice: once for filtering, the second time for generating the end result.

You eliminated this double calculation by caching the results, thus your code is a wee bit faster.

Note however, that the benchmark you did is probably not valid, I suggest reading the accepted answer in https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java as a starter.

Then, be aware that this micro-optimization only pays if you get into serious number crunching. As D.E.Knuth exclaimed (and it still holds true): "premature optimization is the root of all evil" (http://wiki.c2.com/?PrematureOptimization) so think twice before you optimize on that level.

Furthermore, if you are really serious about "the best" production code, this shuffeling around with two arrays seems akward: if you want a structure which holds two ints and a double, then create a structure with two ints and a double, give it a good name, and use that instead of arrays. This will eliminate the cast-int-to-double-and-back-to-int that you do and make the concept a bit clearer to the reader.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Much thanks for it. Agree with you about the benchmark, I don't know much about them. I understood the caching part, thank you, that was the whole point of my optimizations. Also, int[] array was in the original example, so going with that seemed fine, light-weight primitive. Calculation of ints into a double was unavoidable per the nature of squaring numbers. Also, the nature of the problem is to have "pythagorean triples" where all three values are int, not 2 ints and 1 double. See page 114 of the aforementioned book. I appreciate the use of value objects though, thank you. \$\endgroup\$ – Steve T Jan 22 '17 at 2:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.