[Richard Suchenwirth] 2004-11-17 - When time-consuming operations occur more than once on the same input (and giving the same result), it is faster to cache such results for further use (see [Result caching]). However, if a long-running process uses a cache, it will grow unbounded - less politely expressed, a kind of "leak". So here's a caching code that keeps a list of least-recently-used elements, and deletes one once the maximum size is reached: ---- proc cached {arrName key args} { upvar #0 $arrName arr if {![info exists arr($key)]} { set arr($key) [eval $args] if {[llength $arr()]>=$arr(maxSize)} { unset arr([lindex $arr() 0]) set arr() [lrange $arr() 1 end] } } else { set pos [lsearch $arr() $key] set arr() [lreplace $arr() $pos $pos] } lappend arr() $key ;# LRU list set arr($key) } ---- Testing: initialize a cache, fill with some data % array set Cache {maxSize 4 {} {}} % cached Cache a clock seconds 1100702390 % cached Cache b clock seconds 1100702440 % cached Cache c clock seconds 1100702443 % cached Cache d clock seconds 1100702445 % parray Cache Cache() = a b c d Cache(a) = 1100702390 Cache(b) = 1100702440 Cache(c) = 1100702443 Cache(d) = 1100702445 Cache(maxSize) = 4 Ask for the element "a" again (moves it to end of LRU list): % cached Cache a clock seconds 1100702390 % parray Cache Cache() = b c d a Cache(a) = 1100702390 Cache(b) = 1100702440 Cache(c) = 1100702443 Cache(d) = 1100702445 Cache(maxSize) = 4 % cached Cache c clock seconds 1100702443 % parray Cache Cache() = b d a c Cache(a) = 1100702390 Cache(b) = 1100702440 Cache(c) = 1100702443 Cache(d) = 1100702445 Cache(maxSize) = 4 As maxSize is reached, the least-recently-used "a" will be decached: % cached Cache x clock seconds 1100704105 % parray Cache Cache() = d a c x Cache(a) = 1100702390 Cache(c) = 1100702443 Cache(d) = 1100702445 Cache(maxSize) = 4 Cache(x) = 1100704105 ---- [Arts and crafts of Tcl-Tk programming]