From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id 9028FBBAF for ; Tue, 22 Sep 2009 13:33:47 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AqEBAMtSuEpCbwQZkGdsb2JhbACadQEBAQEJCQwHEwS7Q4QbBQ X-IronPort-AV: E=Sophos;i="4.44,431,1249250400"; d="scan'208";a="33275295" Received: from out1.smtp.messagingengine.com ([66.111.4.25]) by mail2-smtp-roc.national.inria.fr with ESMTP; 22 Sep 2009 13:33:47 +0200 Received: from compute2.internal (compute2.internal [10.202.2.42]) by gateway1.messagingengine.com (Postfix) with ESMTP id 3009972126; Tue, 22 Sep 2009 07:33:46 -0400 (EDT) Received: from heartbeat1.messagingengine.com ([10.202.2.160]) by compute2.internal (MEProxy); Tue, 22 Sep 2009 07:33:48 -0400 X-Sasl-enc: jUjEOYrp3cOUFcGeUdvpB61oD3O7/RDqv2+MQ7Pa18V8 1253619225 Received: from [192.168.1.12] (ALyon-157-1-50-146.w83-201.abo.wanadoo.fr [83.201.201.146]) by mail.messagingengine.com (Postfix) with ESMTPSA id 810F96FF45; Tue, 22 Sep 2009 07:33:45 -0400 (EDT) Message-ID: <4AB8B44F.6040503@ens-lyon.org> Date: Tue, 22 Sep 2009 13:26:07 +0200 From: Martin Jambon User-Agent: Thunderbird 2.0.0.22 (X11/20090908) MIME-Version: 1.0 To: Hugo Ferreira Cc: caml-list@inria.fr Subject: Re: [Caml-list] Cache algorithms: implementation or library available? References: <4AB8A6F1.7090802@inescporto.pt> In-Reply-To: <4AB8A6F1.7090802@inescporto.pt> Content-Type: text/plain; charset=ISO-8859-15 Content-Transfer-Encoding: 7bit X-Spam: no; 0.00; ens-lyon:01 ocaml:01 integers:01 trade-offs:01 bounded:01 frisch:01 hash:01 frisch:01 wrote:01 integer:01 caml-list:01 probability:01 probability:01 alain:01 alain:01 Hugo Ferreira wrote: > Hello, > > I would like to know if anyone has or knows of an Ocaml > library or open-source code implementation of some cache > algorithms (example: least recently used). > > Basically I need to cache a function that maps a list > of ordered integers into a value (float, integer). I > would like something that allows setting a maximum size > of the map and automatically discards the data. There are so many possible access patterns and trade-offs: - speed requirements? - memory requirements? - constant size or just bounded? - is the probability of accessing an element a function of time? I see two frequent use cases: a. some elements are accessed more frequently than others regardless of time b. recently-accessed elements have a higher probability of being accessed Alain Frisch provides an implementation of roughly a hash table in which buckets hold only one element, which looks great at least for case (a): http://alain.frisch.fr/soft.html#memo Martin -- http://mjambon.com/