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
