阅读中文版本

LFU Cache CLI

A Node CLI that simulates an LFU (least-frequently-used) cache, processing get and put commands from stdin and printing evictions.

node --version

printf "put a 1\nput b 2\nget a\nput c 3" | node lfu.mjs 2

node --test lfu.test.mjs

Prints the result of each get and the key evicted on each put that exceeds capacity, using least-frequently-used eviction with LRU tie-breaking.

What it does

Simulates an LFU cache with the given capacity. Each get increments the frequency and updates the recency; each put on a full cache evicts the least-frequently-used key, with LRU tie-breaking by recency. The eviction is printed so the policy is observable.

const cap = +process.argv[2];
const freq = new Map(), val = new Map(), last = new Map();
const evict = () => {
  let minK = null, minF = Infinity, minT = Infinity;
  for (const [k, f] of freq) if (f < minF || (f === minF && last.get(k) < minT)) { minK = k; minF = f; minT = last.get(k); }
  freq.delete(minK); val.delete(minK); last.delete(minK);
  return minK;
};
let tick = 0;
const get = k => { if (!val.has(k)) return 'null'; freq.set(k, freq.get(k) + 1); last.set(k, tick++); return val.get(k); };
const put = (k, v) => {
  if (val.has(k)) { val.set(k, v); freq.set(k, freq.get(k) + 1); last.set(k, tick++); return; }
  if (val.size >= cap) console.log('evicted ' + evict());
  val.set(k, v); freq.set(k, 1); last.set(k, tick++);
};
const rl = require('readline').createInterface({ input: process.stdin });
rl.on('line', cmd => {
  const [op, k, v] = cmd.split(' ');
  if (op === 'get') console.log('get ' + k + ' = ' + get(k));
  else if (op === 'put') put(k, v);
});

Run and verify

printf "put a 1\nput b 2\nget a\nput c 3" | node lfu.mjs 2

Run the test command to check the implementation: node --test lfu.test.mjs.

Expected Output

With capacity 2: put a and b fill the cache, get a raises a frequency, put c evicts b (frequency 1, less than a frequency 2):

get a = 1
evicted b

Limitations

The frequency and recency maps are scanned on every eviction, which is O(n). A real LFU uses a frequency-list structure for O(1) eviction, but this CLI prioritizes clarity.