[EMAIL PROTECTED] writes:
| G'day all.
|
| Tom Pledger wrote:
|
| > How about adapting splay trees so that their pointers become weak
| > after a certain depth? The advantage for caching is that the more
| > frequently used elements move closer to the root, so you wouldn't have
| > to add much code for tracking recent use, just a depth threshold.
|
| Nice idea, but I think it wouldn't be generally useful. Splay trees
| optimise themselves for static frequency distributions. Caches, on
| the other hand, are generally used more for changing working sets (i.e.
| dynamic frequency distributions). It seems to me that splay trees are
| therefore not necessarily a good fit.
Hi.
It sounds like the term "splay tree" means different things to
different people. I was thinking in particular of one which, whenever
it finds a key it was looking for, does some rotation so that the
key's node's depth is reduced.
e.g. finding g in this initial tree causes this rotation
d d
/ \ / \
T1 h T1 h
/ \ / \
weak f T2 g T2
pointer ------ / \ -------------------------- / \ -------
threshold T3 g f T5
/ \ / \
T4 T5 T3 T4
This is admittedly a side effect on the cache lookup, but we'd be in
the IO monad anyway if we're using weak pointers.
- Tom
_______________________________________________
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
