>>>>> "PP" == Philip Potter <philip.g.pot...@gmail.com> writes:
PP> Actually, there is a certain amount of reasoning possible with respect PP> to comparison functions: for example, a Schwartzian Transform will be PP> a win if the key calculation is more expensive than the comparison of PP> keys. that is incorrect. it all depends on the growth of the algorithm. key extraction can be the same work as comparisons but it becomes O(N). note that with a straight call to sort() the comparison must also do key extraction. if the keys are just a list of strings or numbers, then the extraction becomes nothing and there is no win for any transform. pretty much anything else will win given a large enough data set. that is always the case. a slow as hell bubble sort (O(N**2)) is FASTER for 3 elements than any other sort only because the data set is so small. sort speed is always about growth curves which is what O() notation is all about. for instance O( N * log N + N ) is the SAME as O( N * log N ). the highest order term wins since it grows the fastest. and constant factors are removed from the function as well. the win with the ST and GRT is not in the growth curve but in the real world savings of duplicated work (key extraction). it is done only once per key and not for each comparison. note that you must always do some key extraction (even if it is a no-op) so converting that from O( N * log N ) to O( N ) is a real world win especially with larger data sets. but the actual O() value doesn't change! the sort comparison is still O( N * log N ) with any of the transforms since sort is called. uri -- Uri Guttman ------ u...@stemsystems.com -------- http://www.sysarch.com -- ----- Perl Code Review , Architecture, Development, Training, Support ------ --------- Gourmet Hot Cocoa Mix ---- http://bestfriendscocoa.com --------- -- To unsubscribe, e-mail: beginners-unsubscr...@perl.org For additional commands, e-mail: beginners-h...@perl.org http://learn.perl.org/
