Collection sorted on last accessed object

[Vani Murarka]

Hi Everyone,

Does .NET offer any collection class which will give me objects last
*accessed* such that I may build a least-recently-used cache that
kills off objects that haven't been used for awhile?

Or is there any other way to implement this kind of a cache /
collection where one can do this kind of cleanup based on
least-recently-used objects?

Java has a collection class called LinkedHashSet which enables one to
do this. Is there something similar in .NET - or some other way of
doing this?

Any pointers will be really appreciated.

Thanks a ton

Regards

Vani

[at]

Just move it to the front on access and kill those at the back. Any
collection class that allows the move and the kill will do for this, like
ArrayList.

"Vani Murarka" <va**********@g mail.com> wrote in message
news:96******** *************** **@posting.goog le.com...

Hi Everyone,

Does .NET offer any collection class which will give me objects last
*accessed* such that I may build a least-recently-used cache that
kills off objects that haven't been used for awhile?

Or is there any other way to implement this kind of a cache /
collection where one can do this kind of cleanup based on
least-recently-used objects?

Java has a collection class called LinkedHashSet which enables one to
do this. Is there something similar in .NET - or some other way of
doing this?

Any pointers will be really appreciated.

Thanks a ton

Regards

Vani

[Helge Jensen]

at wrote:

Just move it to the front on access and kill those at the back. Any
collection class that allows the move and the kill will do for this, like
ArrayList.

You may run into performance-problems, ArrayList really doesn't perform
that well on anything but appending.

You could look into using a splay-tree data-structure, it fits your
requirements pretty nice and is really easy to implement.

--
Helge Jensen
mailto:he****** ****@slog.dk
sip:he********* *@slog.dk
-=> Sebastian cover-music: http://ungdomshus.nu <=-

[at]

That interests and surprises me, I have not measured the ArrayList's
performance for moving elements around but could you provide some links to
confirm your statement? I do not contradict your statement but I would like
some confirmation.

Then, an ArrayList comes standard meaning less code to write and as long as
its performance is ok why not stick with it? One can always change to
another container as the need arises and have the process itself up and
running first and then see what the performance is.

"Helge Jensen" <he**********@s log.dk> wrote in message
news:eu******** ******@TK2MSFTN GP14.phx.gbl...

at wrote:

Just move it to the front on access and kill those at the back. Any
collection class that allows the move and the kill will do for this, like
ArrayList.

You may run into performance-problems, ArrayList really doesn't perform
that well on anything but appending.

You could look into using a splay-tree data-structure, it fits your
requirements pretty nice and is really easy to implement.

--
Helge Jensen
mailto:he****** ****@slog.dk
sip:he********* *@slog.dk
-=> Sebastian cover-music: http://ungdomshus.nu <=-

[Helge Jensen]

at wrote:

That interests and surprises me, I have not measured the ArrayList's
performance for moving elements around but could you provide some links to
confirm your statement? I do not contradict your statement but I would like
some confirmation.
Output of attached source (measured execution time since start):

00:00:00 mutation from end...
00:00:00.010014 4 mutation from end... done
00:00:00.010014 4 mutation from start...
00:00:12.377798 4 mutation from start... done

It's not really suprising, since lists implemented as arrays has to copy
the tail of the list when inserting/removing.
Then, an ArrayList comes standard meaning less code to write and as long as
its performance is ok why not stick with it? One can always change to
another container as the need arises and have the process itself up and
running first and then see what the performance is.

Yes, the initial implementation can easily be done using ArrayList, and
if the profiler shows a performance problem there you can
re-implement.... but, I have implemented caching in the past, and
array's really aren't a good datastructure for it.

BTW: How are you going to search the cache? if it gets mederately large
you should probably have a seperate indexing on it, by hashing for example.

If my memory seves me right wrt. LinkedHashSet(J AVA), there is no way to
rearrange the ordering, moving most-used elements to the front, so it
really isn't very good for caching either.

--
Helge Jensen
mailto:he****** ****@slog.dk
sip:he********* *@slog.dk
-=> Sebastian cover-music: http://ungdomshus.nu <=-

using System;
using System.Collecti ons;

namespace ArrayListPerfor mance
{
class ArrayListPerfom anceTest
{
public static void Main()
{
int count = 100000;
DateTime start = DateTime.UtcNow ;
IList l = new ArrayList();
Console.WriteLi ne("{0} mutation from end...", DateTime.UtcNow-start);
for (int i = 0; i < count; ++i)
l.Insert(i, i);
Console.WriteLi ne("{0} mutation from end... done", DateTime.UtcNow-start);
l = new ArrayList();
Console.WriteLi ne("{0} mutation from start...", DateTime.UtcNow-start);
for (int i = 0; i < count; ++i)
l.Insert(0, i);
Console.WriteLi ne("{0} mutation from start... done", DateTime.UtcNow-start);
}
}
}

[at]

I thought ArrayList was backed by a doubly linked list, I guess I was wrong.
If implemented using fixed size arrays you are completely right.

Whatever data structure, as long as it is has the operations that a doubly
linked list has (implemented as such or as some tree flavour) the one most
in front is the most recently accessed one, the next one the one accessed
before that and so on. From the other end it works the same way hence te
requirement for doybly linked list semantics.

I am not considering random access here, just access starting from head and
starting from tail and step from there.

Well, thanks anyway, for pointing out the ArrayList inefficiency.

"Helge Jensen" <he**********@s log.dk> wrote in message
news:e6******** ******@TK2MSFTN GP14.phx.gbl...

at wrote:

That interests and surprises me, I have not measured the ArrayList's
performance for moving elements around but could you provide some links
to
confirm your statement? I do not contradict your statement but I would
like
some confirmation.
Output of attached source (measured execution time since start):

00:00:00 mutation from end...
00:00:00.010014 4 mutation from end... done
00:00:00.010014 4 mutation from start...
00:00:12.377798 4 mutation from start... done

It's not really suprising, since lists implemented as arrays has to copy
the tail of the list when inserting/removing.

Then, an ArrayList comes standard meaning less code to write and as long
as
its performance is ok why not stick with it? One can always change to
another container as the need arises and have the process itself up and
running first and then see what the performance is.

Yes, the initial implementation can easily be done using ArrayList, and
if the profiler shows a performance problem there you can
re-implement.... but, I have implemented caching in the past, and
array's really aren't a good datastructure for it.

BTW: How are you going to search the cache? if it gets mederately large
you should probably have a seperate indexing on it, by hashing for
example.

If my memory seves me right wrt. LinkedHashSet(J AVA), there is no way to
rearrange the ordering, moving most-used elements to the front, so it
really isn't very good for caching either.

--
Helge Jensen
mailto:he****** ****@slog.dk
sip:he********* *@slog.dk
-=> Sebastian cover-music: http://ungdomshus.nu <=-

--------------------------------------------------------------------------------

using System;
using System.Collecti ons;

namespace ArrayListPerfor mance
{
class ArrayListPerfom anceTest
{
public static void Main()
{
int count = 100000;
DateTime start = DateTime.UtcNow ;
IList l = new ArrayList();
Console.WriteLi ne("{0} mutation from end...", DateTime.UtcNow-start);
for (int i = 0; i < count; ++i)
l.Insert(i, i);
Console.WriteLi ne("{0} mutation from end... done",
DateTime.UtcNow-start);
l = new ArrayList();
Console.WriteLi ne("{0} mutation from start...",
DateTime.UtcNow-start);
for (int i = 0; i < count; ++i)
l.Insert(0, i);
Console.WriteLi ne("{0} mutation from start... done",
DateTime.UtcNow-start);
}
}
}

[at]

But, I tried the following

I measured

ArrayList al = new ArrayList();
for(int i = 0; i < 100000; i++)
{
al.Add(new TestItem(i));
}

TestItem ti;
int j = 99999;
Console.WriteLi ne("{0} starting turn around", DateTime.UtcNow );
for(int i = 0; i < 100000; i++)
{
ti = (TestItem)al[j];
al.RemoveAt(j);
al.Insert(0, ti);
j--;
}
Console.WriteLi ne("{0} turn around finished", DateTime.UtcNow );

and

public class TestItem
{
private int m;

public TestItem(int i)
{
m = i;
}
}

With the following result:

3/26/2005 4:18:20 PM starting turn around
3/26/2005 4:18:59 PM turn around finished

That is about 0.0004 seconds per move, I'd say that is better than fast
enough, at least it sufficiently fast so if moving an element to the front
is all that is needed I would initially just use an ArrayList.

Regards,

At

"at" <a@t> wrote in message news:42******** *************@n ews.xs4all.nl.. .

I thought ArrayList was backed by a doubly linked list, I guess I was
wrong. If implemented using fixed size arrays you are completely right.

Whatever data structure, as long as it is has the operations that a doubly
linked list has (implemented as such or as some tree flavour) the one most
in front is the most recently accessed one, the next one the one accessed
before that and so on. From the other end it works the same way hence te
requirement for doybly linked list semantics.

I am not considering random access here, just access starting from head
and starting from tail and step from there.

Well, thanks anyway, for pointing out the ArrayList inefficiency.

"Helge Jensen" <he**********@s log.dk> wrote in message
news:e6******** ******@TK2MSFTN GP14.phx.gbl...

at wrote:

That interests and surprises me, I have not measured the ArrayList's
performance for moving elements around but could you provide some links
to
confirm your statement? I do not contradict your statement but I would
like
some confirmation.

Output of attached source (measured execution time since start):

00:00:00 mutation from end...
00:00:00.010014 4 mutation from end... done
00:00:00.010014 4 mutation from start...
00:00:12.377798 4 mutation from start... done

It's not really suprising, since lists implemented as arrays has to copy
the tail of the list when inserting/removing.

Then, an ArrayList comes standard meaning less code to write and as long
as
its performance is ok why not stick with it? One can always change to
another container as the need arises and have the process itself up and
running first and then see what the performance is.

Yes, the initial implementation can easily be done using ArrayList, and
if the profiler shows a performance problem there you can
re-implement.... but, I have implemented caching in the past, and
array's really aren't a good datastructure for it.

BTW: How are you going to search the cache? if it gets mederately large
you should probably have a seperate indexing on it, by hashing for
example.

If my memory seves me right wrt. LinkedHashSet(J AVA), there is no way to
rearrange the ordering, moving most-used elements to the front, so it
really isn't very good for caching either.

--
Helge Jensen
mailto:he****** ****@slog.dk
sip:he********* *@slog.dk
-=> Sebastian cover-music: http://ungdomshus.nu <=-

--------------------------------------------------------------------------------

using System;
using System.Collecti ons;

namespace ArrayListPerfor mance
{
class ArrayListPerfom anceTest
{
public static void Main()
{
int count = 100000;
DateTime start = DateTime.UtcNow ;
IList l = new ArrayList();
Console.WriteLi ne("{0} mutation from end...",
DateTime.UtcNow-start);
for (int i = 0; i < count; ++i)
l.Insert(i, i);
Console.WriteLi ne("{0} mutation from end... done",
DateTime.UtcNow-start);
l = new ArrayList();
Console.WriteLi ne("{0} mutation from start...",
DateTime.UtcNow-start);
for (int i = 0; i < count; ++i)
l.Insert(0, i);
Console.WriteLi ne("{0} mutation from start... done",
DateTime.UtcNow-start);
}
}
}

[Helge Jensen]

at wrote:

I thought ArrayList was backed by a doubly linked list, I guess I was
wrong. If implemented using fixed size arrays you are completely right.
It's backed by an Array :)

Based on experimental evidence, the Array is reallocated when full. I'm
guessing it uses reallocation by multiplying the current size (O(n)
amortized for n inserts).
I am not considering random access here, just access starting from head
and starting from tail and step from there.
Didn't you mention a cache? what do you do lookup based on?
Well, thanks anyway, for pointing out the ArrayList inefficiency.

Well, it may or may not be a problem... atleast you know why it could be
slow.

--
Helge Jensen
mailto:he****** ****@slog.dk
sip:he********* *@slog.dk
-=> Sebastian cover-music: http://ungdomshus.nu <=-

[Helge Jensen]

at wrote:

That is about 0.0004 seconds per move, I'd say that is better than fast
enough, at least it sufficiently fast so if moving an element to the front
is all that is needed I would initially just use an ArrayList.

Good for you.

The expected expense of a randomly remove/insert would be O((n/2(^2)).

If the cache is smaller than 10k this may be an acceptible delay for
you, especially if the cached calculation is very expensive or lookups
are infrequent.

Of course you can always change to a "better" implementation later.

--
Helge Jensen
mailto:he****** ****@slog.dk
sip:he********* *@slog.dk
-=> Sebastian cover-music: http://ungdomshus.nu <=-

[Jeff J.]

If the important element is expiration of older items, rather than
sorting by access, you can use the Cache object from
System.Web.Cach ing. It supports timed expirations, both fixed and
sliding, as well as callbacks fired on removed items.

I don't know what the associated overhead is, but I hope that helps.

Good luck.

~ Jeff

Vani Murarka wrote:

Hi Everyone,

Does .NET offer any collection class which will give me objects last
*accessed* such that I may build a least-recently-used cache that
kills off objects that haven't been used for awhile?

Or is there any other way to implement this kind of a cache /
collection where one can do this kind of cleanup based on
least-recently-used objects?

Java has a collection class called LinkedHashSet which enables one to
do this. Is there something similar in .NET - or some other way of
doing this?

Any pointers will be really appreciated.

Thanks a ton

Regards

Vani