Re: Optimizing basic operations
- Posted by Spock Aug 01, 2013
- 6047 views
5) My data structure basically looks like this: { evaluation, {group 1 of integers}, {group 2 of integers} }. The evaluation starts out as a division / floating point, but I can convert it to an integer as approximate may be good enough. Group 1 and Group 2 always have the same length, so list could be made flat for sorting and re-grouped later. Only the evaluation needs to be sorted. The rest just come along for the ride. ASM shell sort sounds nice. How do I find this?
Which element are you sorting on? If you are sorting on one of the integer groups, how do you determine ordering? That is, whether one group is greater than, less than, or equal to another group?
Have you looked at the functions in std/sort.e? http://openeuphoria.org/docs/std_sort.html#_2964_sorting
Edit: Never mind, I see the answer in my quoted section above.
I'll come up with a code snippet later.
James,
If I read this correctly, you have a list of data structures each with this form :
{ eval, {group 1 of integers}, {group 2 of integers} }
And you want to sort by the "eval" of each structure? If so this could be a good candidate for an indexed sort, ie, sort indexes to the data rather than the data itself. However, how long is the super list of these structures? This is to narrow down which sort algo might be the best.
What I would do for the sort is create 2 additional sequences: {eval1, eval2, eval3,..} and some indexes {1,2,3,..}. Thne feed both these into your custom sort routine which will emit a sorted index list with which you can access the original data. You could then rearrange the whole original data, if you wanted. The extra memory for this operation will be like 1% (or less) of the original data. And the sort will be working on a linear list of integers so will have good performance.
In fact, there might already be some sort of index sort in a std library for Euphoria. If there is, try that first, then later optimize using a custom asm shell sort - there'll be plenty on the internet.
I think JayGade might be able to offer additional suggestion too.
regards, Spock
