Some cache simulation code to play around

trenes.clj

(ns trenes
  (:require [clojure.string :as str]))

(defn empty-cache [c]
  {:capacity c
   :values   {}
   :time     0
   :misses   0
   })

(defn hit? [cache elem]
  (get-in cache [:values elem]))

(defn full? [{:keys [capacity values]}]
  (>= (count values) capacity))

(defn expulse [{c      :capacity
                values :values   :as cache}]
  (let [[elem _] (apply min-key second values)
        purged   (dissoc values elem)]
    (assoc cache :values purged)))

(defn access [{t :time :as cache} elem]
  (let [hit (hit? cache elem)
        refreshed (-> cache
                    (assoc-in [:time] (inc t))
                    (assoc-in [:values elem] t)
                    (update-in [:misses] (if hit identity inc))
                    )]
    (if (and (not hit) (full? cache))
      (expulse refreshed)
      refreshed)))

(defn misses [c comparisons]
  (:misses
    (reduce access
            (empty-cache c)
            (flatten comparisons))))

(defn naive-access [_ n]
  (for [r (range n),
        c (range n) 
        :when (< r c)]
    [r c]))

(defn smart-access [c n]
  (let [routes (range n)
        blocks (partition-all (/ c 2) routes)]
    (for [rows blocks
          cols blocks
          r    rows 
          c    cols 
          :when (< r c)]
      [r c])))

(defn way-smart-access [c n]
  (let [routes   (range n)]
    (for [segment (partition-all (- c 2) routes)
          row     routes
          col     segment
          :when   (< row col)]
      [row col])))

(defn compare-all [c n]
  (let [algos {:naive naive-access
               :smart smart-access 
               :way-smart way-smart-access}]
    (into {} (map (fn [[name fn]]
                    [name (misses c (fn c n))])
                  algos))))

(defn access-order [pairs]
  (let [indexed (map vector pairs (iterate inc 0))]
    (reduce #(apply assoc-in %1 %2)
            {}
            indexed)))

(defn pprint-table [table]
  (let [rows (apply sorted-set (keys table))
        cols (apply sorted-set (flatten (map keys (vals table))))]
    (println
      (str/join "\n"
                (for [row rows]
                  (str/join "\t"
                            (for [col cols] (str (get-in table [row col])))
                            ))))))