Hi Dan,
push-new is O(n) and therefore prune is O(n^2). The reason prune is
implemented this way is because the places that call it have very
specific ordering requirements. If you want to extract unique
elements from a sequence without regard to the order, you can use
hash-prune, which is O(n).
Slava
On 21-Jan-07, at 2:52 PM, Daniel Ehrenberg wrote:
> I was recently writing something that used prune (for finding the
> combined usage of a sequence of words) and I noticed that prune's
> implementation is rather inefficient. prune calls push-new, which is
> implemented as : push-new [ delete ] 2keep push ;. delete iterates
> through the entire sequence, shifting the rest of the sequence down
> when it encounters an element that is the same as the given one. But
> push-new could be implemented without delete. If it doesn't matter
> that the element to be pushed is at the end, push-new could be :
> push-new* 2dup member? [ 2drop ] [ push ] if ; (since we know that the
> element only occurs at most once in the sequence being built) and a
> new prune could be implemented exactly the same as the old one, except
> using push-new* instead of push-new . This new prune is about 2.5
> times faster when pruning the sequence [ 100 [ 100 % ] times ] { }
> make , though it gives the results in a different order. However,
> pruning a short sequence like { 1 2 1 2 1 2 } appears to be around 1.5
> times slower. This is probably because the old prune has at worst an
> O(n^3) worst-case asymptotic complexity (the first benchmark is pretty
> much the worst case), while the new one is O(n^2). Or am I calculating
> that wrong? They might both be O(n^2); I haven't formally studied big
> O notation yet, so I'm not sure.
>
> This is just a minor little thing, anyway. Are there any problems with
> this new version of push-new? I'm not sure if it would work with all
> cases where it's used, if any of those depends on the new element
> being on the end.
>
> Dan
>
> ----------------------------------------------------------------------
> ---
> 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
-------------------------------------------------------------------------
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
