Skip to content

Instantly share code, notes, and snippets.

@lukego
Last active December 12, 2015 03:19
Show Gist options
  • Save lukego/4706097 to your computer and use it in GitHub Desktop.
Save lukego/4706097 to your computer and use it in GitHub Desktop.
Table data structure that "garbage collects" not-recently-used items in O(1) time

I use this data structure all the time. Can someone leave a comment and tell me what it's called?

  1. insert(k,v): add a new value
  2. lookup(k): lookup an existing value
  3. age(): delete old entries (that have not been used since previous call to age())
# Initialize 'old' and 'new' to empty tables
local old, new = {}, {}

function insert(k, v)
  new[k] = v
end

function lookup(k)
  if new[k] then
    # Found in new table
    return new[k]
  elseif old[k] then
    # Migrate from old table to new table
    new[k] = old[k]
    return old[k]
  else
    # Not found
    return nil
  end
end

function age()
  # Entries in 'old' are dropped, entries in 'new' become old.
  old = new
  new = {} # empty table
end
@lukego
Copy link
Author

lukego commented Feb 4, 2013

I suppose it's good that Lua distinguishes between statements and expressions, because otherwise I wouldn't be able to resist this 4-liner version:

local old, new = {}, {}
function insert(k, v) new[k] = v                         end
function lookup(k)    return new[k] or (new[k] = old[k]) end
function age()        old, new = new, {}                 end

@lukego
Copy link
Author

lukego commented Feb 4, 2013

Using Tony Finch's suggestion to make insert() return 'v' and thus refactor into what looks like actually valid Lua code:

local old, new = {}, {}
function insert(k, v) new[k] = v; return v                end
function lookup(k)    return new[k] or insert(k, old[k])  end
function age()        old, new = new, {}                  end

.. and yeah makes sense because in Lisp it's SETF returning the value that makes it combine nicely with AND/OR/etc.

@lukego
Copy link
Author

lukego commented Feb 4, 2013

Common Lisp version being discussed on Twitter:

(defvar *new* (make-hash-table))
(defvar *old* (make-hash-table))

(defun insert (k v)
  (when v (setf (gethash *new* k) v)))

(defun lookup (k v)
  (or (gethash *new* k) (insert k (gethash *old* k))))

(defun age ()
  (rotatef old new)
  (clrhash new))

@darius
Copy link

darius commented Feb 4, 2013

Nice -- I'll remember that. Here's a similar-but-different thing I do sometimes:

table = {}

def insert(k, v):
    if k not in table and 10000 <= len(table):
        table.clear()
    table[k] = v

@dougo
Copy link

dougo commented Feb 17, 2013

Seems like a degenerate version of a MRU cache?

Also, the lisp version of "lookup" shouldn't have a "v" argument, right?

@philipaconrad
Copy link

It looks like an LRU cache that has no hard limit on the number of elements.

Also, I ported this data structure to Python recently.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment