lcd wrote:
> 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).
I wonder how often these will be used. The goal is not to provide every
possible function, but to provide just enough for Vim plugin writers to
make their stuff work.
> > > 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*
We do want to include useful functions in Vim, but only those which
more than a few people will actually use. It's difficult to decide
which ones are not useful enough. There will always be people who argue
that the function they need is what everybody wants.
Best solution is to have an intermediate level: A Vim plugin that
provides additional library functions, implemented in Vim script. They
will be slower, but at least not every script writer will have to write
them over and over again. And maintenance is distributed and doesn't
depend on Vim releases.
That's why a good plugin system has become more important. If
dependencies are taken care of properly, thus a plugin author can
specify that it depends on another plugin that provides these library
functions, that makes things a lot smoother. Especially when the
functions are provided with the autoload mechanism, thus only the ones
that are actually used get loaded, avoids making startup a lot slower.
I'm thinking of a kind of manifest that specifies these dependencies.
When we standardize that it's still possible to use a choice of plugin
managers.
--
Scientists decoded the first message from an alien civilization:
SIMPLY SEND 6 TIMES 10 TO THE 50 ATOMS OF HYDROGEN TO THE STAR
SYSTEM AT THE TOP OF THE LIST, CROSS OFF THAT STAR SYSTEM, THEN PUT
YOUR STAR SYSTEM AT THE BOTTOM OF THE LIST AND SEND IT TO 100 OTHER
STAR SYSTEMS. WITHIN ONE TENTH GALACTIC ROTATION YOU WILL RECEIVE
ENOUGH HYDROGREN TO POWER YOUR CIVILIZATION UNTIL ENTROPY REACHES ITS
MAXIMUM! IT REALLY WORKS!
/// Bram Moolenaar -- b...@moolenaar.net -- http://www.Moolenaar.net \\\
/// sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ \\\
\\\ an exciting new programming language -- http://www.Zimbu.org ///
\\\ help me help AIDS victims -- http://ICCF-Holland.org ///
--
--
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.
