Skip to main content

Java 8 Lambdas applied to QuickSort algorithm

In this article I'm going to review Java 8 Lambdas use cases after I've watched the Lambdas have come to Java! screencast from Typesafe. As a nice example, I've decided to count comparisons in the Quicksort algorithm.
  1. Basic algorithm.
  2. Inline lambdas.
  3. Method references.
Basic algorithm
Here is a basic implementation where we count comparisons in the Quicksort algorithm:
public class QuickSort {
    public static long countComparisons(List<Integer> a) {
        if (a.size() <= 1) return 0;
        int p = getPivot(a);
        int i = 1;
        for (int j = 1; j < a.size(); j++) {
             if (a.get(j) < p) {
                 if (j > i) swapInList(a, i, j);
                 i++;
             }
        }
        swapInList(a, 0, i - 1);
        return countComparisons(a.subList(0, i - 1)) +
                countComparisons(a.subList(i, a.size())) + a.size() - 1;
    }

    private static Integer getPivot(List<Integer> a) {
        return a.get(0);
    }

    private static void swapInList(List<Integer> a, int i, int j) {
        int temp = a.get(j);
        a.set(j, a.get(i));
        a.set(i, temp);
    }
}
Above the getPivot method is a crucial point of the Quicksort algorithm. The choice of pivot affects the algorithm performance. So I'd like to be able to provide an external implementation of this method and use "median of three" rule, for example. This rule means choosing the median of the first, middle and last element as a pivot.

Inline lambdas
First let's use lambdas in the straightforward way. This is what QuickSort.countComparisons method will look like:
public static long countComparisons(List<Integer> a,
                                    Function<List<Integer>, Integer> getPivot) {
    if (a.size() <= 1) return 0;
    int p = getPivot.apply(a);
    int i = 1;
    for (int j = 1; j < a.size(); j++) {
         if (a.get(j) < p) {
             if (j > i) swapInList(a, i, j);
             i++;
         }
    }
    swapInList(a, 0, i - 1);
    return countComparisons(a.subList(0, i - 1), getPivot) +
            countComparisons(a.subList(i, a.size()), getPivot) + a.size() - 1;
}
And here are the unit tests:
public class TestQuickSort {
    private List<Integer> unsorted;

    @Before
    public void setUp() {
        unsorted = Arrays.asList(9, 5, 1, 10, 6, 3, 2, 9, 3, 2);
    }

    @Test
    public void testFirstAsPivot() {
        Assert.assertEquals(22, QuickSort.countComparisons(unsorted, a -> a.get(0)));
    }

    @Test
    public void testLastAsPivot() {
        Assert.assertEquals(23, QuickSort.countComparisons(unsorted, a -> {
            QuickSort.swapInList(a, 0, a.size() - 1);
            return a.get(0);
        }));
    }

    @Test
    public void testMedianOfThreeAsPivot() {
        Assert.assertEquals(21, QuickSort.countComparisons(unsorted, a -> {
            int l = a.get(0), m = a.get((a.size() - 1) / 2), r = a.get(a.size() - 1);
            if ((m >= l && m <= r) || (m >= r && m <= l)) {
                QuickSort.swapInList(a, 0, (a.size() - 1) / 2);
            } else if ((r >= l && r <= m) || (r >= m && r <= l)) {
                QuickSort.swapInList(a, 0, a.size() - 1);
            }
            return a.get(0);
        }));
    }
}
Now all this is cool except that it's hard to debug, maintain and reuse. So if there is an exception being thrown from inside the lambda, you'll see rather cryptic stacktrace using anonymous class syntax. For example, let's add division by zero to a lambda and see the stacktrace:
@Test
public void testFirstAsPivot() {
    Assert.assertEquals(22, QuickSort.countComparisons(unsorted, a -> a.get(0) / 0));
}

java.lang.ArithmeticException: / by zero
 at TestQuickSort.lambda$testFirstAsPivot$0(TestQuickSort.java:22)
 at TestQuickSort$$Lambda$2/1766822961.apply(Unknown Source)
 at QuickSort.countComparisons(QuickSort.java:71)
 at TestQuickSort.testFirstAsPivot(TestQuickSort.java:22)
Not a big issue some will say. But in the next section let's refactor the lambdas into methods and use method references.

Method references
First let's move the choice of pivot logic to a separate class:
public class PivotChoice {
    public static Integer getFirst(List<Integer> a) {
        return a.get(0);
    }

    public static Integer getLast(List<Integer> a) {
        QuickSort.swapInList(a, 0, a.size() - 1);
        return a.get(0);
    }

    public static Integer getMedianOfThree(List<Integer> a) {
        int l = a.get(0), m = a.get((a.size() - 1) / 2), r = a.get(a.size() - 1);
        if ((m >= l && m <= r) || (m >= r && m <= l)) {
            QuickSort.swapInList(a, 0, (a.size() - 1) / 2);
        } else if ((r >= l && r <= m) || (r >= m && r <= l)) {
            QuickSort.swapInList(a, 0, a.size() - 1);
        }
        return a.get(0);
    }
}
Second let's update the unit tests:
@Test
public void testFirstAsPivot() {
    Assert.assertEquals(22, QuickSort.countComparisons(unsorted, PivotChoice::getFirst));
}

@Test
public void testLastAsPivot() {
    Assert.assertEquals(23, QuickSort.countComparisons(unsorted, PivotChoice::getLast));
}

@Test
public void testMedianOfThreeAsPivot() {
    Assert.assertEquals(21, QuickSort.countComparisons(unsorted, PivotChoice::getMedianOfThree));
}
Now it already looks much prettier. But let's again add division by zero at the same place and see the stacktrace:
public static Integer getFirst(List<Integer> a) {
    return a.get(0) / 0;
}

java.lang.ArithmeticException: / by zero
 at PivotChoice.getFirst(PivotChoice.java:8)
 at TestQuickSort$$Lambda$2/1496724653.apply(Unknown Source)
 at QuickSort.countComparisons(QuickSort.java:29)
 at TestQuickSort.testFirstAsPivot(TestQuickSort.java:22)
The stacktrace looks much more readable now. Besides when using method references, you cannot close over variables as you definitely can with lambdas. It makes the code less error-prone.

Comments

Popular posts from this blog

DynamicReports and Spring MVC integration

This is a tutorial on how to exploit DynamicReports reporting library in an existing Spring MVC based web application. It's a continuation to the previous post where DynamicReports has been chosen as the most appropriate solution to implement an export feature in a web application (for my specific use case). The complete code won't be provided here but only the essential code snippets together with usage remarks. Also I've widely used this tutorial that describes a similar problem for an alternative reporting library.
So let's turn to the implementation description and start with a short plan of this how-to:
Adding project dependencies.Implementing the Controller part of the MVC pattern.Modifying the View part of the MVC pattern.Modifying web.xml.Adding project dependencies
I used to apply Maven Project Builder throughout my Java applications, thus the dependencies will be provided in the Maven format.

Maven project pom.xml file:
net.sourceforge.dynamicreportsdynamicrepo…

Choosing Java reporting tool - part 2

I've provided a general overview of possible solutions to get a reporting/exporting functionality in the previous post. This is the second overview of alternatives based on JasperReports reporting engine.

Since the previous part I've done the following:
Implemented a simple report using both DynamicJasper and DynamicReports to compare them from technical side.Investigated JasperServer features and tried to implement a simple report for JasperServer instance (it appeared we already have a ready licensed installation of JasperServer that makes it unreasonable to install a fresh one).
First, the comparison results of Java libraries (DynamicJasper and DynamicReports):
Both libraries suffer from poor-quality or missing Java docs but they look a bit better in DynamicJasper.Taking into account the point 1, a developer has to use online documentation and to review the code. Here the code looks definitely nicer and more readable for DynamicReports. With respect t…

Do It Yourself Java Profiling

This article is a free translation of the Russian one that is a transcript of the Russian video lecture done by Roman Elizarov at the Application Developer Days 2011 conference.
The lecturer talked about profiling of Java applications without any standalone tools. Instead, it's suggested to use internal JVM features (i.e. threaddumps, java agents, bytecode manipulation) to implement profiling quickly and efficiently. Moreover, it can be applied on Production environments with minimal overhead. This concept is called DIY or "Do It Yourself". Below the lecture's text and slides begin.
Today I'm giving a lecture "Do It Yourself Java Profiling". It's based on the real life experience that was gained during more than 10 years of developing high-loaded finance applications that work with huge amounts of data, millions currency rate changes per second and thousands of online users. As a result, we have to deal with profiling. Application profiling is an i…