Lecture Notes for SE 598, Data Structures and Algorithms

9 August 2000, Map and Multimap Algorithms

1. memoization - remembering what's been done before

   1. when computing f(x₁, x₂, ..., x_n), remember v, the value computed

   2. store v in a memo map using some combination of x₁, x₂, ..., x_n as a key

   3. before computing f(x₁, x₂, ..., x_n), look in the memo map to see if it's been computed before

   4. saves time on expensive, re-occurring computations

   5. f() must be a function - produce the same value from the same arguments every time

2. software caching - more general than memoization, more reliant on hashing

   1. when retrieving a value, store a copy of in the cache

   2. caches are fast, simple, and near-by, while the values may be far, slow, or difficult to get

   3. maps ensure that caches are fast and efficient to modify and search

      1. stl maps have unfortunate semantics

   4. networking makes heavy use of software caches - information is far away and difficult to get

   5. the stale-date problem with caches

This page last modified on 9 August 2000.