>>>>> "Dan" == Daniel Ehrenberg
>>>>> <[EMAIL PROTECTED]> writes:
Dan> This new prune is about 2.5 times faster when pruning the
Dan> sequence [ 100 [ 100 % ] times ] { } make , though it gives the
Dan> results in a different order. However, pruning a short sequence
Dan> like { 1 2 1 2 1 2 } appears to be around 1.5 times slower.
You made me wonder what would happen with an hashtable to keep track
of values that have already been considered. I've tried the following
words:
: set-hash-t ( hash elt -- )
t swap rot set-hash ;
: push-new* ( seq hash elt -- seq )
dup pick hash [ 2drop ] [ tuck set-hash-t over push ] if ;
: prune* ( seq -- newseq )
[ V{ } clone H{ } clone rot [ push-new* ] each-with ] keep like ;
With your 10,000 elements list prune* is 10 times faster than prune,
and with { 1 2 1 2 1 2 } it is still slightly better.
The semantic difference between prune and prune* semantics is that
prune keeps the last element in the sequence while prune* preserves
the first one. Incidentally, I prefer the prune* variant.
Sam
PS/ Making set-hash-t inline or reducing stack shuffling around it
should further increase the performances. For example, set-hash-t
could be replaced by something like "dup rot set-hash" (to store the
element itself as both the key and the value, since the value has no
importance), or even by "over set-hash" (storing the hash-table itself
as value) but I haven't looked at the garbage collector and I don't
know whether circular references would confuse it.
--
Samuel Tardieu -- [EMAIL PROTECTED] -- http://www.rfc1149.net/
-------------------------------------------------------------------------
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
Factor-talk@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/factor-talk
