Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] removing an item from a list efficiently
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Stefano Zacchiroli <zack@b...>
Subject: Re: [Caml-list] removing an item from a list efficiently
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