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..!
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 163 |
| 2 | cry | 161 |
| 3 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | awoo | 158 |
| 6 | atcoder_official | 157 |
| 7 | adamant | 155 |
| 7 | nor | 155 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.09.2024 18:46:42 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
recursive dp is slower bc you make recursive calls and calling a function is slow
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).
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 ..!
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.
recursive dp quite slower comparatively but for this problem my recursive dp solution ran below 400ms 268191223
Yeah it depends on implementation, but I was comparing similar implementation on both rec. And iterative dp's and hence was shocked.
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:
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.
You visit memory in an unorderly manner, causing more cache misses. https://codeforces.net/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.
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.
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.
Yeah sure, thanks
Wooow thnx, that was very insightful. I would definitely be more mindful from now. Thnx again