1 year after
>> I don't know how Judy works internally, but i think you do a search
>> first (like JudyGet) of parameter passed to JudyNext/JudyPrev and then
>> return the next/prev element. With the cursor interface you can store
>> the current pointers (tree path) in the structure and use this info at
>> the next call (without a new search at each call).
...
> But it's important to note that for a
> cache-smart algorithm like libJudy, the overhead time to do this after a
> previous lookup is virtually zero. That's one reason we didn't worry
> about giving you back some kind of quickref/"cursor" for the next call.
It's true that Judy uses cache-smart algorithm. This is why Judy's
iteration is rather efficient. But CPU usage may also be significant
constituent. Two years ago, I wrote C++ stl-like templates that
implement hash tables (maps and sets) using Judy as a backend instead of
linear arrays. I have benchmarks comparing time of
insert/delet/lookup operations and... iteration too.
Benchmarks are here
http://judyhash.sourceforge.net/benchmarks/bench_size65599.html
http://judyhash.sourceforge.net/benchmarks/
See the graphic about an iteration. std::map and std::set (AVL tree)
and google's SPARCE abnd DENSE hashes show a better performance.
I think "cursor" idea for First/Last/Next/Prev functions will make Judy
even more efficient especially for the case when there are lots of
sequencial keys (n, n+1 etc.) keys in the array.
I personally don't see why it cannot be done or why it is conseptually wrong.
The fact that Judy is cache-efficient doesn't make an idea wrong.
--
Best regards, Aleksey Cheusov.
------------------------------------------------------------------------------
This SF.net email is sponsored by:
SourcForge Community
SourceForge wants to tell your story.
http://p.sf.net/sfu/sf-spreadtheword
_______________________________________________
Judy-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/judy-devel
