Re: Optimizing basic operations
- Posted by Spock Jul 31, 2013
- 6133 views
My first goal was to look at the sorting process. I noticed that shell_sort works best in general, but there are still many situations where it does not. For example, if the list to be sorted is already sorted, bubble_sort comes out on top. If the list is completely sorted except for the last entry (the insertion), then, not surprisingly, insertion_sort is faster..
..I now realize that my original question about optimization had a hidden meaning. There is low level optimization such as n += 1 appears faster than n = n + 1 and high level optimization (situation based). The bucket_sort works best in certain restricted situation because it avoids the comparison operator. Is there a performance penalty for using ">", compare() or equal()? Is there a performance penalty if I use a loop to extract elements of a list instead of splicing into it? (Yes, I think so.) While there may be many ways to skin a cat, some are faster than others. Is there a resource guide that addresses some of these issues?
James, I've done my own tests on various sort types and came to the same conclusions as you have. Here are a couple of suggestions:
1) Don't try and optimize the sort now, just get your overall algo functioning as it should and then optimize the sort later.
2) If what you're sorting is not simple, like a flat sequence of ints or strings, you might be better off sorting a sequence of indexes to the data, rather than the data itself. Of course, you'll have to make your own sort routine - just copy an existing one and edit it and change the comparison section inside it.
3) Get some stats of your algorithm (eg, like the histogram of all the data lengths that get sorted). This could be quite insightfull as to deciding which sort would be best.
4) Being able to sort data is quite nice. But would the algorithm (what you're trying to ultimately achieve) still work if NO sorting were done?
5) If what you're sorting IS simple (like a flat sequence of ints) and you really did need Fast_Sort_Now there's always ASM Shell sort, which somebody can help with..
regards, Spock
