Having groups you can invalidate? Or anything else? Groups would work,
I more or less persued this for fun...
Oliver
On Wed, 27 Oct 2004 22:09:23 +0200, Daniel Florey <[EMAIL PROTECTED]> wrote:
> Hi,
> I've not fully understood what this is good for. I thought the main problem is to
> invalidate/remove subtrees in a cache.
> This could be achieved quit simple, doesn't it?
> Or have I missed something...
> Cheers,
> Daniel
>
> "Jakarta Commons Developers List" <[EMAIL PROTECTED]> schrieb am 27.10.04 16:35:05:
>
>
> >
> > After discussion and more tests in the Slide group I have abandoned
> > the approach.
> >
> > All this does not work for realistic scenarios and realistic sizes.
> > Main problem is that if the keys do not share much common prefixes the
> > size of states gets enormously and impracticably high.
> >
> > Sources still can be found in the Slide CVS.
> >
> > Cheers and thanks for the attention,
> >
> > Oliver
> >
> > On Tue, 19 Oct 2004 07:30:44 +0200, Oliver Zeigermann
> > <[EMAIL PROTECTED]> wrote:
> > > Folks,
> > >
> > > while thinking about cache invalidation strategies in the Slide
> > > project a long abandoned idea come back to my mind: a DFA based map
> > > for String keys only! When I implemented a scetch of this once it
> > > turned out to be slower in all respects than hash maps. These are my
> > > old measurements:
> > >
> > > DFA: 100000 puts: 5,7 secs / 100000 gets: 1 sec
> > > HashMap: 100000 puts: 3,2 secs / 100000 gets: .661 sec
> > >
> > > Even hand tuned versions could not catch up (no measurements - I guess
> > > I was too frustrated at that time).
> > >
> > > Anyway, what I need now is a map *plus* something that returns all
> > > values of the keys that have a certain prefix. E.g. if I have three
> > > entries like
> > >
> > > olli -> v1
> > > olli2 -> v2
> > > ollo -> v3
> > >
> > > the prefix of "oll" would get me v1,v2,v3; "olli" would get me v1,v2; etc.
> > >
> > > Now when the number of entries is small you could just iterate over
> > > the entries and do something like a startsWith and collect the values.
> > > In a scenario with thousands or even millions of entries with frequent
> > > checks this is prohibitive, though.
> > >
> > > Coming to the point now, when I organise the look up as a DFA the
> > > search space for prefixed values should be dramatically decreased! The
> > > map DFA would be some sort of tree and classes might look like this.
> > >
> > > class DFAState {
> > > Object value;
> > > Edge[] mapping;
> > > }
> > >
> > > class Edge {
> > > char label;
> > > DFAState nextState;
> > > }
> > >
> > > Every state would have an associated value and a number of outgoing
> > > edges to other states. Upon lookup they can be traversed when the next
> > > character is the labeled one. There can at most be one character per
> > > label, so this is deterministic.
> > >
> > > If there is no such label then the look fails. If the whole key has
> > > been matched the look up value is the one associated with the DFA.
> > > Those states are called end states. All other states have no
> > > associated value.
> > >
> > > Applied to the example above the DFA might look like this. s{i} are
> > > state names, |s{i}| are end state, - are edges. Above and below the
> > > edges, I have put the labels.
> > >
> > > o l l i 2
> > > s1 - s2 - s3 - s4 - |s5| - |s6|
> > > \
> > > o |s7|
> > >
> > > (hope this makes sense to anyone)
> > >
> > > Now, suppose the prefix is "oll". Traversing the DFA would bring me to
> > > s4. Doing a simple depth first search from there for all reachable end
> > > states (s5,s6,s7) will return me all entries having this prefix, i.e.
> > > v1,v2,v3. "olli" would bring me to s5 and the end states reachable
> > > from there (s5,s6) will bring me the v1,v2.
> > >
> > > And there I am...
> > >
> > > In case anyone has read this through, does it make sense? Or should I
> > > start taking those pills?
> > >
> > > Oliver
> > >
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: [EMAIL PROTECTED]
> > For additional commands, e-mail: [EMAIL PROTECTED]
> >
>
> ________________________________________________________________
> Verschicken Sie romantische, coole und witzige Bilder per SMS!
> Jetzt neu bei WEB.DE FreeMail: http://freemail.web.de/?mc=021193
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [EMAIL PROTECTED]
> For additional commands, e-mail: [EMAIL PROTECTED]
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
