From Functional to Imperative Programming

In this post, we mentioned the need for taking into consideration the physical limitations of time and space when writing an algorithm. Today, we will show how the anatomy of an algorithm varies as successive optimizations are added. This change is reflected, especially, in the shift from a functional to an imperative style.

As we know, functional programming allows us to develop in a declarative way: specify to do and leave them to the computer. On the other hand, imperative programming cares about both.

As functional programming is focused on the what, it is better suited to solve problems at a higher level of abstraction. Whereas, the need for dealing with implementation details makes imperative programming more error-prone and the solutions less portable across different domains.

Having said that, optimizing an algorithm requires us to do things in a very specific way. In that case, only an imperative approach will do.

Longest Increasing Subsequence

To illustrate these ideas, let's consider the problem of the Longest Increasing Sequence (LIS).

As it is known, the standard solution is O(N ²), and there is an optimized version O(N logN).

Solution 1

Let's consider a first approach using functional programming. This approach builds all possible increasing subsequences and then selects the longest one.

def solution1(arr: List[Int]): List[Int] = {
  val subSequences: mutable.Set[List[Int]] = mutable.Set()

  arr.foreach { x =>
    subSequences ++= (subSequences
      .filter(_.head < x)
      .map(x :: _) match{
      case s if s.isEmpty => Set(List(x))
      case s => s
    })
  }
  subSequences.map(s => (s, s.size)).maxBy(_._2)._1.reverse
}

To see this solution in action, let's consider the array [5,2,7,4,3,8].

Below is the list of subsequences generated in each iteration over the array:

And the longest subsequences are: [5,7,8], [2,7,8], [2,4,8], [2,3,8]

The code is easy to understand, with no need of handling painful loop indices (although, there are two nested loops disguised in the methods "foreach" and "filter/map"). Given that the intermediate solutions are stored and used to build the new ones, this algorithm could be an example of dynamic programming.

However, this approach is too naive as generating so many subsequences makes the application run out of memory for inputs as small as 200 elements.

Solution 2

If we are only interested in getting any of the longest subsequences, we can apply our first optimization by concatenating each new element only to the longest of the previous subsequences (if there is more than one such subsequence, we take any one of them).

And here's the code, just a small variant over the previous solution and yet delivers a significant speed improvement and avoids running out of memory In this case, the number of subsequences is the same as the number of elements in the original array.

def solution2(arr: List[Int]): List[Int] = {

  val subSequences: mutable.Set[List[Int]] = mutable.Set()

  arr.foreach { x =>
    subSequences += (subSequences
      .filter(_.head < x)
      .map(l => (l,l.size)) match {
        case s if s.isEmpty => List(x)
        case s => x :: s.maxBy(_._2)._1
      })
  }
  subSequences.map(s => (s, s.size)).maxBy(_._2)._1.reverse
}

Solution 3

Despite the improvements introduced by solution 2, we are still calculating too many sequences. In the previous example, there are two sequences of size 1 and 3 of size 2. However, without loss of generality, we can keep just the sequence of each size ending with the smallest number. For instance, any increasing sequence built on top of [2,7] and [2,4] can also be built on top of [2,3]. Therefore we can keep just [2,3].

Here's the algorithm in action

And the code:

def solution3(arr: List[Int]) = {

  val subSequences: Array[List[Int]] = new Array(arr.size)
  subSequences(0) = List(arr(0))
  for(i <- Range(1,arr.size))
    subSequences(i) = List(Integer.MAX_VALUE)

  var maxIdx = 0
  for(i <- Range(1,arr.size)){
    var j = maxIdx
    while(j >= 0){
      if(subSequences(j).head < arr(i)) {
        subSequences(j + 1) = arr(i) :: subSequences(j)
        if(j == maxIdx) maxIdx += 1
        j = -1 //to break the loop
      }
      else if(j == 0){
        subSequences(0) = List(arr(i))
        j -= 1
      }
      else
        j -= 1
    }
  }

  subSequences.map(s => (s, s.size)).maxBy(_._2)._1.reverse
}

This is a great improvement! The total number of subsequences in memory is never greater than the number of elements of the LIS.

Unfortunately, we are forced to deal with the low-level handling of the loops, entering the realm of imperative programming and losing the simplicity of the functional version.

Note: an additional optimization introduced in this solution is to limit the loop over "subSequences" to those elements with actual values.

Solution 4

If we are just interested in knowing the length of the LIS, we can still go further into the optimization process. Looking at the above solution, it is clear that the only thing that we need to store is the last element of each sequence as the length of the LIS is given by maxIdx + 1.

This version is very similar to the previous one, and the improvement is not much:

def solution4(arr: List[Int]) = {

  val subSequences: Array[Int] = new Array(arr.size)
  subSequences(0) = arr(0)
  for(i <- Range(1,arr.size))
    subSequences(i) = Integer.MAX_VALUE

  var maxIdx = 0
  for(i <- Range(1,arr.size)){
    var j = maxIdx
    while(j >= 0){
      if(subSequences(j) < arr(i)) {
        subSequences(j + 1) = arr(i)
        if(j == maxIdx) maxIdx += 1
        j = -1
      }
      else if(j == 0){
        subSequences(0) = arr(i)
        j -= 1
      }
      else
        j -= 1
    }
  }
  maxIdx + 1
}

Solution 5

Although a small improvement, the previous version paved the way for the last optimization: replacement of the linear search with a binary search. The use of the binary search makes this solution O(N logN).

def solution5(arr: List[Int]) = {

  def binarySearch(arr: Array[Int], valueSearched: Int, lowerBound: Int, upperBound: Int): Int = {

    if(lowerBound > upperBound) lowerBound - 1
    else {
      val mid = (lowerBound + upperBound) / 2
      if (valueSearched <= arr(mid)) binarySearch(arr, valueSearched, lowerBound, mid - 1)
      else binarySearch(arr, valueSearched, mid + 1, upperBound)
    }
  }

  val subSequences: Array[Int] = new Array(arr.size+1)
  subSequences(0) = Integer.MIN_VALUE
  for(i <- Range(1,arr.size))
    subSequences(i) = Integer.MAX_VALUE

  var maxIdx = 0
  for(i <- Range(1,arr.size)){
    val idx = binarySearch(subSequences, arr(i), 0, maxIdx)
    subSequences(idx + 1) = arr(i)
    if(maxIdx < idx + 1) maxIdx = idx + 1
  }
  maxIdx
}

Examples

Here's the result of running the different solutions for different inputs randomly generated. "Solution 1" has been left out as it runs out of memory for inputs greater than 100.

Clearly, the results confirm the expected performance. For instance, for input 10000, the LIS has 198 elements and the times vary from the 36 seconds of solution 1 to 352 milliseconds of solution 5

**********************************
array length ==> 1000
**********************************
solution2 58
time2: 363
solution3 58
time3: 48
solution4 58
time4: 21
solution5 58
time5: 4

**********************************
array length ==> 2000
**********************************
solution2 85
time2: 795
solution3 85
time3: 129
solution4 85
time4: 131
solution5 85
time5: 14

**********************************
array length ==> 3000
**********************************
solution2 106
time2: 1965
solution3 106
time3: 354
solution4 106
time4: 335
solution5 105
time5: 19

**********************************
array length ==> 4000
**********************************
solution2 117
time2: 3341
solution3 117
time3: 953
solution4 117
time4: 980
solution5 117
time5: 55

**********************************
array length ==> 5000
**********************************
solution2 139
time2: 5953
solution3 139
time3: 1881
solution4 139
time4: 1872
solution5 139
time5: 88

**********************************
array length ==> 6000
**********************************
solution2 150
time2: 9043
solution3 150
time3: 2952
solution4 150
time4: 2957
solution5 150
time5: 131

**********************************
array length ==> 7000
**********************************
solution2 164
time2: 13542
solution3 164
time3: 3743
solution4 164
time4: 3717
solution5 164
time5: 180

**********************************
array length ==> 8000
**********************************
solution2 170
time2: 19721
solution3 170
time3: 5776
solution4 170
time4: 5740
solution5 170
time5: 240

**********************************
array length ==> 9000
**********************************
solution2 181
time2: 26030
solution3 181
time3: 8064
solution4 181
time4: 7942
solution5 181
time5: 299

**********************************
array length ==> 10000
**********************************
solution2 198
time2: 36755
solution3 198
time3: 9954
solution4 198
time4: 9750
solution5 198
time5: 352

The repository containing the source code in this post can be found on GitHub.