From: terje.mathisen@nospicedham.tmsw.no   
      
   Robert Wessel wrote:   
   > On Wed, 19 Jul 2017 13:03:43 +0000, Robert Prins   
   >  wrote:   
   >   
   >> This question isn't specific x86, but given that the program   
   >> incorporating this change is mostly written in (inline) assembler,   
   >> this might well be acceptable.   
   >>   
   >> It was suggested that I add three "top-10/25/40" tables to an   
   >> existing program (yes, "that" program"), for distance, time (these   
   >> two are mildly correlated), and velocity, where equal values are   
   >> tie-broken by a second sort-key, velocity, distance, and distance.   
   >> And finally, to the x86 nitty gritty, if only 32-bit code is   
   >> possible, is there a better way to do the compares than a   
   >>   
   >> cmp a,b jg  ok jne next   
   >>   
   >> cmp c,d jle next   
   >>   
   >> ok: process a(/c) > b(/d)   
   >>   
   >> and second, is there an easy way to make this a generic process?   
   >>   
   >> For what it's worth, I do have working Shellsort and Heapsort   
   >> routines, so I'm not really looking for code. I think they are   
   >> quite efficiently coded, but maybe someone would like to have a   
   >> look at the Shellsort code below, and point out if there's any room   
   >> for improvement - the code is followed by the original Pascal   
   >> code.   
   >>   
   >   
   >   
   > If I understand your problem correctly, you want to extract the top   
   > N elements of a list.  While sorting the whole list is obviously one   
   > way of doing this, this is a selection problem, not a sorting   
   > problem, and can be done rather faster than sorting the whole list.   
      
   Exactly right.   
      
   The largest set (40) is still such a tiny value that it is really   
   trivial to just maintain a running top list of the top 40 entries:   
      
   Each time you get a new entry you compare it with the last and discard   
   immediately if below, otherwise I'd just replace #40 with the current   
   entry and then do a single iteration bubble sort to move it to the   
   correct spot.   
      
   You can of course use binary search to reduce this to max 6 compares,   
   followed by a block copy to shift the bottom part down to make roon in   
   the right spot.   
      
   This key is that 40 is such a small number that on average you will need   
   very few comparisons for the naive code.   
      
   Terje   
      
      
   --   
   -    
   "almost all programming can be viewed as an exercise in caching"   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)