in reply to A (kinda) Circular Cache
Every time you scan or manipulate an array that is a O(n) operation. Arranging to constantly scan arrays quickly turns into O(n*n) which is slow algorithmically.
I hinted at this to you in Re (tilly) 3: Efficiency Question. MeowChow and I talked more in private than you see at that node. The key concept here is that you want to use hash lookups (O(1) operation) as often as possible and then rebuild your cache (O(n) operation but with a poor constant) only when you have to. This is algorithmically much, much better than doing O(n) searches repeatedly.
The general rule is that whenever you see "scan array" you should look for a hash.
There are other stylistic notes. For instance you could write your new method as:
which by using the 2-argument form of bless will allow someone to inherit from your cache implementation if they want...sub new { my $self = bless { array => [] }, shift; $self->{size} = shift || 30; $self; }
|
---|
Replies are listed 'Best First'. | |
---|---|
re: A (kinda) Circular Cache
by mr.nick (Chaplain) on Mar 24, 2001 at 00:26 UTC | |
by tilly (Archbishop) on Mar 24, 2001 at 01:11 UTC |