On 25 March 2014, Dominique Pellé <dominique.pe...@gmail.com> wrote:
> lcd wrote:
>
> > Thanks. Any comment about the red-black trees? The resulting
> > uniq() function should be about as fast as sort(), but having the
> > tree operations implemented as macros would make the code a little
> > awkward.
>
> I don't think that uniq should use a red-black tree. It should only
> remove consecutive items which is done in O(n).
That's how the current uniq() works, and it's now included in
7.4.218.
> If you want to remove all identical items, call sort() followed by
> uniq().
>
> There are valid use cases for calling uniq() on non-sorted array.
We're in violent agreement. :) I'm not saying we should change how
uniq() works now, but add an optional parameter that would tell it to
switch modes.
There is a case for "stable" uniques, where the list is left in the
initial order, but the second and subsequent copies of each element are
removed. This can be accomplished in O(N log(N)) with red-black trees.
That's roughly as fast as sorting, and red-black trees are the right
structure to use when comparisons are more expensive than moving things
around (which is largely the case in VimL).
There's also another aspect: sort() and red-black trees require
total ordering, while removing consecutive dupes only requires equality
comparisons. Total ordering is not always possible, so perhaps we
should also provide a "dumb" (that is, the naive O(N^2)) unique, for
completeness.
To summarize: I'm suggesting we should add an optional parametter to
uniq():
- "sorted" (default when absent) - remove consecutive dupes, O(N);
- "stable" - remove dupes while keeping the initial order, O(N log(N));
- "dumb" - same as stable but require only == comparisons, O(N^2).
> > On the other hand, the same trees (or perhaps splays, implemented
> > in the same header file) might also be useful for speeding up
> > operations involving hash keys.
>
> Balanced tree (red-black tree, splay tree...) are useful for ordered
> dictionaries, but not for hashes. I don't see the link between
> balanced trees and hashes.
When you need to update the value of an element in a hash you have a
key and you need to locate the element. If the key is a string, this is
best done with splays. *shrug*
/lcd
--
--
You received this message from the "vim_dev" maillist.
Do not top-post! Type your reply below the text you are replying to.
For more information, visit http://www.vim.org/maillist.php
---
You received this message because you are subscribed to the Google Groups
"vim_dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to vim_dev+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
