Folks,
tests showed that all this is not practical. I had two test cases
running where first I created 100000 key/value pairs with the pattern:
"key-" + i
"value-" + i
stored them and retrieved them. The results look promissing:
HashMap:
put/get: 300 / 190 ms
TableDFAMap:
put/get: 360 / 190 ms
DFAMap:
put/get: 460 / 250 ms
However, this works fine only as all keys have common prefixes keeping
the number of states low. If I, however, revers the pattern like:
i + "-key"
i + "-value"
the HashMap does not seem to be too much affected, but both map
implementations fail with an out of memory error as there are sooo
many expanded states.
Anyway, I took the freedom to add my initial implementation of the DFA
map implementations to the proposals section if anyone is interested.
If there was a sandbox section I would have added it there...
I will remove it ASAP if anyone feels it should not be there.
Oliver
On Mon, 25 Oct 2004 19:16:56 +0200, Unico Hommes <[EMAIL PROTECTED]> wrote:
> Oliver Zeigermann wrote:
>
> >This impresses me, as I really have almost the same code for a hand
> >optimized version for speed comparision against HashMap! By the way:
> >HashMap still wins the get/put competition :(
> >
> >
> >
>
> Wow, are these the comparisons you posted earlier? I guess it's the
> overhead created by the larger number of method calls.
>
> >However, this only works when your character set is stricly ASCII,
> >otherwise you would need something like
> >
> >new DFAState[65536];
> >
> >right? If so this is prohibitive, I guess...
> >
> >
> >
>
> Yep, having a 2 byte long array for every state would be rather
> expensive. Perhaps there is way to add ranges of chars as the need
> arises. If a char is added that is out of range a new segment is created
> for it.
>
> >Concerning caching: it might indeed by a better idea to have somehing
> >like groups you can invalidate as a bunch. With our cache a path would
> >make a group, versions of a resource as well.
> >
> >
> >
>
> Hmm yes, the caching use case is a special case that can be treated
> differently from the general scenario. Perhaps the EHCache functionality
> James pointed out is a good starting point.
>
> >Anyway, I will inverst more work into the DFAMap as it at least is fun :)
> >
> >
>
> :-)
>
> --
> Unico
>
> >Oliver
> >
> >On Mon, 25 Oct 2004 15:41:51 +0200, Unico Hommes <[EMAIL PROTECTED]> wrote:
> >
> >
> >>Pretty cool stuff Oliver. I've had a few occasions in the past when I
> >>wondered whether something like this existed. I never managed to
> >>translate my requirements into an actual design though.
> >>
> >>If memory is no concern and/or you are willing to accept to work with
> >>only a small subset of chars, what about the following alternative
> >>implementation?
> >>
> >>DFAState {
> >> Object value;
> >> DFAState[] successors = new DFAState[128];
> >> DFAState get(char c) {
> >> successors[(int)c];
> >> }
> >>}
> >>
> >>That should speed things up considerably.
> >>
> >>--
> >>Unico
> >>
> >>
>
> <snip/>
>
> ---------------------------------------------------------------------
>
>
> 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]
