On Sat, Apr 6, 2013 at 1:39 AM, James Hirschorn wrote: Vadim Stadnik wrote ... Augmented trees are non-standard due to different performance guarantees.
At the same these data structures are beneficial for complex algorithms,
since they offer a wider set of more efficient operations compared to
standard containers. The typical performance improvement for one operation is O(log N) against O(N). For less efficient operations these trees
normally provide running time O(log N) against O(1), which is good enough
for many applications. This is very similar to a project I have been working on, with the
intention
of submitting to boost. The new data structure I have implemented is called
a skip list. They can be used in place of balanced trees, and according to
the inventor, insertion and deletion are significantly faster than for
balanced trees (I have not tested this yet). See, e.g. William Pugh. 1990. Skip lists: a probabilistic alternative to balanced
trees. Commun. ACM 33, 6 (June 1990), 668-676. DOI=10.1145/78973.78977
http://doi.acm.org/10.1145/78973.78977 The difference in performance guarantees are much more subtle than you
describe above. For example, skip lists have expected O(log n) insert,
delete and search, versus O(log n). In practice, the expected O(log n) time
is just as good as true O(log n), unless a performance bound is required
with certainty, because the probability of the skip list having height much
larger than log n is extremely low. I also implemented what I called
augmented skip lists, which allow for expected O(log n) rank lookup (i.e.
random access). I wasn't aware of the counter tree library, or else I would
probably have just used it instead of implementing skip lists. I used skip lists to provide "drop in" STL replacements. Now I have
skip_list::set and skip_list::multiset, and I could similarly make
skip_list::map and skip_list::multimap. There is also
augmented_skip_list::set and augmented_skip_list::multiset. For now the
augmented versions have an additional member function nth_element providing
E[O(log n)] random access. Hopefully, this will be helpful towards the goals you have described. IMO, the basic and augmented skip lists that support interfaces of STL
containers would be a valuable addition to Boost library. Skip lists have
an important advantage of relatively simple search and update operations.
Quite obviously, you when you propose these data structures, you will have
the problem of explaining the usefulness of these data structures as they
have non-standard computational complexities of some STL interface
functions.
I am interested in performance of various augmented data structures.
Comparison of deterministic data structures with randomized should be
particularly interesting. Please let me know when you finish and publish
your project. I will be happy to analyze your data structures and test
their performance.
... Are there Boost experts who could volunteer to take responsibility of
review manager for any of these two libraries? Data structures are very interesting to me, and I am in between jobs, so I
have time to review one of these. If I take the time to review, I hope someone will be willing to review my
skip list library, if I complete it and submit it to boost. If you mean the role of the review manager, then I really appreciate that
you agreed. However, there are Boost rules for a formal review and I am not
sure if you are eligible for this role. Hopefully, one of experienced Boost
members will help answer this question.
As for just review, I am interested in any helpful comments and suggestions
concerning advanced data structures.
Regards,
Vadim Stadnik