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.

**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

## Post a Comment