Array and List recursion performance

Question

I solving the problem of "Best-time-to-buy-and-sell-stock" at leetcode https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/ with 2 approaches:

With first, I transformed Array to List and handle list recursively:

 def maxProfit(prices: Array[Int]): Int = {
 @tailrec
 def maxProfitHelp(prices: List[Int], maxProfit: Int, lastBuy: Int): Int = {
   prices match {
     case Nil => maxProfit
     case head :: tail => if (head > lastBuy)  {
       maxProfitHelp(tail, Math.max(maxProfit, head - lastBuy), lastBuy)
     } else {
       maxProfitHelp(tail, maxProfit, head)
     }
   }
 }

 val listPrices = prices.toList
 maxProfitHelp(listPrices.tail, 0, listPrices.head)
}

This gave time performance 962 ms. (Memory: 71,70 MB)

With second I tried to handle original array in the same recursive manned.

def maxProfitWithoutList(prices: Array[Int]): Int = {
  @tailrec
  def maxProfitHelp(prices: Array[Int], maxProfit: Int, lastBuy: Int): Int = {
   prices match {
    case c if c.isEmpty => maxProfit
    case c => if (c.head > lastBuy)  {
     maxProfitHelp(c.tail, Math.max(maxProfit, c.head - lastBuy), lastBuy)
     } else {
        maxProfitHelp(c.tail, maxProfit, c.head)
     }
   }
 }

  maxProfitHelp(prices.tail, 0, prices.head)
}

And time performance is 9134 ms. (Memory: 75,47 MB)

So with Array-recursion complexity is 10 times worse (!) as with List-recursion!

Why did this happen?

Does this answer your question? Performance of tail function for Scala Arrays — yangzai
– yangzai, Commented Apr 16, 2024 at 11:43
Because taking the tail of an Array copies all the memory. Don't use Arrays as a newcomer, they have a lot of problems, one of them being terrible at performance if you don't use them appropriately. — Luis Miguel Mejía Suárez
– Luis Miguel Mejía Suárez, Commented Apr 16, 2024 at 13:57

Guru Stron · Accepted Answer · 2024-04-16 12:25:51Z

5

Previously when using leetcode I have quite often encountered even the same code having vastly different runtimes (though not 10x), so try submitting the same solution several times or better use appropriate tools for benchmarking
From what I can see Array.tail returns Array[T] which means that a new array should be constructed and have data copied to it (hence O(n)) unlike with List which is:

immutable, linked-list class

which means that tail operation should be extremely fast (O(1)).

edited Apr 16, 2024 at 12:25

answered Apr 16, 2024 at 11:45

Guru Stron

151k11 gold badges186 silver badges233 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Array and List recursion performance

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related