DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Please enter at least three characters to search
Refcards Trend Reports
Events Video Library
Refcards
Trend Reports

Events

View Events Video Library

Zones

Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks

Modernize your data layer. Learn how to design cloud-native database architectures to meet the evolving demands of AI and GenAI workkloads.

Secure your stack and shape the future! Help dev teams across the globe navigate their software supply chain security challenges.

Releasing software shouldn't be stressful or risky. Learn how to leverage progressive delivery techniques to ensure safer deployments.

Avoid machine learning mistakes and boost model performance! Discover key ML patterns, anti-patterns, data strategies, and more.

Related

  • Infrastructure as Code: What You Need to Know
  • A Beginner's Guide to Infrastructure as Code: How IaC Works, Its Benefits, and Common Challenges

Trending

  • Unlocking the Benefits of a Private API in AWS API Gateway
  • Google Cloud Document AI Basics
  • Unlocking AI Coding Assistants Part 3: Generating Diagrams, Open API Specs, And Test Data
  • Integrating Security as Code: A Necessity for DevSecOps

From Functional to Imperative Programming

Sometimes optimizing an algorithm in specific ways can benefit from an imperative approach.

By 
Francisco Alvarez user avatar
Francisco Alvarez
DZone Core CORE ·
Nov. 26, 18 · Analysis
Likes (5)
Comment
Save
Tweet
Share
11.8K Views

Join the DZone community and get the full member experience.

Join For Free

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 2), 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:

Iteration Subsequences
1 [5]
2 [2]
3 [5,7]
[2,7]
[7]
4 [2,4]
[4]
5 [2,3]
[3]
6

[5,8]

[2,8]

[5,7,8]

[2,7,8]

[7,8]

[2,4,8]

[4,8]

[2,3,8]

[3,8]

[8]

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).

Iteration Subsequences
1 [5]
2 [2]
3 [2,7]
4 [2,4]
5 [2,3]
6

[2,3,8].

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

Iteration Subsequence length Subsequences
1 1 [5]
2 1 [2]
3 1 [2]
2 [2,7]
4 1 [2]
2 [2,4]
5 1 [2]
2 [2,3]
6 1 [2]
2 [2,3]
3

[2,3,8]


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.

Iteration Subsequence length Last element
1 1 5
2 1 2
3 1 2
2 7
4 1 2
1 4
5 1 2
2 3
6 1 2
2 3
3

8

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.

Imperative programming

Published at DZone with permission of Francisco Alvarez, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Related

  • Infrastructure as Code: What You Need to Know
  • A Beginner's Guide to Infrastructure as Code: How IaC Works, Its Benefits, and Common Challenges

Partner Resources

×

Comments
Oops! Something Went Wrong

The likes didn't load as expected. Please refresh the page and try again.

ABOUT US

  • About DZone
  • Support and feedback
  • Community research
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Core Program
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • support@dzone.com

Let's be friends:

Likes
There are no likes...yet! 👀
Be the first to like this post!
It looks like you're not logged in.
Sign in to see who liked this post!