Computer Science 70 Big Idea memoization Hashing General principle store rather than recompute Context is a tree recursive algorithm with lots of repeated computation e g Fibonacci int Fib int n if n 0 n 1 return n else if we ve computed n s value already return that value else int value Fib n 1 Fib n 2 store n value return value Pairs n value of Fib n are stored in the table Discrete Mathematics and Probability Theory Lecture 23 2003 10 22 Dan Garcia www cs berkeley edu ddgarcia inst eecs berkeley edu cs70 1 Handout notes CS70 L23 Hashing 1 Dan Garcia UCB Hash Function CS70 L23 Hashing 2 Dan Garcia UCB Writing hash functions TTT 1 If what we want to memoize isn t a simple number how do we convert it to a number to easily store it into a table We need something that can help us map this data into an integer to serve as an index into an array used to store the table Let s consider Tic Tac Toe One player chooses X the other chooses O They take turns placing their piece on the board Assume X goes first Once a piece is placed it isn t moved The player who first gets 3 in a row wins If the board gets filled up and nobody wins it s a tie This mapping function is called a hash function http en wikipedia org wiki Hash function CS70 L23 Hashing 3 Dan Garcia UCB CS70 L23 Hashing 4 Dan Garcia UCB 1 Writing hash functions TTT 2 Writing a Tic Tac Toe hash function h Writing hash functions TTT 3 Think of each of the 9 slots as 1 of 3 values Blank O and X Let s assign values 0 1 and 2 to these 13 205 2 0 0 0 1 0 0 0 2 One idea is to ignore the 2D nature of the game and make it a 1D array of slots 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 Let s think about this as a ternary number S8 38 S7 37 S1 31 S0 30 2 38 1 34 2 30 13 205 0 1 2 3 4 5 6 7 8 CS70 L23 Hashing 5 Dan Garcia UCB Writing hash functions TTT 4 This is known as a polynomial hash code CS70 L23 Hashing 6 Dan Garcia UCB Writing hash functions TTT 5 Optimizing the Tic Tac Toe hash function Analysis of ternary polynomial hashcode 0 1 2 3 4 5 6 7 8 How can we create a single number from this 0 What s the smallest 39 1 What s the biggest Is this as optimal I e tightly packed as possible No Any suggestions for making this more optimal This involves understanding the rules of placement The players take turns X goes first Let s consider some small 1D boards S of slots S 1 2 boards X We ll use to separate groups S 2 5 boards X X XO OX S 3 13 boards X X X OX XO O X OX X O XO OXX XOX XXO 1 3 6 3 S 4 boards pattern CS70 L23 Hashing 7 Dan Garcia UCB CS70 L23 Hashing 8 Dan Garcia UCB 2 5 Remember your Combinatorics Recall Pascal s Triangle 2 10 K Let s figure out numBoards s s slots For n 5 we had 0 Generalizing from this example p pieces numBoards s p 0 N s 2 rearrange p p s But what is rearrange x o s p 1 rearrange p p 1 s of ways to rearrange x Xs o Os in s slots CS70 L23 Hashing 9 Dan Garcia UCB s s x o x o x o o x Think of permuting all the elements how many How many were overcounted Xs Os spaces o Answer is quotient of these s x o 5 6 1 1 1 2 1 2 1 3 1 3 3 1 4 1 4 6 4 5 1 5 10 10 5 6 1 6 15 20 15 6 This table describes how to calculate combinations I e N choose K N K 1 1 1 N K N K That is the number of ways to rearrange 2 pieces in 5 slots is 5 choose 2 which is the expression at the top 10 ways CS70 L23 Hashing 10 Dan Garcia UCB numBoards 4 1 4 12 12 6 35 numBoards 9 1 9 72 252 756 1260 1680 1260 630 126 6 046 19 683 39 Plotting rearrange x o 4 x o x s x s x o s o x s x o CS70 L23 Hashing 11 4 Now we know numBoards s 0 1 2 3 4 5 6 7 8 First blur eyes how many ways to rearrange s x o ALL x o pieces in s slots stop blurring now For EACH how many ways to rearrange Xs in pieces x o x Answer is product of these Overcount method 3 Now we know our Hash Table size rearrange x o s r x o s How many ways to rearrange x Xs o Os in s slots Blur method 2 0 1 ways to rearrange 0 Xs 0 Os in 4 slots ways to rearrange 1 Xs 0 Os in 4 slots ways to rearrange 1 Xs 1 Os in 4 slots ways to rearrange 2 Xs 1 Os in 4 slots ways to rearrange 2 Xs 2 Os in 4 slots s 2 1 Dan Garcia UCB 2 Note zig zag pattern as a result of the alternating moves of each player numBoards just sums em o 1 0 1 s 4 0 6 12 12 4 1 2 x CS70 L23 Hashing 12 Dan Garcia UCB 3 But what about the hash function How do we write the combinatorially optimal hash This take our board and generates a between 0 and numBoards 1 Two steps sum the following numbers Must be a between 0 and numBoards 4 1 34 Two steps BIAS REARRANGEMENT 1 Finding out how many numbers there were in the zigzag up to our box this is the BIAS or OFFSET 2 Finding out our number REARRANGEMENT within our box Exactly same idea as the ternary polynomial hash code X counts as 2 i e 2 3i O counts as 1 I e 1 3i 0 Here we consider the leftmost slot how much it s worth BIAS X 2 O 1 S 4 Count buckets up to us 1 4 12 17 REARRANGEMENT R X O S X3 r 2 1 3 r 2 0 3 3 3 O2 r 1 1 2 2 2 1 0 X0 0 from shortcut o 1 REARRANGEMENT 3 3 2 8 0 1 X counts for all ways to rearrange if it were O O counts for all ways to rearrange if it were counts for 0 Shortcut when a board has all the same piece counts for 0 CS70 L23 Hashing 13 Example TicTacToe …
View Full Document
Unlocking...