Re: [Caml-list] removing an item from a list efficiently

[Stefano Zacchiroli <zack@bononia.it>]

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