days
0
-9
hours
0
-1
minutes
-3
0
seconds
-4
-2
search
Interesting logic

Comparing imperative and functional algorithms in Java 8

Lukas Eder
Rubik's cube image via Shutterstock

Lukas Eder is excited about functional programming in Java 8, which he believes is becoming much like the expressive power of SQL-style declarative programming. Here he looks at the imperative and functional approaches available in Java 8.

This post was originally published over at jooq.org, a blog focusing on all things open source, Java and software development from the perspective of jOOQ.

Mario Fusco’s popular tweet impressively shows what the main difference between imperative and functional approaches to similar algorithms really is:

Both algorithms do the same thing, they’re probably equally fast and reasonable. Yet, one of the algorithms is much easier to write and read than the other. The difference lies in the fact that in imperative programming, different algorithmic requirements are spread throughout the code block, when in functional programming, each requirement has its own little line of code. Compare:

  • Green: Error handling
  • Blue: Stop criteria
  • Red: IO operations
  • Yellow: “Business logic”

Functional programming doesn’t always beat imperative programming as displayed in other examples on the jOOQ blog:

But here’s an example from Stack Overflow by user Aurora_Titanium, where the difference is as clear as in Mario Fusco’s example:

Calculating the Duplicate Values in an Array

The idea is to calculate the sum of all those values that are duplicate in a set of values. For instance, the following array:

int[] list = new int[]{1,2,3,4,5,6,7,8,8,8,9,10};

… should yield as a result something like:

Duplicate: 8. Sum of all duplicate values: 24

The imperative approach

One of the answers by user Volkan Ozkan takes an imperative approach and calculates the sum as such:

int[] array = new int[] {
    1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 9, 10
};

int sum = 0;
for (int j = 0; j < array.length; j++)
{
    for (int k = j + 1; k < array.length; k++)
    {
        if (k != j && array[k] == array[j])
        {
            sum = sum + array[k];
            System.out.println(
                "Duplicate found: "
              + array[k]
              + " "
              + "Sum of the duplicate value is " + sum);
        }
    }
}

The approach works only for sorted arrays where duplicates appear right after one another. In that case, however, it is probably an optimal solution in terms of performance, if performance really matters to this algorithm.

The functional approach

If a slight decrease of performance is acceptable to you (boxing ints, collecting them into maps), and it probably is, you can replace the above difficult-to-read code with the following bit of functional Java-8-style logic, which communicates much more clearly what it does:

int[] array = new int[] {
    1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 9, 10
};

IntStream.of(array)
         .boxed()
         .collect(groupingBy(i -> i))
         .entrySet()
         .stream()
         .filter(e -> e.getValue().size() > 1)
         .forEach(e -> {
             System.out.println(
                 "Duplicates found for : "
               + e.getKey()
               + " their sum being : "
               + e.getValue()
                  .stream()
                  .collect(summingInt(i -> i)));
         });

or, with explanations:

int[] array = new int[] {
    1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 9, 10
};

// Create a Stream<Integer> from your data
IntStream.of(array)
         .boxed()

// Group values into a Map<Integer, List<Integer>>
         .collect(groupingBy(i -> i))

// Filter out those map values that have only
// 1 element in their group
         .entrySet()
         .stream()
         .filter(e -> e.getValue().size() > 1)

// Print the sum for the remaining groups
         .forEach(e -> {
             System.out.println(
                 "Duplicates found for : "
               + e.getKey()
               + " their sum being : "
               + e.getValue()
                  .stream()
                  .collect(summingInt(i -> i)));
         });

(note that the functional approach calculates sums for each duplicate value, not an overall sum, like the imperative approach. From the original question, this requirement wasn’t very clear).

As we’ve stated in a previous article on our blog, the power of functional programming via an API like the Java 8 Stream API is the fact that we’re approaching the expressive power of SQL-style declarative programming. We’re no longer concerned with remembering individual array indexes and how to calculate them and store intermediate results into some buffers. We can now focus on the really interesting logic, such as: “what’s a duplicate?” or “what sum am I interested in?”

Read on about how SQL compares to Java 8 Streams here.

Author
Lukas Eder
Lukas is a Java and SQL aficionado. He’s the founder of Data Geekery GmbH, the company behind jOOQ, the best way to write SQL in Java.

Leave a Reply

Be the First to Comment!

avatar
400
  Subscribe  
Notify of