From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id NAA00014; Fri, 7 Nov 2003 13:46:23 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id NAA00104 for ; Fri, 7 Nov 2003 13:46:22 +0100 (MET) X-SPAM-Warning: Sending machine is listed in blackholes.five-ten-sg.com Received: from vsmtp12.tin.it (vsmtp12.tin.it [212.216.176.206]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id hA7CkL114386 for ; Fri, 7 Nov 2003 13:46:21 +0100 (MET) Received: from dalamar.takhisis.org (80.180.123.130) by vsmtp12.tin.it (7.0.019) id 3F8C8492009B8829 for caml-list@inria.fr; Fri, 7 Nov 2003 13:46:21 +0100 Received: from fistandantilus.takhisis.org (fistandantilus.takhisis.org [192.168.1.113]) by dalamar.takhisis.org (Postfix) with ESMTP id C5486B770 for ; Fri, 7 Nov 2003 13:46:19 +0100 (CET) Received: by fistandantilus.takhisis.org (Postfix, from userid 3148) id 4CEBD274025; Fri, 7 Nov 2003 13:46:19 +0100 (CET) Date: Fri, 7 Nov 2003 13:46:19 +0100 From: Stefano Zacchiroli To: Caml Mailing List Subject: Re: [Caml-list] removing an item from a list efficiently Message-ID: <20031107124619.GA14374@fistandantilus.takhisis.org> Mail-Followup-To: Caml Mailing List References: <483F0AC5-1105-11D8-AC71-000393CFE6B8@spy.net> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <483F0AC5-1105-11D8-AC71-000393CFE6B8@spy.net> User-Agent: Mutt/1.5.4i X-Loop: caml-list@inria.fr X-Spam: no; 0.00; bononia:01 caml-list:01 okasaki's:01 bononia:01 imho:01 nov:01 bologna:03 wrote:03 zacchiroli:03 zacchiroli:03 romney:03 unibo:03 zack:03 zack:03 stefano:04 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Fri, Nov 07, 2003 at 01:32:19AM -0800, Dustin Sallings wrote: > I'm trying to implement an LRU cache and I'm using a list to keep up > with the accesses. I'm using filter to remove the item for > repositioning it. That's very slow. List.filter will scan the entire list anyway. In the LRU case you can stop the list traversal after finding the first (i.e. only) element you want to remove. Still you have to traverse the list at least until the element you want to remove. IMHO to implement an LRU policy, lists are not the best structures due to the O(n) limit above. You can consider standard heaps (assuming you have an upper bound on the number of entries) or binomial heaps (you can find an implementation in Okasaki's book). Cheers. -- Stefano Zacchiroli -- Master in Computer Science @ Uni. Bologna, Italy zack@{cs.unibo.it,debian.org,bononia.it} - http://www.bononia.it/zack/ " I know you believe you understood what you think I said, but I am not sure you realize that what you heard is not what I meant! " -- G.Romney ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners