From: alex@nospicedham.rivadpm.com   
      
   On 19-Jul-17 14:03, 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.   
   >   
   > The current input file contains just over 4,000 records, and is unlikely   
   > to grow much over 5,000.   
   >   
   > The two options I seem to have is to read in the whole lot, and do three   
   > sorts before the generation of the three new tables, or, but I have a   
   > strong gut feeling, insert new max values into three tables at read-in   
   > time.   
   >   
   > I only a "top-1" of max values would be required, this would without a   
   > grain of doubt orders of magnitude faster than a final sort, and even   
   > generating a top-5 on-the-fly at read-in time might be faster (three   
   > times (up to) 20,000 compares and re-ordering five items) then a full   
   > blown sort, but obviously(?) generating a top-40 on the fly would be   
   > very expensive, both on compares and data-movement.   
   >   
   > What I have also been thinking about is a series of partial sorts, i.e.   
   > first sort the whole set with a reasonably efficient algorithm (Shell?)   
   > into two parts and repeat that process with the top-half until the final   
   > top-half/quarter/eight is finally sorted completely - an initial thought   
   > that this might also reduce the time to do the second sort (on time)   
   > turned out to be too optimistic one of the top time-values is in the   
   > bottom of the distance half.   
      
   Insertion sort at read time is your best bet.   
      
   Let's say you have N records and want a top M table. The maximum number   
   of compares is N*log2(M) if you keep the table max(M) in sorted order   
   and binary search it, and the maximum number of inserts for a worst case   
   already sorted input will be N, but more likely average N/2. (And   
   obviously, don't move records; move pointers.)   
      
   --   
   Alex   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)