Decision Trees, Dynamic Programming, and useMemo()

Table of Contents:

1. The debate over useCallback and useMemo
2. Decision Trees
   • Fibonacci Sequence
3. Dynamic Programming
   • Fibonacci Sequence (notice the repeated work)
   • Principles of DP
   • Another Example, Coin change
   • 5 common problem types – Neetcode (eg. 0/1 Knapsack, unbounded knapsack)
4. useCallback and useMemo
   • A simple example (time saved)
   • How much time does it save in the code?

1. The debate over useCallback and useMemo

1. Basic use of the hooks
   

2. But you must ensure ALL variables are memo-ed, otherwise React will still re-render the component (read more: here)
   

3. Memoizing entire components might be more useful
   

4. How to profile the useMemo / function to see if it is better
   

Closing the debate: React Docs for useMemo()

You may rely on useMemo as a performance optimization, not as a semantic guarantee. In the future, React may choose to “forget” some previously memoized values and recalculate them on next render, e.g. to free memory for offscreen components. Write your code so that it still works without useMemo — and then add it to optimize performance.

This means useMemo does not exactly get "free" memory storage. It has to trade extra memory usage for faster runtimes.

Computers are so advanced, do all this matter anyway?

Research Paper: Why are you so slow? – Misattribution of transmission delay to attributes of the conversation partner at the far-end (https://www.sciencedirect.com/science/article/abs/pii/S1071581914000287)

Idea: 1.2 seconds delay makes one frustrated with their video-conferencing counterparts.
Question: Does useMemo and useCallback really reduce the delay to an extent where users would be less frustrated using the app?

2. Decision Trees

A decision tree is a decision support tool that uses a tree-like model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility.

Fibonacci Sequence

3. Dynamic Programming

Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial.

We can see in Fibonacci above that there is repeat work (or subproblems). Let's look at another problem to better our understanding:

• Coin Change, Medium [Leetcode]

Thought process explained (see more on Neetcode's youtube tutorial):

1. Brute Force first, try all possible solutions.
2. Need "greedy" algorithm to choose best solution.

3. Start with the smallest subproblem that you KNOW FOR SURE. That is, number of coins to make up Amount = 0 is 0!
   Hence, Bottom-up DP.
   

4. Many other articles echo this same procedure for solving Dynamic Programming.

   • https://www.linkedin.com/pulse/master-art-dynamic-programming-ajay-prakash-1d
   • https://www.byte-by-byte.com/fast-method/
   • https://towardsdatascience.com/mastering-dynamic-programming-a627dbdf0229
   • https://leetcode.com/discuss/general-discussion/712010/The-ART-of-Dynamic-Programming-An-Intuitive-Approach%3A-from-Apprentice-to-Master

Work through example? (10 mins)

coins = [1,2,5], amount = 7

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        dp = [amount+1] * (amount - 1)
        dp[0] = 0

        for a in range(1, amount + 1):
            for c in coins:
                if a - c >= 0:
                    dp[a] = min(dp[a], 1 + dp[a-c])

        return dp[amount] if dp[amount] != amount + 1 else -1

Key takeaway

• Rather than computing all subproblems' answers, dp array help to store subproblem answers.
• Dynamic Programming trades MEMORY for RUNTIME

Other kinds of Dynamic Programming problems (Neetcode's youtube guide)

4. React Hooks: useMemo() and useCallback()

Basic Idea

Tutorial: https://www.youtube.com/watch?v=oR8gUi1LfWY

Idea is that after he used the useMemo and useCallback for the Fibonacci number, his text input of "Dave" became much faster and responded after each letter typed. Before it all displayed AFTER the last letter is typed.

Time saved: about 2 seconds for a BILLION sized array. (maybe it doesn't matter THAT much after all)

How much time does it save in practical projects?

In practice, most times we memoize small props here and there.
Maybe can memoize entire components?
Or do some profiling to see where it is useful? Because an understanding of the render tree / stack navigator may be useful before deciding when to use useMemo.

Going Full Circle

Back to that Question: Does useMemo and useCallback really reduce the delay to an extent where users would be less frustrated using the app?

• Tradeoffs... tradeoffs... a daily occurrence for an engineer.
• Have to see the context in which these hooks are used.
• While it is still unclear, hopefully at least there is greater awareness about the tradeoffs and principles behind these hooks.