On 11/19/2012 3:09 PM, Doug Baskins wrote:
Tim:
Sorry for delayed reply. I have been getting ready for travel. I am
currently
in an Airport on my way to Thailand (from Colorado, USA).
Absolutely, not a problem. Have a safe trip.
> 2.) Doug, have you thought about making a search function that will give
> up as soon as it determines that there are no matches beginning with
> Index?What do you think about including it in one of the upcoming
> versions?
I think it is very do-able. The data structure lends itself to that
kind of
"search".
That's what I thought. From my basic knowledge of the structure, it
seems that a prefix-search is simply a First where you quit early if it
turns out you would have to go up a level. So that might be a simple
matter of leaving /out/ some code that the normal JudySLFirst() requires.
By the way, I misspoke in my first email. I said that I was using
JudySLNext() followed by an strncmp(), but I should have said
JudySLFirst(). It's along these lines:
inline PPvoid_t JudySLPrefix (Pcvoid_t PArray, uint8_t *Index,
PJError_t PJError) const {
PPvoid_t PStoredValue;
size_t Prefix_Len=strlen((char*)Index);
char Prefix_Cpy[Prefix_Len+1] = {0};
strcpy (Prefix_Cpy, (char*)Index);
return (PStoredValue=JudySLFirst (PArray, Index,
PJError))!=NULL ? (!strncmp((char*)Index, Prefix_Cpy, Prefix_Len) ?
PStoredValue : NULL) : NULL;
}
Suggest an API and I will consider it.
It occurs to me that a prefix version of both JudySLFirst() and
JudySLNext() would be desirable, for looping through all elements that
share the prefix. However, it's less clear that a JudySLNextPrefix()
would perform well in a loop--wouldn't you have to repeat a lookup for
the prefix leaf each time you call it?
*Suggested API*
If you're just making JudySLFirstPrefix(), the API could be identical to
JudySLFirst(). Seed Index with the prefix, and then it will be
populated with a key value during the call.
If you're also making JudySLNextPrefix(), in order to use it in a loop
it would require both the standard Index and a separate const parameter
for the prefix. So why not make the parameter list identical in both
functions? Namely:
PPvoid_t JudySLFirstPrefix(Pcvoid_t PArray, const uint8_t * Prefix,
uint8_t * Index, PJError_t PJError);
PPvoid_t JudySLNextPrefix(Pcvoid_t PArray, const uint8_t * Prefix,
uint8_t * Index, PJError_t PJError);
*Example code*
A loop for all the elements that have the prefix would be the
following. (As always, Index must be big enough for the largest key on
the tree.)
for (Word_t *PStoredValue=JudySLFirstPrefix(PArray, Prefix, Index,
PJError); PStoredValue!=NULL; PStoredValue=JudySLNextPrefix(PArray,
Prefix, Index, PJError)) {
//do something with PStoredValue and Index
}
Also, depending on how you implement JudySLFirstPrefix(), someone might
be able to get away with calling it like so:
PStoredValue = JudySLFirstPrefix (PArray, Index, Index, PJError);
That would be useful when we don't need the Prefix buffer after calling
JudySLFirstPrefix(). Why create a separate Prefix buffer if we don't
need it? On the other hand, this is a bit sneaky and misunderstandable,
and it doesn't get you very much, so it might be best not to support it.
(see below, there is a
paper that suggest Judy is a weak performer in this area).
Thanks for your interest
Doug
PS. My intuition is it may not improve performance, because of
caching of the
data. But, there are people that say "I am out of touch" with modern
computers.
They have implemented a "bulk" JudyLNext() and got big improvements.
I have
not had a chance to verify.
Are you talking about the Judy1SetArray() and JudyLInsArray() functions
that Alan Silverstein wrote? Those aren't applicable to JudySL, right?
There was a paper presented recently that compared
Judy performance with several other methods. I will look it up, if
your interested.
Improving Judy*Next is on my "to do" list.
I would be interested in that paper, yes. Thank you.
---
Tim Margheim
Neuric Technologies, LLC
------------------------------------------------------------------------------
Monitor your physical, virtual and cloud infrastructure from a single
web console. Get in-depth insight into apps, servers, databases, vmware,
SAP, cloud infrastructure, etc. Download 30-day Free Trial.
Pricing starts from $795 for 25 servers or applications!
http://p.sf.net/sfu/zoho_dev2dev_nov
_______________________________________________
Judy-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/judy-devel
