Prev: A new prime number pattern
Next: solutions to Sipser's Theory of Computation
From: Patricia Shanahan on 13 Jul 2010 17:24
On 7/13/2010 11:33 AM, Dann Corbit wrote:
> In article<5b3865ae-24ad-43dd-9416-495d8f3fad58
> @x1g2000prc.googlegroups.com>, dhruvbird(a)gmail.com says...
>> 1. It is not necessary that items with the same frequency get evicted
>> by the LRU algorithm. It is just *one* of the ways to go about the
>> task. There could be a different way wherein any random entry is
>> evicted if there are many frequently used entries (having the same
>> access count/frequency).
>
> What do you think the "Recently" means in Least Recently Used?
> If we do not consider time, then it is not an LRU algorithm.
>
>> 2. LRU is an orthogonal discussion.
>>
>> 3. LRU doesn't require you to keep track of time. It can be (and
>> usually) is very easily implemented by using a combination of a linked
>> list and a hash map.
>
> If it does not consider time, then it is not an LRU algorithm. It is
> something else.
>

I think we should distinguish between time order and elapsed time. LRU
depends on the time order of events, but not on elapsed time.

Patricia

From: Tim Little on 13 Jul 2010 19:35
On 2010-07-13, dhruvbird <dhruvbird(a)gmail.com> wrote:
> From what I see, you aren't giving any solid evidence or even
> quoting any publications to base your claims on. I have quoted
> numerous resources which clearly contradict the views you held.

I have quoted *exactly the same sources* back to you contradicting
your own views. As I said, this discussion appears to be over.


- Tim
From: jacko on 14 Jul 2010 14:48
I thought that each page has a counter. Then the master counter is
updated by an increment/(number of pages). So any page which overflows
it's counter becomes locked, and any which underflows (all relative to
the master count) gets evicted there and then, becoming unlocked as
necessary.
From: dhruvbird on 19 Jul 2010 03:34
On Jul 14, 2:24 am, Patricia Shanahan <p...(a)acm.org> wrote:
> On 7/13/2010 11:33 AM, Dann Corbit wrote:
>
>
>
>
>
> > In article<5b3865ae-24ad-43dd-9416-495d8f3fad58
> > @x1g2000prc.googlegroups.com>, dhruvb...(a)gmail.com says...
> >> 1. It is not necessary that items with the same frequency get evicted
> >> by the LRU algorithm. It is just *one* of the ways to go about the
> >> task. There could be a different way wherein any random entry is
> >> evicted if there are many frequently used entries (having the same
> >> access count/frequency).
>
> > What do you think the "Recently" means in Least Recently Used?
> > If we do not consider time, then it is not an LRU algorithm.
>
> >> 2. LRU is an orthogonal discussion.
>
> >> 3. LRU doesn't require you to keep track of time. It can be (and
> >> usually) is very easily implemented by using a combination of a linked
> >> list and a hash map.
>
> > If it does not consider time, then it is not an LRU algorithm.  It is
> > something else.
>
> I think we should distinguish between time order and elapsed time. LRU
> depends on the time order of events, but not on elapsed time.
>

Exactly!!

Regards,
-Dhruv.
From: dhruvbird on 19 Jul 2010 03:36
On Jul 14, 11:48 pm, jacko <jackokr...(a)gmail.com> wrote:
> I thought that each page has a counter. Then the master counter is
> updated by an increment/(number of pages). So any page which overflows
> it's counter becomes locked, and any which underflows (all relative to
> the master count) gets evicted there and then, becoming unlocked as
> necessary.

There are many variations to LFU. What you mention is one such
variation. This over/under-flow occurs because the number of bits in
the counter might be bounded in some way.

Regards,
-Dhruv.
First  |  Prev  | 
Pages: 1 2 3 4
Prev: A new prime number pattern
Next: solutions to Sipser's Theory of Computation