2 ms·

> This is grossly inefficient for some operations, but functions as a map I believe it's actually faster than a hash table for a decently large n, around the o

• Jtsummers 5y ago
  I've never benchmarked the two as I usually either need something small (so use alists) or of large or indeterminate size (so use hash tables). There's a clear performance difference between the two choices at that second case, but since I never hit the "middle ground" I don't know what the threshold is. It probably also varies with each implementation. Hash tables, though, should be O(1) for retrieval and updates and amortized O(1) for insertions. Alists are O(n) for retrieval and updates and O(1) for insertions (if you don't check for the presence of the key).
• TeMPOraL 5y ago
  If you want performance, you may be better off using arrays in some cases. Instead of an alist or a hash table, make a struct - or even just a cons cell like: (cons keys values). Then have your association function do a linear search for target key on (car table), e.g. via #'position, and use its index to fetch the value from (cdr table) directly.