Sm_ar__z__'s blog

Iterative V/s Recursive dp
By Sm_ar__z__, history, 2 months ago, In English

Hi everyone , I recently submitted my dp soln to the problem 1987D - World is Mine and was really surprised with the running time of both my code , iterative — 281468972 which ran in 400ms to recursive — 281467770 which barely passed the time limit . Please can anyone tell me whether my implementation to the recursive part is wrong and if not , why so much discrepancy. Thank You..!

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +9 Vote: I do not like it

recursive dp is slower bc you make recursive calls and calling a function is slow

→ Reply
»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Recursive implementations of DP questions almost always takes more time because of the function calls and the recursive call stack.

That's why high rated folks always prefer iterative DP because it can run in tighter constraints and also for the fact that many optimization techniques are only possible in the iterative versions (like taking prefix sums of previously computed rows or running range queries on them).

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hii , thnx for replying . I know iterative is faster , but didn't knew it was this fast for a particular question , so i doubted that my recursive implementation might have some modifications to offer . Could you suggest me if any ..!

    → Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's true that iterative DP can make some optimizations easier, but the main reason to use it as often as possible is that it's simply shorter code.

    → Reply
»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

recursive dp quite slower comparatively but for this problem my recursive dp solution ran below 400ms 268191223

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah it depends on implementation, but I was comparing similar implementation on both rec. And iterative dp's and hence was shocked.

    → Reply
»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

People say it's slower because of recursion but it's not just that, I think that's actually a small part of it. The main 2 differences (according to my intuition) are:

  1. When you do memoization+recursion then your code ends up having a lot more ifs. Read https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array I've read this answer in 2015-2016 and it's very enlightening.

  2. You visit memory in an unorderly manner, causing more cache misses. https://codeforces.me/contest/1987/submission/281498628 this is your recursive code but with fors calling the DP in a good order, forcing it to use memory in a less random order and execution time was cut to 800ms.

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Very insightful discussion!

    I also wanted to ask if the dimensions of the DP matrix (say n*m vs m*n) can make a difference in the time consumed by cache misses in a certain case especially when n >> m.

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Try it yourself. From my experiments I've seen a dp going down from 4s to 800ms just by changing the order of things in memory.

      → Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wooow thnx, that was very insightful. I would definitely be more mindful from now. Thnx again

    → Reply