On 17/11/2012, at 10:43 AM, Tim Margheim wrote:
> One of the most frequent operations I need to perform is a prefix
> search, i.e. "return the first element that starts with Index, or return
> null if nothing does".
>
> I'm currently doing this by calling JudySLNext(). If it returns a
> non-null pointer, but the new Index doesn't start with the prefix, I
> still return null.
>
> Two questions:
> 1.) Does anyone know of a more efficient way to do that with the current
> set of Judy functions?
The searching is close to optimal. The only cost is copying the unwanted
key, i.e. descending into the Judy tree copying characters as we go,
when we don't actually want that key.
However subsequent insertion is expensive since the search
must be repeated, even when the position for a new key is known.
Someone made a "cursor" based version of Judy that fixed this,
however that code is not re-entrant and therefore unacceptable
to me at least, because their modified Judy only supported
one cursor.
The existing function set is "thread safe" in the sense that
provided each function call is protected by a lock,
and provided one deals with the extra flow required to store
a value after insertion. Indeed, Felix uses Judy for garbage
collection in a multi-threaded environment, with appropriate
locks to ensure the base operations are atomic.
> 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?
A more consistent function would be
find-between
given two keys, find key satisfying
< <= > >-=
the first key, and
< <= > >=
on the second key. in other words
find > <= k1 k2
would find the first key k > k1 and also <= k2,
i.e. "findFirst with Bound". Your requirement is than
a special case:
k > prefix k< prefix'
where prefix' is the same as prefix except incremented (lexicographically)
by 1. This would allow you to search for names like:
SmithJ upto SmithP
which cannot be done with just prefix Smith.
--
john skaller
[email protected]
http://felix-lang.org
------------------------------------------------------------------------------
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
