Re: [patch] add sortuniq() function
Andre Sihera wrote: > On 27/03/14 06:42, Bram Moolenaar wrote: > > Since many plugins consist of several files, and we would like to check > > the dependencies before downloading all the files, the best place for > > these dependencies is to have them in a separate manifest file. > > > > Another advantage is that there would be one central place where plugin > > authors upload the newest manifest file. For the moment assume that's > > the script storage in vim.org. This also solves the problem of scripts > > on vim.org being one file. > > > > The manifest can specify any place, including git repo's, where to fetch > > the files. > > > > One could also fetch a manifest from elsewhere (e.g. by simply editing > > it) and then run the plugin installer/updater. The dependencies can be > > in the form of just a plugin ID, to be found in the central repository, > > but it could also be the URL of that dependency's manifest file. That > > way a plugin author can also publish alpha and beta versions, with > > yet unreleased dependencies, before making the fully tested plugin > > available at vim.org. > > > > Using URLs for the location is flexible and easy to debug. Using single > > files avoids problems with unpacking archives, the need to first install > > tools, etc. I believe all respositories support downloading individual > > files. What this does NOT support is further developing the plugin or > > merging local changes. Normal users won't need that. > > > > Have you ever had the opportunity of doing ruby programming and having to > use "bundle" or some other "gem" manager? What you're proposing is very > similar and I would recommend you install ruby, play with it, and get to > know the "gem" managers before embarking down this path. > > Due to the fact that such systems give the impression that it is "easy" for > the user to upgrade to the latest version, it engenders a cavalier attitude > amongst plugin writers that proper test/release control is unnecessary; > they just dump out the latest version without testing because if it contains > a bug they can just fix it and dump out yet another version with the fix. > > Particularly in the workplace, and I speak from personal experience, these > kinds of systems do waste more time than they save due to everything > grinding > to a halt due when one plug-in in a dependency hierarchy breaks, normally > because the plug-in author couldn't be bothered to test their code > adequately > before releasing it. Add to this the usual system integrity problems that > accompany network-based systems and we have more headaches in the making. The plugin system can't do much here, it's really up to the plugin author to be testing the changes. We can support "alpha" and "beta" versions, but it's still the author who decides what gets released. There are two main reasons for a new version: - New features added. In this case it depends on a few users to try them out. That means there must be users who really want these new features. - A problem is reported, the plugin author fixes it and points the bug reporter to a new version to verify the problem is fixed. Only after confirmation the new version is released. Both require being able for a user to point to a specific, unreleased version of a plugin. Doing that with a URL to the manifest would work. > If you do implement this system, may I strongly suggest that you invest more > time in the backup/rollback features than the install/management features? > That way when things go wrong we can be sure we can get back to where we > want > to get back to as quickly and as painlessly as possible. Good point, besides being able to try out a new plugin, which means it must be easy to remove it again, we should also have an easy way to go back to a previous version. And that means to before the last time the plugins were updated. For a user who knows what he is doing he could perhaps select a specific version of a specific plugin, but for most users it would be: 1. Install various plugins, use them. 2. Run "update all plugins" 3. Use the new versions. 4. If a problem is noticed, do a "go back one step", which means undo the last update. A multi-level undo is needed, since it can be a few days before you notice a problem. -- Engineers understand that their appearance only bothers other people and therefore it is not worth optimizing. (Scott Adams - The Dilbert principle) /// 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 ---
Re: [patch] add sortuniq() function
On 27/03/14 06:42, Bram Moolenaar wrote: Since many plugins consist of several files, and we would like to check the dependencies before downloading all the files, the best place for these dependencies is to have them in a separate manifest file. Another advantage is that there would be one central place where plugin authors upload the newest manifest file. For the moment assume that's the script storage in vim.org. This also solves the problem of scripts on vim.org being one file. The manifest can specify any place, including git repo's, where to fetch the files. One could also fetch a manifest from elsewhere (e.g. by simply editing it) and then run the plugin installer/updater. The dependencies can be in the form of just a plugin ID, to be found in the central repository, but it could also be the URL of that dependency's manifest file. That way a plugin author can also publish alpha and beta versions, with yet unreleased dependencies, before making the fully tested plugin available at vim.org. Using URLs for the location is flexible and easy to debug. Using single files avoids problems with unpacking archives, the need to first install tools, etc. I believe all respositories support downloading individual files. What this does NOT support is further developing the plugin or merging local changes. Normal users won't need that. Have you ever had the opportunity of doing ruby programming and having to use "bundle" or some other "gem" manager? What you're proposing is very similar and I would recommend you install ruby, play with it, and get to know the "gem" managers before embarking down this path. Due to the fact that such systems give the impression that it is "easy" for the user to upgrade to the latest version, it engenders a cavalier attitude amongst plugin writers that proper test/release control is unnecessary; they just dump out the latest version without testing because if it contains a bug they can just fix it and dump out yet another version with the fix. Particularly in the workplace, and I speak from personal experience, these kinds of systems do waste more time than they save due to everything grinding to a halt due when one plug-in in a dependency hierarchy breaks, normally because the plug-in author couldn't be bothered to test their code adequately before releasing it. Add to this the usual system integrity problems that accompany network-based systems and we have more headaches in the making. If you do implement this system, may I strongly suggest that you invest more time in the backup/rollback features than the install/management features? That way when things go wrong we can be sure we can get back to where we want to get back to as quickly and as painlessly as possible. Cheers, -- -- 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.
Re: [patch] add sortuniq() function
Charles Campbell wrote: > Bram Moolenaar wrote: > > 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. > FWIW, GLVS (getscript) supports plugin dependencies. A number of my > plugins have lines such as > >" GetLatestVimScripts: 1066 1 cecutil.vim > > in scripts other than cecutil which tell getscript that the current > script also depends upon cecutil.vim. So is it better for the plugin > writer to explicitly state such dependencies as getscript promotes, or > is it better to have a centralized manifest with them. How will that > manifest be maintained, updated, etc? Since many plugins consist of several files, and we would like to check the dependencies before downloading all the files, the best place for these dependencies is to have them in a separate manifest file. Another advantage is that there would be one central place where plugin authors upload the newest manifest file. For the moment assume that's the script storage in vim.org. This also solves the problem of scripts on vim.org being one file. The manifest can specify any place, including git repo's, where to fetch the files. One could also fetch a manifest from elsewhere (e.g. by simply editing it) and then run the plugin installer/updater. The dependencies can be in the form of just a plugin ID, to be found in the central repository, but it could also be the URL of that dependency's manifest file. That way a plugin author can also publish alpha and beta versions, with yet unreleased dependencies, before making the fully tested plugin available at vim.org. Using URLs for the location is flexible and easy to debug. Using single files avoids problems with unpacking archives, the need to first install tools, etc. I believe all respositories support downloading individual files. What this does NOT support is further developing the plugin or merging local changes. Normal users won't need that. -- An easy way to determine if you have enough teamwork to be doomed is simply to measure how long it takes from the time you decide to go to lunch together until the time you actually eat. (Scott Adams - The Dilbert principle) /// 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.
[patch] stable uniques (was: Re: [patch] add sortuniq() function)
On 26 March 2014, LCD 47 wrote:
[...]
> FWIW, I have a preliminary implementation, and I ran a few
> benchmarks. Here are few numbers:
[...]
Patch attached below. The patch adds an optional parameter {mode}
to uniq():
uniq({list} [, {mode} [, {func} [, {dict}]]])
If {mode} is absent, or if it is set to "sorted", uniq() removes
only consecutive dupes; if {mode} is set to "stable", uniq() removes all
dupes without changing the order of the items in {list}.
Sadly, the new syntax can't be backwards compatible while still
remaining useful.
If you're curious about the numbers I mentioned in my previous
message, I also attached a small benchmark script. You need +python to
run it (Python is used only to generate 1 mil. of random numbers).
Several obvious improvements are possible, f.i. better checks for
sys/tree.h, or perhaps re-implementing outside sys/tree.h the few
functions for red-black trees that we're actually using. Given the
reactions so far to all this, I'll leave the pleasure of implementing
those improvements to somebody else.
/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.
diff -r d96e8fbc3747 runtime/doc/eval.txt
--- a/runtime/doc/eval.txt Tue Mar 25 18:24:23 2014 +0100
+++ b/runtime/doc/eval.txt Wed Mar 26 19:57:07 2014 +0200
@@ -2006,7 +2006,7 @@
type( {name}) Number type of variable {name}
undofile( {name}) String undo file name for {name}
undotree() Listundo file tree
-uniq( {list} [, {func} [, {dict}]])
+uniq( {list} [, {mode} [, {func} [, {dict}]]])
Listremove adjacent duplicates from a list
values( {dict})Listvalues in {dict}
virtcol( {expr}) Number screen column of cursor or mark
@@ -5978,7 +5978,7 @@
The number can be used with the |:tab| command.
-tabpagewinnr({tabarg}, [{arg}])*tabpagewinnr()*
+tabpagewinnr({tabarg}[, {arg}])*tabpagewinnr()*
Like |winnr()| but for tab page {tabarg}.
{tabarg} specifies the number of tab page to be used.
{arg} is used like with |winnr()|:
@@ -5996,7 +5996,7 @@
for the current buffer. This is the 'tags' option expanded.
-taglist({expr})
*taglist()*
+taglist({expr})*taglist()*
Returns a list of tags matching the regular expression {expr}.
Each list item is a dictionary with at least the following
entries:
@@ -6178,10 +6178,14 @@
blocks. Each item may again have an "alt"
item.
-uniq({list} [, {func} [, {dict}]]) *uniq()* *E882*
- Remove second and succeeding copies of repeated adjacent
- {list} items in-place. Returns {list}. If you want a list
- to remain unmodified make a copy first: >
+uniq({list} [, {mode} [, {func} [, {dict}]]]) *uniq()* *E882*
+Eliminate duplicates from {list}. If {mode} is absent, or if
+it is set to "sorted", remove second and succeeding copies of
+repeated adjacent {list} items. If {mode} is set to "stable",
+remove second and succeeding copies of {list} items, regardless
+of whether they are adjacent or not. The operation is done
+in-place. If you want the |List| to remain unmodified make a
+copy first: >
:let newlist = uniq(copy(mylist))
< The default compare function uses the string representation of
each item. For the use of {func} and {dict} see |sort()|.
diff -r d96e8fbc3747 src/config.h.in
--- a/src/config.h.in Tue Mar 25 18:24:23 2014 +0100
+++ b/src/config.h.in Wed Mar 26 19:57:07 2014 +0200
@@ -258,6 +258,7 @@
#undef HAVE_SYS_SYSINFO_H
#undef HAVE_SYS_SYSTEMINFO_H
#undef HAVE_SYS_TIME_H
+#undef HAVE_SYS_TREE_H
#undef HAVE_SYS_TYPES_H
#undef HAVE_SYS_UTSNAME_H
#undef HAVE_TERMCAP_H
diff -r d96e8fbc3747 src/configure.in
--- a/src/configure.in Tue Mar 25 18:24:23 2014 +0100
+++ b/src/configure.in Wed Mar 26 19:57:07 2014 +0200
@@ -2797,7 +2797,8 @@
libc.h sys/statfs.h poll.h sys/poll.h pwd.h \
utime.h sys/param.h libintl.h libgen.h \
util/debug.h util/msg18n.h frame.h sys/
Re: [patch] add sortuniq() function
Bram Moolenaar wrote: 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. FWIW, GLVS (getscript) supports plugin dependencies. A number of my plugins have lines such as " GetLatestVimScripts: 1066 1 cecutil.vim in scripts other than cecutil which tell getscript that the current script also depends upon cecutil.vim. So is it better for the plugin writer to explicitly state such dependencies as getscript promotes, or is it better to have a centralized manifest with them. How will that manifest be maintained, updated, etc? Regards, Chip Campbell -- -- 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.
Re: [patch] add sortuniq() function
On 26 March 2014, Bram Moolenaar wrote:
>
> lcd wrote:
[...]
> > 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.
Well, in the particular case of "stable" uniques it isn't really a
matter of convenience, but rather a matter of being able to do it at all
for useful data sizes. For lists of elements that can be meaningfully
stringified, things are not that bad, you can do something like this:
function! StableUniq(list)
let seen = {}
let uniques = []
for elem in a:list
if !has_key(seen, elem)
let seen[elem] = 1
call add(uniques, elem)
endif
endfor
return uniques
endfunction
However, this doesn't work if the elements are dicts. Dicts can
be stringified, but equal dicts can produce different stringifications
because of the order of keys. Good luck doing a stable update in VimL
for a list of, say, 1k dicts.
So, realistically, where do you get a list of 1k dicts? Why, I just
got a few from getloclist().
FWIW, I have a preliminary implementation, and I ran a few
benchmarks. Here are few numbers:
(1) C stable unique without a custom comparison function is 12% slower
than the eqivalent sort;
(2) C stable unique with a custom comparison function is marginally
faster (< 2%) than the equivalent sort;
(3) C stable unique without a custom comparison function, for 1 mil.
random numbers, with ~40% duplicates: 4.7 s;
(4) VimL function StableUniq() above, for 1 mil. random numbers: 5.3 s;
(4) C stable unique for with a custom comparison function, for 1 mil.
random numbers: 44.3 s;
(5) naive O(N^2) VimL stable unique for 1k dicts: 5.1 s.
Case (5) was actually my motivation for getting involved in all
this.
The "sorted" unique you just included in Vim is actually the least
interesting case: it's O(N), it's trivial to write in VimL, and just
about any implementation is fast enough. As the good Dr. Chip points
out, it has no business being in Vim. The interesting case is the
"stable" one.
> > > > 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.
[...]
Here I was actually referring to a speedup in the way (all) dicts
work. It would affect (or rather benefit) everybody. But, whetever;
there are things in life more interesting than optimising Vim dicts.
/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.
Re: [patch] add sortuniq() function
lcd wrote: > On 25 March 2014, Dominique Pellé 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.
Re: [patch] add sortuniq() function
On 25 March 2014, Dominique Pellé 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.
Re: [patch] add sortuniq() function
On Mar 25, 2014 11:41 PM, "Charles E Campbell" wrote: > > LCD 47 wrote: >> >> On 19 March 2014, Cade Forester wrote: Looks like you made a copy of f_sort() and modified it a bit. That's a lot of duplicate code. Better move the common stuff into a function that's used by both sort() and sortuniq(). >>> >>> Fixed >> >> How about separating it from sort()? That is, an uniq() function >> that would remove duplicates from an already sorted list (results would >> be undefined if the input list is not sorted). That would be consistent >> with how uniq(1) works on UNIX. >> > I'm not convinced that it should even be in the vim source. (ducking spitballs now) The only reason I see for it is to support Windows, as it is command-line tool poor. Otherwise, ... > Why not use a plugin? Why not use system() (and macos's or linux's uniq)? Going through a list to do uniq should be an O(n) action. Sorting is O(n)log(n) (or O(n^2) for some algorithms), and so speed is more important. > > This process logically would re-invent lots of tools and embed them in vim (admittedly, uniq is likely to be a small one). However, there's lots of tools that Windows lacks that "would be nice" to have -- but should vim have it? It is convenience-for-maintainability trade-off. One of the reasons I like python is its standard library: for 90% of needs I use just it. And, hell, this is very convenient. But most likely hard to maintain. Coding this in C is only an optimization: if you have lots of VimL code it easily starts to become too slow. This does not matter how sort is compared to uniq: if you have thousands iterations you take a code generator that removes whitespaces, truncates command names and joins a sequence of Ex commands into a single one (though only the last was beneficial enough, first two only won very few ms, but were much easier to implement) and hope it is enough. I would not say I need fast uniq() though: I never needed uniq() not in shell at all. But others may need. > > Regards, > Chip Campbell > > > > -- > -- > 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. -- -- 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.
Re: [patch] add sortuniq() function
LCD 47 wrote: On 19 March 2014, Cade Forester wrote: Looks like you made a copy of f_sort() and modified it a bit. That's a lot of duplicate code. Better move the common stuff into a function that's used by both sort() and sortuniq(). Fixed How about separating it from sort()? That is, an uniq() function that would remove duplicates from an already sorted list (results would be undefined if the input list is not sorted). That would be consistent with how uniq(1) works on UNIX. I'm not convinced that it should even be in the vim source. (ducking spitballs now) The only reason I see for it is to support Windows, as it is command-line tool poor. Otherwise, ... Why not use a plugin? Why not use system() (and macos's or linux's uniq)? Going through a list to do uniq should be an O(n) action. Sorting is O(n)log(n) (or O(n^2) for some algorithms), and so speed is more important. This process logically would re-invent lots of tools and embed them in vim (admittedly, uniq is likely to be a small one). However, there's lots of tools that Windows lacks that "would be nice" to have -- but should vim have it? Regards, Chip Campbell -- -- 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.
Re: [patch] add sortuniq() function
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. > > /lcd I don't think that uniq should use a red-black tree. It should only remove consecutive items which is done in O(n). 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. > 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. Regards Dominique -- -- 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.
Re: [patch] add sortuniq() function
On 25 March 2014, Bram Moolenaar wrote: > > lcd wrote: > > > > > On 21 March 2014, Cade Forester wrote: > > > > > > How about separating it from sort()? That is, an uniq() > > > > > > function that would remove duplicates from an already sorted > > > > > > list (results would be undefined if the input list is not > > > > > > sorted). That would be consistent with how uniq(1) works on > > > > > > UNIX. > > > > > > > > > > This patch add uniq() function. uniq(list) will remove copies > > > > > of repeated adjacent items > > > > > > > > There is a problem with this patch: it removes the > > > > duplicates on the fly, so if the comparison function fails on > > > > the second or subsequent call the list is still modified. In > > > > contrast, sort() restores the list to the initial state if the > > > > comparison fails at some point. > > > > > > > > I'm attaching bellow my attempt to a fix. I also merged > > > > f_sort() and f_uniq() in a single function, and made some minor > > > > optimisations. > > > > > > > > On a related topic: adding an efficient "stable unique" > > > > would be relatively straightforward too, using plain red-black > > > > trees. Now, red-black trees are implemented as a header (namely > > > > sys/tree.h) on *BSD, but not on other systems. Any comment > > > > on the preferred way to handle this? I'd suggest testing for > > > > the existence of sys/tree.h in autoconf, and also including a > > > > stripped down copy of it from, say, OpenBSD, for the systems > > > > that don't have it. > > > > > > There are a few problems with this implementation. > > > > > > The li_prev pointer is not updated. > > > > Right: this comes from the initial patch. I should have checked > > what is actually going on. > > > > > When the first item is not a list the error is for sort(), even > > > when uniq() is used. > > > > Updated patch below. > > Thanks. There are a few remaining issues but it's easier to fix them > than to explain the problems. 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. 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. /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.
Re: [patch] add sortuniq() function
lcd wrote: > > > On 21 March 2014, Cade Forester wrote: > > > > > How about separating it from sort()? That is, an uniq() > > > > > function that would remove duplicates from an already sorted > > > > > list (results would be undefined if the input list is not > > > > > sorted). That would be consistent with how uniq(1) works on > > > > > UNIX. > > > > > > > > This patch add uniq() function. uniq(list) will remove copies of > > > > repeated adjacent items > > > > > > There is a problem with this patch: it removes the duplicates > > > on the fly, so if the comparison function fails on the second or > > > subsequent call the list is still modified. In contrast, sort() > > > restores the list to the initial state if the comparison fails at > > > some point. > > > > > > I'm attaching bellow my attempt to a fix. I also merged > > > f_sort() and f_uniq() in a single function, and made some minor > > > optimisations. > > > > > > On a related topic: adding an efficient "stable unique" would be > > > relatively straightforward too, using plain red-black trees. Now, > > > red-black trees are implemented as a header (namely sys/tree.h) on > > > *BSD, but not on other systems. Any comment on the preferred way to > > > handle this? I'd suggest testing for the existence of sys/tree.h in > > > autoconf, and also including a stripped down copy of it from, say, > > > OpenBSD, for the systems that don't have it. > > > > There are a few problems with this implementation. > > > > The li_prev pointer is not updated. > > Right: this comes from the initial patch. I should have checked > what is actually going on. > > > When the first item is not a list the error is for sort(), even when > > uniq() is used. > > Updated patch below. Thanks. There are a few remaining issues but it's easier to fix them than to explain the problems. -- ALL: A witch! A witch! WITCH: It's a fair cop. ALL: Burn her! Burn her! Let's make her into a ladder. "Monty Python and the Holy Grail" PYTHON (MONTY) PICTURES LTD /// 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.
Re: [patch] add sortuniq() function
On 25 March 2014, LCD 47 wrote:
> On 25 March 2014, Bram Moolenaar wrote:
> >
> > lcd wrote:
> >
> > > On 21 March 2014, Cade Forester wrote:
> > > > > How about separating it from sort()? That is, an uniq()
> > > > > function that would remove duplicates from an already sorted
> > > > > list (results would be undefined if the input list is not
> > > > > sorted). That would be consistent with how uniq(1) works on
> > > > > UNIX.
> > > >
> > > > This patch add uniq() function. uniq(list) will remove copies of
> > > > repeated adjacent items
> > >
> > > There is a problem with this patch: it removes the duplicates
> > > on the fly, so if the comparison function fails on the second or
> > > subsequent call the list is still modified. In contrast, sort()
> > > restores the list to the initial state if the comparison fails at
> > > some point.
> > >
> > > I'm attaching bellow my attempt to a fix. I also merged
> > > f_sort() and f_uniq() in a single function, and made some minor
> > > optimisations.
> > >
> > > On a related topic: adding an efficient "stable unique"
> > > would be relatively straightforward too, using plain red-black
> > > trees. Now, red-black trees are implemented as a header (namely
> > > sys/tree.h) on *BSD, but not on other systems. Any comment on
> > > the preferred way to handle this? I'd suggest testing for the
> > > existence of sys/tree.h in autoconf, and also including a stripped
> > > down copy of it from, say, OpenBSD, for the systems that don't
> > > have it.
> >
> > There are a few problems with this implementation.
> >
> > The li_prev pointer is not updated.
>
> Right: this comes from the initial patch. I should have checked
> what is actually going on.
>
> > When the first item is not a list the error is for sort(), even when
> > uniq() is used.
>
> Updated patch below.
... And another wrong message. How embarrasing.
/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.
diff -r 798d83d15327 runtime/doc/change.txt
--- a/runtime/doc/change.txtTue Mar 25 15:34:48 2014 +0100
+++ b/runtime/doc/change.txtTue Mar 25 17:18:50 2014 +0200
@@ -1650,7 +1650,7 @@
7. Sorting text*sorting*
Vim has a sorting function and a sorting command. The sorting function can be
-found here: |sort()|.
+found here: |sort()|, |uniq()|.
*:sor* *:sort*
:[range]sor[t][!] [i][u][r][n][x][o] [/{pattern}/]
diff -r 798d83d15327 runtime/doc/eval.txt
--- a/runtime/doc/eval.txt Tue Mar 25 15:34:48 2014 +0100
+++ b/runtime/doc/eval.txt Tue Mar 25 17:18:50 2014 +0200
@@ -327,6 +327,7 @@
Changing the order of items in a list: >
:call sort(list)" sort a list alphabetically
:call reverse(list) " reverse the order of items
+ :call uniq(sort(list)) " sort and remove duplicates
For loop ~
@@ -2005,6 +2006,8 @@
type( {name}) Number type of variable {name}
undofile( {name}) String undo file name for {name}
undotree() Listundo file tree
+uniq( {list} [, {func} [, {dict}]])
+ Listremove adjacent duplicates
values( {dict})Listvalues in {dict}
virtcol( {expr}) Number screen column of cursor or mark
visualmode( [expr])String last visual mode used
@@ -6169,6 +6172,14 @@
blocks. Each item may again have an "alt"
item.
+uniq({list} [, {func} [, {dict}]]) *uniq()* *E702*
+ Remove second and succeeding copies of repeated adjacent
+ {list} items in-place. Returns {list}. If you want a list
+ to remain unmodified make a copy first: >
+ :let newlist = uniq(copy(mylist))
+< Compare function uses the string representation of each item.
+ For the use of {func} and {dict} see |sort()|.
+
values({dict}) *values()*
Return a |List| with all the values of {dict}. The |List| is
in arbitrary order.
diff -r 798d83d15327 runtime/doc/usr_41.txt
--- a/runtime/doc/usr_41.txtTue Mar 25 15:34:48 2014 +0100
+++ b/runtime/doc/usr_41.txtTue Mar 25 17:18:50 2014 +0200
@@ -623,6 +623,7 @@
map() change each List item
sort() sort a List
reverse()
Re: [patch] add sortuniq() function
On 25 March 2014, Bram Moolenaar wrote:
>
> lcd wrote:
>
> > On 21 March 2014, Cade Forester wrote:
> > > > How about separating it from sort()? That is, an uniq()
> > > > function that would remove duplicates from an already sorted
> > > > list (results would be undefined if the input list is not
> > > > sorted). That would be consistent with how uniq(1) works on
> > > > UNIX.
> > >
> > > This patch add uniq() function. uniq(list) will remove copies of
> > > repeated adjacent items
> >
> > There is a problem with this patch: it removes the duplicates
> > on the fly, so if the comparison function fails on the second or
> > subsequent call the list is still modified. In contrast, sort()
> > restores the list to the initial state if the comparison fails at
> > some point.
> >
> > I'm attaching bellow my attempt to a fix. I also merged
> > f_sort() and f_uniq() in a single function, and made some minor
> > optimisations.
> >
> > On a related topic: adding an efficient "stable unique" would be
> > relatively straightforward too, using plain red-black trees. Now,
> > red-black trees are implemented as a header (namely sys/tree.h) on
> > *BSD, but not on other systems. Any comment on the preferred way to
> > handle this? I'd suggest testing for the existence of sys/tree.h in
> > autoconf, and also including a stripped down copy of it from, say,
> > OpenBSD, for the systems that don't have it.
>
> There are a few problems with this implementation.
>
> The li_prev pointer is not updated.
Right: this comes from the initial patch. I should have checked
what is actually going on.
> When the first item is not a list the error is for sort(), even when
> uniq() is used.
Updated patch below.
/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.
diff -r d2ef98a43b5d runtime/doc/change.txt
--- a/runtime/doc/change.txtMon Mar 24 19:44:09 2014 +0100
+++ b/runtime/doc/change.txtTue Mar 25 16:49:48 2014 +0200
@@ -1650,7 +1650,7 @@
7. Sorting text*sorting*
Vim has a sorting function and a sorting command. The sorting function can be
-found here: |sort()|.
+found here: |sort()|, |uniq()|.
*:sor* *:sort*
:[range]sor[t][!] [i][u][r][n][x][o] [/{pattern}/]
diff -r d2ef98a43b5d runtime/doc/eval.txt
--- a/runtime/doc/eval.txt Mon Mar 24 19:44:09 2014 +0100
+++ b/runtime/doc/eval.txt Tue Mar 25 16:49:48 2014 +0200
@@ -327,6 +327,7 @@
Changing the order of items in a list: >
:call sort(list)" sort a list alphabetically
:call reverse(list) " reverse the order of items
+ :call uniq(sort(list)) " sort and remove duplicates
For loop ~
@@ -2005,6 +2006,8 @@
type( {name}) Number type of variable {name}
undofile( {name}) String undo file name for {name}
undotree() Listundo file tree
+uniq( {list} [, {func} [, {dict}]])
+ Listremove adjacent duplicates
values( {dict})Listvalues in {dict}
virtcol( {expr}) Number screen column of cursor or mark
visualmode( [expr])String last visual mode used
@@ -6169,6 +6172,14 @@
blocks. Each item may again have an "alt"
item.
+uniq({list} [, {func} [, {dict}]]) *uniq()* *E702*
+ Remove second and succeeding copies of repeated adjacent
+ {list} items in-place. Returns {list}. If you want a list
+ to remain unmodified make a copy first: >
+ :let newlist = uniq(copy(mylist))
+< Compare function uses the string representation of each item.
+ For the use of {func} and {dict} see |sort()|.
+
values({dict}) *values()*
Return a |List| with all the values of {dict}. The |List| is
in arbitrary order.
diff -r d2ef98a43b5d runtime/doc/usr_41.txt
--- a/runtime/doc/usr_41.txtMon Mar 24 19:44:09 2014 +0100
+++ b/runtime/doc/usr_41.txtTue Mar 25 16:49:48 2014 +0200
@@ -623,6 +623,7 @@
map() change each List item
sort() sort a List
reverse() reverse the order of a List
+ uniq() remove copies of repeated adjacent items
split() split a String into a List
Re: [patch] add sortuniq() function
lcd wrote: > On 21 March 2014, Cade Forester wrote: > > > How about separating it from sort()? That is, an uniq() > > > function that would remove duplicates from an already sorted list > > > (results would be undefined if the input list is not sorted). That > > > would be consistent with how uniq(1) works on UNIX. > > > > This patch add uniq() function. uniq(list) will remove copies of > > repeated adjacent items > > There is a problem with this patch: it removes the duplicates on the > fly, so if the comparison function fails on the second or subsequent > call the list is still modified. In contrast, sort() restores the list > to the initial state if the comparison fails at some point. > > I'm attaching bellow my attempt to a fix. I also merged f_sort() > and f_uniq() in a single function, and made some minor optimisations. > > On a related topic: adding an efficient "stable unique" would be > relatively straightforward too, using plain red-black trees. Now, > red-black trees are implemented as a header (namely sys/tree.h) on *BSD, > but not on other systems. Any comment on the preferred way to handle > this? I'd suggest testing for the existence of sys/tree.h in autoconf, > and also including a stripped down copy of it from, say, OpenBSD, for > the systems that don't have it. There are a few problems with this implementation. The li_prev pointer is not updated. When the first item is not a list the error is for sort(), even when uniq() is used. -- It is too bad that the speed of light hasn't kept pace with the changes in CPU speed and network bandwidth. -- /// 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.
RE: [patch] add sortuniq() function
Bram said: > Thanks. I'll add it in the todo list. Although we may add uniq() instead. > Consistancy with Unix is useful. I just wanted to weigh in on the idea of adding uniq() instead of sortuniq(). The modularity of Unix commands is great and all, but when working with big data sets you want to scale as efficiently as possible. In Unix, "sort -u" is more efficient than "sort | uniq". The difference can be dramatic. (Note: Not all Unix "sort" commands support -u.) If a combined sortuniq() turns out to be the most efficient implementation, then I'd urge you to go with that. Of course a standalone uniq() could also be provided, but use cases for uniq() seem to be fairly niche outside of sorting. -- -- 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.
Re: [patch] add sortuniq() function
On 25 March 2014, LCD 47 wrote: [...] > I'm attaching bellow my attempt to a fix. I also merged f_sort() > and f_uniq() in a single function, and made some minor optimisations. [...] > +static int (*item_compare_func_ptr)__ARGS((const void *, const void > *s2)); [...] ^^ Cut & waste error. :) On a side note: this is a global variable in preparation for use in the red-black trees macros. /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.
Re: [patch] add sortuniq() function
On 21 March 2014, Cade Forester wrote:
> > How about separating it from sort()? That is, an uniq()
> > function that would remove duplicates from an already sorted list
> > (results would be undefined if the input list is not sorted). That
> > would be consistent with how uniq(1) works on UNIX.
>
> This patch add uniq() function. uniq(list) will remove copies of
> repeated adjacent items
There is a problem with this patch: it removes the duplicates on the
fly, so if the comparison function fails on the second or subsequent
call the list is still modified. In contrast, sort() restores the list
to the initial state if the comparison fails at some point.
I'm attaching bellow my attempt to a fix. I also merged f_sort()
and f_uniq() in a single function, and made some minor optimisations.
On a related topic: adding an efficient "stable unique" would be
relatively straightforward too, using plain red-black trees. Now,
red-black trees are implemented as a header (namely sys/tree.h) on *BSD,
but not on other systems. Any comment on the preferred way to handle
this? I'd suggest testing for the existence of sys/tree.h in autoconf,
and also including a stripped down copy of it from, say, OpenBSD, for
the systems that don't have it.
/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.
diff -r d2ef98a43b5d runtime/doc/change.txt
--- a/runtime/doc/change.txtMon Mar 24 19:44:09 2014 +0100
+++ b/runtime/doc/change.txtTue Mar 25 01:28:04 2014 +0200
@@ -1650,7 +1650,7 @@
7. Sorting text*sorting*
Vim has a sorting function and a sorting command. The sorting function can be
-found here: |sort()|.
+found here: |sort()|, |uniq()|.
*:sor* *:sort*
:[range]sor[t][!] [i][u][r][n][x][o] [/{pattern}/]
diff -r d2ef98a43b5d runtime/doc/eval.txt
--- a/runtime/doc/eval.txt Mon Mar 24 19:44:09 2014 +0100
+++ b/runtime/doc/eval.txt Tue Mar 25 01:28:04 2014 +0200
@@ -327,6 +327,7 @@
Changing the order of items in a list: >
:call sort(list)" sort a list alphabetically
:call reverse(list) " reverse the order of items
+ :call uniq(sort(list)) " sort and remove duplicates
For loop ~
@@ -2005,6 +2006,8 @@
type( {name}) Number type of variable {name}
undofile( {name}) String undo file name for {name}
undotree() Listundo file tree
+uniq( {list} [, {func} [, {dict}]])
+ Listremove adjacent duplicates
values( {dict})Listvalues in {dict}
virtcol( {expr}) Number screen column of cursor or mark
visualmode( [expr])String last visual mode used
@@ -6169,6 +6172,14 @@
blocks. Each item may again have an "alt"
item.
+uniq({list} [, {func} [, {dict}]]) *uniq()* *E702*
+ Remove second and succeeding copies of repeated adjacent
+ {list} items in-place. Returns {list}. If you want a list
+ to remain unmodified make a copy first: >
+ :let newlist = uniq(copy(mylist))
+< Compare function uses the string representation of each item.
+ For the use of {func} and {dict} see |sort()|.
+
values({dict}) *values()*
Return a |List| with all the values of {dict}. The |List| is
in arbitrary order.
diff -r d2ef98a43b5d runtime/doc/usr_41.txt
--- a/runtime/doc/usr_41.txtMon Mar 24 19:44:09 2014 +0100
+++ b/runtime/doc/usr_41.txtTue Mar 25 01:28:04 2014 +0200
@@ -623,6 +623,7 @@
map() change each List item
sort() sort a List
reverse() reverse the order of a List
+ uniq() remove copies of repeated adjacent items
split() split a String into a List
join() join List items into a String
range() return a List with a sequence of numbers
diff -r d2ef98a43b5d runtime/doc/version7.txt
--- a/runtime/doc/version7.txt Mon Mar 24 19:44:09 2014 +0100
+++ b/runtime/doc/version7.txt Tue Mar 25 01:28:04 2014 +0200
@@ -942,6 +942,7 @@
|tagfiles()| List with tags file names
|taglist()|get list of matching tags (Yegappan Lakshmanan)
|tr()| trans
Re: [patch] add sortuniq() function
> > I think some of us would be rather surprised if the result weren't > > [1,2,3]. > > Well, the more experienced among us would know that full (unsorted) > unique would be nice, but expensive. :) It eluded my mind that vimscript aims at high performance computing. I was talking about user expectations given that probably the majority of vim users are ruby, python, javascript developers -- at least from my perspective, which could be biased. -- -- 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.
Re: [patch] add sortuniq() function
On 22 March 2014, Michael Reiland wrote: > On 3/22/2014 12:51 PM, LCD 47 wrote: [...] > > Well, there is another function I seem to be reinventing over > >and over again, namely any() (returns true if all items in a list or > >dict meet a criterion). [...] > > Did you misspeak there? I would expect any to return true if even 1 > item met the criterion. What you described sounds like "all" to me. Yes, of course, sorry about that. Well, they are essentially the same thing, any(cond) == !all(!cond). /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.
Re: [patch] add sortuniq() function
Cade Forester wrote: > > Looks like you made a copy of f_sort() and modified it a bit. That's a > > lot of duplicate code. Better move the common stuff into a function > > that's used by both sort() and sortuniq(). > > Fixed Thanks. I'll add it in the todo list. Although we may add uniq() instead. Consistancy with Unix is useful. -- Kiss me twice. I'm schizophrenic. /// 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.
Re: [patch] add sortuniq() function
On Fr, 21 Mär 2014, LCD 47 wrote: > On 21 March 2014, lith wrote: > > > In other words, I'd expect this for example: > > > > > > :echo uniq([1, 2, 3, 3, 2, 2, 1]) > > > [1, 2, 3, 2, 1] > > > > I think some of us would be rather surprised if the result weren't > > [1,2,3]. > > Well, the more experienced among us would know that full (unsorted) > unique would be nice, but expensive. :) While I'd like to have a unique() function in Vimscript, I am wondering, whether we could distribute some kind of script package, that defines more used functions. There could be a vim autoload package that provides vim#unique() and we wouldn't need to patch Vims C core, to add more functions later on. >From my experience, I don't expect the last bit of performance from Vimscript anyways so this might be okay. Of course this would only work with functions that could be written in Vimscript and don't require changes to the core. Best, Christian -- -- -- 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.
Re: [patch] add sortuniq() function
On 21 March 2014, lith wrote: > > In other words, I'd expect this for example: > > > > :echo uniq([1, 2, 3, 3, 2, 2, 1]) > > [1, 2, 3, 2, 1] > > I think some of us would be rather surprised if the result weren't > [1,2,3]. Well, the more experienced among us would know that full (unsorted) unique would be nice, but expensive. :) On a side note: how does Vim handle hash keys? It's the exact same problem; if it's done in less than O(N^2), perhaps the same algorithm could be used here. /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.
Re: [patch] add sortuniq() function
On 21 March 2014, Cade Forester wrote: > > How about separating it from sort()? That is, an uniq() > > function that would remove duplicates from an already sorted list > > (results would be undefined if the input list is not sorted). That > > would be consistent with how uniq(1) works on UNIX. > > This patch add uniq() function. uniq(list) will remove copies of > repeated adjacent items Excellent. But now f_sort() and f_uniq() are identical, except at the very end. How about merging them in a single function, and making f_sort() and f_uniq() wrappers to that. /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.
Re: [patch] add sortuniq() function
> In other words, I'd expect this for example: > > :echo uniq([1, 2, 3, 3, 2, 2, 1]) > [1, 2, 3, 2, 1] I think some of us would be rather surprised if the result weren't [1,2,3]. -- -- 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.
Re: [patch] add sortuniq() function
LCD 47 wrote: > On 19 March 2014, Cade Forester wrote: >> > Looks like you made a copy of f_sort() and modified it a bit. That's a >> > >> > lot of duplicate code. Better move the common stuff into a function >> > >> > that's used by both sort() and sortuniq(). >> >> Fixed > > How about separating it from sort()? That is, an uniq() function > that would remove duplicates from an already sorted list (results would > be undefined if the input list is not sorted). That would be consistent > with how uniq(1) works on UNIX. uniq() should also make sense on non sorted list: it should remove adjacent identical items. This is consistent with the UNIX uniq or std::unique() in c++. In other words, I'd expect this for example: :echo uniq([1, 2, 3, 3, 2, 2, 1]) [1, 2, 3, 2, 1] I'm surprised this did not exist already. Dominique -- -- 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.
Re: [patch] add sortuniq() function
> How about separating it from sort()? That is, an uniq() function
>
> that would remove duplicates from an already sorted list (results would
>
> be undefined if the input list is not sorted). That would be consistent
>
> with how uniq(1) works on UNIX.
This patch add uniq() function. uniq(list) will remove copies of repeated
adjacent items
--
--
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.
diff -r 70fac246bfe4 runtime/doc/change.txt
--- a/runtime/doc/change.txtWed Mar 19 18:57:54 2014 +0100
+++ b/runtime/doc/change.txtFri Mar 21 21:36:11 2014 +0700
@@ -1650,7 +1650,7 @@
7. Sorting text*sorting*
Vim has a sorting function and a sorting command. The sorting function can be
-found here: |sort()|.
+found here: |sort()|, |uniq()|.
*:sor* *:sort*
:[range]sor[t][!] [i][u][r][n][x][o] [/{pattern}/]
diff -r 70fac246bfe4 runtime/doc/eval.txt
--- a/runtime/doc/eval.txt Wed Mar 19 18:57:54 2014 +0100
+++ b/runtime/doc/eval.txt Fri Mar 21 21:36:11 2014 +0700
@@ -327,6 +327,7 @@
Changing the order of items in a list: >
:call sort(list)" sort a list alphabetically
:call reverse(list) " reverse the order of items
+ :call uniq(sort(list)) " sort and remove duplicates
For loop ~
@@ -2005,6 +2006,8 @@
type( {name}) Number type of variable {name}
undofile( {name}) String undo file name for {name}
undotree() Listundo file tree
+uniq( {list} [, {func} [, {dict}]])
+ Listremove adjacent duplicates
values( {dict})Listvalues in {dict}
virtcol( {expr}) Number screen column of cursor or mark
visualmode( [expr])String last visual mode used
@@ -6169,6 +6172,14 @@
blocks. Each item may again have an "alt"
item.
+uniq({list} [, {func} [, {dict}]]) *uniq()* *E702*
+ Remove second and succeeding copies of repeated adjacent
+ {list} items in-place. Returns {list}. If you want a list
+ to remain unmodified make a copy first: >
+ :let newlist = uniq(copy(mylist))
+< Compare function uses the string representation of each item.
+ For the use of {func} and {dict} see |sort()|.
+
values({dict}) *values()*
Return a |List| with all the values of {dict}. The |List| is
in arbitrary order.
diff -r 70fac246bfe4 runtime/doc/usr_41.txt
--- a/runtime/doc/usr_41.txtWed Mar 19 18:57:54 2014 +0100
+++ b/runtime/doc/usr_41.txtFri Mar 21 21:36:11 2014 +0700
@@ -623,6 +623,7 @@
map() change each List item
sort() sort a List
reverse() reverse the order of a List
+ uniq() remove copies of repeated adjacent items
split() split a String into a List
join() join List items into a String
range() return a List with a sequence of numbers
diff -r 70fac246bfe4 runtime/doc/version7.txt
--- a/runtime/doc/version7.txt Wed Mar 19 18:57:54 2014 +0100
+++ b/runtime/doc/version7.txt Fri Mar 21 21:36:11 2014 +0700
@@ -942,6 +942,7 @@
|tagfiles()| List with tags file names
|taglist()|get list of matching tags (Yegappan Lakshmanan)
|tr()| translate characters (Ron Aaron)
+|uniq()| remove copies of repeated adjacent list items
|values()| get List of Dictionary values
|winnr()| takes an argument: what window to use
|winrestview()|restore the view of the current window
diff -r 70fac246bfe4 src/eval.c
--- a/src/eval.cWed Mar 19 18:57:54 2014 +0100
+++ b/src/eval.cFri Mar 21 21:36:11 2014 +0700
@@ -744,6 +744,7 @@
static void f_type __ARGS((typval_T *argvars, typval_T *rettv));
static void f_undofile __ARGS((typval_T *argvars, typval_T *rettv));
static void f_undotree __ARGS((typval_T *argvars, typval_T *rettv));
+static void f_uniq __ARGS((typval_T *argvars, typval_T *rettv));
static void f_values __ARGS((typval_T *argvars, typval_T *rettv));
static void f_virtcol __ARGS((typval_T *argvars, typval_T *rettv));
static void f_visualmode __ARGS((typval_T *argvars, typval_T *rett
Re: [patch] add sortuniq() function
On 19 March 2014, Cade Forester wrote: > > Looks like you made a copy of f_sort() and modified it a bit. That's a > > > > lot of duplicate code. Better move the common stuff into a function > > > > that's used by both sort() and sortuniq(). > > Fixed How about separating it from sort()? That is, an uniq() function that would remove duplicates from an already sorted list (results would be undefined if the input list is not sorted). That would be consistent with how uniq(1) works on UNIX. /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.
Re: [patch] add sortuniq() function
> Looks like you made a copy of f_sort() and modified it a bit. That's a
>
> lot of duplicate code. Better move the common stuff into a function
>
> that's used by both sort() and sortuniq().
Fixed
--
--
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.
diff -r 5c956eeefc1b runtime/doc/change.txt
--- a/runtime/doc/change.txtTue Mar 18 23:36:13 2014 -0400
+++ b/runtime/doc/change.txtThu Mar 20 12:04:35 2014 +0700
@@ -1650,7 +1650,7 @@
7. Sorting text*sorting*
Vim has a sorting function and a sorting command. The sorting function can be
-found here: |sort()|.
+found here: |sort()|, |sortuniq()|.
*:sor* *:sort*
:[range]sor[t][!] [i][u][r][n][x][o] [/{pattern}/]
diff -r 5c956eeefc1b runtime/doc/eval.txt
--- a/runtime/doc/eval.txt Tue Mar 18 23:36:13 2014 -0400
+++ b/runtime/doc/eval.txt Thu Mar 20 12:04:35 2014 +0700
@@ -326,6 +326,7 @@
Changing the order of items in a list: >
:call sort(list)" sort a list alphabetically
+ :call sortuniq(list)" sort a list and remove duplicates
:call reverse(list) " reverse the order of items
@@ -1956,6 +1957,8 @@
sinh( {expr}) Float hyperbolic sine of {expr}
sort( {list} [, {func} [, {dict}]])
Listsort {list}, using {func} to compare
+sortuniq( {list} [, {func} [, {dict}]])
+ Listsort {list} and remove duplicates
soundfold( {word}) String sound-fold {word}
spellbadword() String badly spelled word at cursor
spellsuggest( {word} [, {max} [, {capital}]])
@@ -5513,6 +5516,11 @@
return a:i1 - a:i2
endfunc
<
+
+sortuniq({list} [, {func} [, {dict}]]) *sortuniq()* *E702*
+ Sort the items in {list} as like |sort()| does and
+ remove duplicates.
+
*soundfold()*
soundfold({word})
Return the sound-folded equivalent of {word}. Uses the first
diff -r 5c956eeefc1b runtime/doc/usr_41.txt
--- a/runtime/doc/usr_41.txtTue Mar 18 23:36:13 2014 -0400
+++ b/runtime/doc/usr_41.txtThu Mar 20 12:04:35 2014 +0700
@@ -622,6 +622,7 @@
filter()remove selected items from a List
map() change each List item
sort() sort a List
+ sortuniq() sort a List and remove duplicate values
reverse() reverse the order of a List
split() split a String into a List
join() join List items into a String
diff -r 5c956eeefc1b runtime/doc/version7.txt
--- a/runtime/doc/version7.txt Tue Mar 18 23:36:13 2014 -0400
+++ b/runtime/doc/version7.txt Thu Mar 20 12:04:35 2014 +0700
@@ -927,6 +927,7 @@
|setqflist()| modify a quickfix list (Yegappan Lakshmanan)
|settabwinvar()| set variable in window of specified tab page
|sort()| sort a List
+|sortuniq()| sort a List and remove duplicates
|soundfold()| get the sound-a-like equivalent of a word
|spellbadword()| get a badly spelled word
|spellsuggest()| get suggestions for correct spelling
diff -r 5c956eeefc1b src/eval.c
--- a/src/eval.cTue Mar 18 23:36:13 2014 -0400
+++ b/src/eval.cThu Mar 20 12:04:35 2014 +0700
@@ -93,6 +93,14 @@
char_u *ll_newkey; /* New key for Dict in alloc. mem or NULL. */
} lval_T;
+/*
+ * Structure used by sort_internal().
+ */
+typedef struct ulistitem_T
+{
+listitem_T *ll_li; /* list item */
+intis_duplicate; /* TRUE, if item already in list */
+} ulistitem_T;
static char *e_letunexp= N_("E18: Unexpected characters in :let");
static char *e_listidx = N_("E684: list index out of range: %ld");
@@ -695,6 +703,7 @@
static void f_sinh __ARGS((typval_T *argvars, typval_T *rettv));
#endif
static void f_sort __ARGS((typval_T *argvars, typval_T *rettv));
+static void f_sortuniq __ARGS((typval_T *argvars, typval_T *rettv));
static void f_soundfold __ARGS((typval_T *argvars, typval_T *rettv));
static void f_spellbadword __ARGS((typval_T *argvars, typval_T *rettv));
static void f_spellsuggest __ARGS((typval_T *argvars, typval_T *rettv));
@@ -8101,6 +8110,7 @@
{"sinh", 1, 1, f_sinh},
#endif
{"sort", 1, 3, f_sort},
+{"sortuniq
Re: [patch] add sortuniq() function
Cade Foster wrote: > Function sortuniq() for sort and remove duplicates. Looks like you made a copy of f_sort() and modified it a bit. That's a lot of duplicate code. Better move the common stuff into a function that's used by both sort() and sortuniq(). -- A M00se once bit my sister ... "Monty Python and the Holy Grail" PYTHON (MONTY) PICTURES LTD /// 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.
