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

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

[Dustin Sallings]

	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?

-- 
Dustin Sallings

-------------------
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

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

[jrouquie]

> 	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?


It's guaranteed in OCaml that when you have a pointer to the head of a list, 
the tail won't be modified.
So you have to rebuild at least a sublist with all the elements before the one 
you want to move. Or you can implement linked lists that doesn't meet the first 
specification.

Jean-Baptiste Rouquier.

-------------------
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

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

[Stefano Zacchiroli]

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

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

[Dustin Sallings]

On Nov 7, 2003, at 4:46, Stefano Zacchiroli wrote:

> 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).

	This is really what I was asking, whether ocaml lists could be 
appropriate.

	I'm having difficulty figuring out how to implement a double linked 
list, though.  I want something like this:

type 'a link = Nothing | Link of 'a t;;

type 'a t = {
     data: 'a;
     mutable prev: 'a link;
     mutable next: 'a link;
};;

	But, link and t don't know about each other.  How does one go about 
doing this kind of thing in ocaml?

-- 
Dustin Sallings

-------------------
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

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

[Stefano Zacchiroli]

[ Please don't Cc:-me, I'm subscribed to this list, as my
  Mail-Followup-To header can confirm ]

On Sat, Nov 08, 2003 at 12:49:48AM -0800, Dustin Sallings wrote:
> 	This is really what I was asking, whether ocaml lists could be 
> appropriate.
> 
> 	I'm having difficulty figuring out how to implement a double linked 
> list, though.  I want something like this:

I still think that lists, no matter if single or doubly linked aren't a
good structure for your cache, anyway ...

> type 'a link = Nothing | Link of 'a t;;
> type 'a t = {
>     data: 'a;
>     mutable prev: 'a link;
>     mutable next: 'a link;
> };;
> 	But, link and t don't know about each other.  How does one go about 
> doing this kind of thing in ocaml?

What do you mean? The above declaration isn't correct just because you
have to use an "and" instead of a "type" for the second declaration to
have two mutual recursive types. I don't know if this is really what
you're asking ...

Cheers.

-- 
^Stefano Zacchiroli -- Master in Computer Science @ Uni. Bologna, Italy$
^zack@{cs.unibo.it,debian.org,bononia.it} -- http://www.bononia.it/zack$
^Frequentando il mio maestro mi ero reso conto [.] che la logica poteva$
^servire a molto a condizione di entrarci dentro e poi di uscirne -Adso$

-------------------
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

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

[Dustin Sallings]

On Nov 8, 2003, at 1:16, Stefano Zacchiroli wrote:

> I still think that lists, no matter if single or doubly linked aren't a
> good structure for your cache, anyway ...

	I'm using a Hashtbl for indexing the linked list which is used for 
maintaining the sequence.  It should be O(1).

>> type 'a link = Nothing | Link of 'a t;;
>> type 'a t = {
>>     data: 'a;
>>     mutable prev: 'a link;
>>     mutable next: 'a link;
>> };;
>> 	But, link and t don't know about each other.  How does one go about
>> doing this kind of thing in ocaml?
>
> What do you mean? The above declaration isn't correct just because you
> have to use an "and" instead of a "type" for the second declaration to
> have two mutual recursive types. I don't know if this is really what
> you're asking ...

	It is, thank you.  The ``and'' thing was not obvious to me.  Still 
learning.

-- 
Dustin Sallings

-------------------
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

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

[Oleg Trott]

On Saturday 08 November 2003 03:49 am, Dustin Sallings wrote:
> On Nov 7, 2003, at 4:46, Stefano Zacchiroli wrote:
> > 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).
>
> 	This is really what I was asking, whether ocaml lists could be
> appropriate.
>
> 	I'm having difficulty figuring out how to implement a double linked
> list, though.  I want something like this:
>
> type 'a link = Nothing | Link of 'a t;;
>
> type 'a t = {
>      data: 'a;
>      mutable prev: 'a link;
>      mutable next: 'a link;
> };;
>
> 	But, link and t don't know about each other.  How does one go about
> doing this kind of thing in ocaml?

I've read your mind, and I think what you are trying to do is

type 'a t = {data: 'a; mutable prev: 'a option; mutable next: 'a option};;

or you can just do a web search for "doubly-linked list". It's out there.
-- 
Oleg Trott <oleg_trott@columbia.edu>

-------------------
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

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

[Oleg Trott]

On Saturday 08 November 2003 05:59 am, Oleg Trott wrote:
> On Saturday 08 November 2003 03:49 am, Dustin Sallings wrote:
> > On Nov 7, 2003, at 4:46, Stefano Zacchiroli wrote:
> > > 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).
> >
> > 	This is really what I was asking, whether ocaml lists could be
> > appropriate.
> >
> > 	I'm having difficulty figuring out how to implement a double linked
> > list, though.  I want something like this:
> >
> > type 'a link = Nothing | Link of 'a t;;
> >
> > type 'a t = {
> >      data: 'a;
> >      mutable prev: 'a link;
> >      mutable next: 'a link;
> > };;
> >
> > 	But, link and t don't know about each other.  How does one go about
> > doing this kind of thing in ocaml?
>
> I've read your mind, and I think what you are trying to do is
>
> type 'a t = {data: 'a; mutable prev: 'a option; mutable next: 'a option};;
>
> or you can just do a web search for "doubly-linked list". It's out there.

I meant 

type 'a t = {data: 'a; mutable prev: 'a t option; mutable next: 'a t option};;

-- 
Oleg Trott <oleg_trott@columbia.edu>

-------------------
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

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

[Brian Hurt]

On Sat, 8 Nov 2003, Dustin Sallings wrote:

> type 'a link = Nothing | Link of 'a t;;
> 
> type 'a t = {
>      data: 'a;
>      mutable prev: 'a link;
>      mutable next: 'a link;
> };;
> 
> 	But, link and t don't know about each other.  How does one go about 
> doing this kind of thing in ocaml?
>

Use and:

type 'a link = Nothing | Something of 'a t 
and 'a t = { data: 'a; mutable next: 'a link; mutable prev: 'a link }

The other alternative is to not redefine option:

type 'a t = 
    { data: 'a; mutable next: 'a t option; mutable prev: 'a t option } 

Brian

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
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

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

[Brian Hurt]

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