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 QAA07023; Fri, 7 Nov 2003 16:51:55 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id QAA07054 for ; Fri, 7 Nov 2003 16:51:54 +0100 (MET) Received: from herd.plethora.net (herd.plethora.net [205.166.146.1]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id hA7Fpr122690 for ; Fri, 7 Nov 2003 16:51:53 +0100 (MET) Received: from bhurt.plethora.net (bhurt.plethora.net [205.166.146.49]) by herd.plethora.net (8.11.6/8.10.1) with ESMTP id hA7FpiC16559; Fri, 7 Nov 2003 09:51:44 -0600 (CST) Date: Fri, 7 Nov 2003 10:50:30 -0600 (CST) From: Brian Hurt X-X-Sender: bhurt@localhost.localdomain To: Dustin Sallings cc: Caml Mailing List Subject: Re: [Caml-list] removing an item from a list efficiently In-Reply-To: <483F0AC5-1105-11D8-AC71-000393CFE6B8@spy.net> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 hashtbl:01 linked:01 nov:01 wrote:03 data:03 implement:05 implement:05 slow:05 structure:06 brian:06 brian:06 fri:07 i'm:07 i'm:07 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Fri, 7 Nov 2003, 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. > > Is there a better way to efficiently move a list item to the front, or > should I just implement a linked list to meet my requirements? > > If delete needs to be fast, consider using a different data structure. Look at the Set, Map, and Hashtbl libraries. Brian ------------------- 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