Library
Module
Module type
Parameter
Class
Class type
Scalable LRU caches
Lru
provides size-bounded finite maps that remove the least-recently-used (LRU) bindings in order to maintain the size constraint. Two implementations are provided: one is functional, the other imperative.
The functional map is backed by a priority search queue. Operations on individual elements are O(log n)
.
The mutable map is backed by the standard Hashtbl
paired with a doubly-linked list. Operations on individual elements incur an O(1)
overhead on top of hash table access.
Both versions support differentially weighted bindings, and have a capacity parameter that limits the combined weight of the bindings. To limit the maps by the number of bindings, use let weight _ = 1
.
v0.2.0 — homepage
module type Weighted = sig ... end
Signature of types with measurable weight.
module F : sig ... end
Functional LRU map.
module M : sig ... end
Mutable LRU map.
val memo :
?hashed:(('a -> int) * ('a -> 'a -> bool)) ->
?weight:('b -> int) ->
cap:int ->
(('a -> 'b) -> 'a -> 'b) ->
'a ->
'b
memo ?hashed ?weight ~cap f
is a new memoized instance of f
, using LRU caching. f
is an open recursive function of one parameter.
~hashed
are hashing and equality over the arguments 'a
. It defaults to (Hashtbl.hash, Pervasives.(=))
.
~weight
is the weighting function over the results 'b
. It defaults to fun _ -> 1
.
~cap
is the total cache capacity.