4 ms·

Don't even get me started on memoization...

by santaclaus 10y ago

brightball 10y ago
I regret that I have but one up vote to give
Cyph0n 10y ago
- "You mean caching?" - "Nope, memoization." - "Uh ok."
- tdb7893 10y ago
  I like that it's not called caching because caching for me makes me think that there is some sort of eviction policy. I generally talk about "storing" data in "lookup tables" if I'm talking to someone not familiar with the jargon
  - Cyph0n 10y ago
    Good point. Caching does usually refer to a temporary memory store.
- wfunction 10y ago
  IMO: caching : memoization :: program performance : algorithm performance
RussellDussel 10y ago
The problem with "memoize" is people always think I'm trying to say "memorize" with a speech impediment, especially because both words usually (kind of) make sense in the context.
- Retra 10y ago
  I'm not actually sure that's a problem. You just have another way to fizz-buzz lay people.
- YeGoblynQueenne 10y ago
  Also, some spellcheckers will surreptitiously auto-"correct" memoization to "memorization" (as, e.g. Word, and I happen to know it does that because it did it in my Master's dissertation; luckily, just a footnote but probably made me look like an idiot trying to show off with terms I don't understand).
aws_ls 10y ago
That was my first thought too. I thought the page was referring to DP/Memoization[1], initially. Thats the most useful concept I learnt about a decade back, and was fortunate to be able to find a case in real-life to apply it. I have often a hard time explaining it though. But very simply (the way I explain) it is, you compute and keep lot of results for lower values e.g. value of f(x,y) where x,y are less than some larger n,m respectively. And for computing f(n,m) you would need to compute f(x,y) a number of times for varying values of x,y. So if you keep it in memory. You save hell lot of a computing time. And your program runs in a fraction of time of what it would take other wise. [1] https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/ https://www.topcoder.com/community/data-science/data-science... Edit: minor correction
- wfunction 10y ago
  The thing is, there is no stipulation that the subproblems be any "smaller" than the original problem. They just need to be instances of the same problem combining together in a manner that solves the original problem.
  - aws_ls 10y ago
    Yes, I can think of a case where how it may be used to solve some problems on a M x N grid, where in you could move in either directions top-left to bottom-right Or vice-versa. I perhaps used smaller where subproblem may be a more optimal use.

Don't even get me started on memoization...

brightball 10y ago

I regret that I have but one up vote to give

Cyph0n 10y ago

- "You mean caching?" - "Nope, memoization." - "Uh ok."

tdb7893 10y ago
I like that it's not called caching because caching for me makes me think that there is some sort of eviction policy. I generally talk about "storing" data in "lookup tables" if I'm talking to someone not familiar with the jargon
- Cyph0n 10y ago
  Good point. Caching does usually refer to a temporary memory store.
wfunction 10y ago
IMO: caching : memoization :: program performance : algorithm performance

RussellDussel 10y ago

The problem with "memoize" is people always think I'm trying to say "memorize" with a speech impediment, especially because both words usually (kind of) make sense in the context.

Retra 10y ago
I'm not actually sure that's a problem. You just have another way to fizz-buzz lay people.
YeGoblynQueenne 10y ago
Also, some spellcheckers will surreptitiously auto-"correct" memoization to "memorization" (as, e.g. Word, and I happen to know it does that because it did it in my Master's dissertation; luckily, just a footnote but probably made me look like an idiot trying to show off with terms I don't understand).

aws_ls 10y ago

That was my first thought too. I thought the page was referring to DP/Memoization[1], initially. Thats the most useful concept I learnt about a decade back, and was fortunate to be able to find a case in real-life to apply it. I have often a hard time explaining it though. But very simply (the way I explain) it is, you compute and keep lot of results for lower values e.g. value of f(x,y) where x,y are less than some larger n,m respectively. And for computing f(n,m) you would need to compute f(x,y) a number of times for varying values of x,y. So if you keep it in memory. You save hell lot of a computing time. And your program runs in a fraction of time of what it would take other wise. [1] https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/ https://www.topcoder.com/community/data-science/data-science... Edit: minor correction

wfunction 10y ago
The thing is, there is no stipulation that the subproblems be any "smaller" than the original problem. They just need to be instances of the same problem combining together in a manner that solves the original problem.
- aws_ls 10y ago
  Yes, I can think of a case where how it may be used to solve some problems on a M x N grid, where in you could move in either directions top-left to bottom-right Or vice-versa. I perhaps used smaller where subproblem may be a more optimal use.