Hi guys,
So prune preserves order (with more recent elements overriding
previous elements), but runs in O(n^2) time, while hash-prune does
not preserve order but runs in O(n) time.
Well here is an implementation of prune which runs in O(n log n) time
and preserves order, making hash-prune redundant:
: prune ( seq -- newseq )
dup length [ dup pick nth swap ] map>hash
nip hash>alist sort-values 0 <column> dup like ;
Everything except sort-values is O(n); sort-values is O(n log n).
I did some performance testing, and it seems to be just as fast as
hash-prune, even with large sequences! And of course it is much
faster than prune.
Slava
-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys - and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
_______________________________________________
Factor-talk mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/factor-talk
