Re: shaving microseconds (avoiding N * logN behavior)

[Bob Fulks <bfulks@xxxxxxxxxxxx>]

At 8:25 PM -0800 3/28/00, Mark Johnson wrote:

>         Problem: for each day in the dataset, look back at
>         the N most recent trading days and return the
>         K'th largest Open price among those N bars.



You might try using a faster sort algorithm. The fastest I have seen is appended below.

It should be possible to sort once and then just remove the old and insert the new into the sorted array. But to do this you would need to keep an index value with each value (to be able to know which one to remove) and you would still have to move all the values in the array, so I suspect the simple fast sort will end up being faster (and a lot simpler).

Perhaps a combination might be even better. Sort the array. Then on each new bar:

   > Get the old value to be removed = Open[N]
   > Get the new value to be added = Open
   > Search the sorted array for the value to be removed
   > Replace that value with the new value
   > Resort the array

The new sort should be very fast since all of the entries except one will already be in the correct order.

Interesting problem...

Bob Fulks

----------

Attached is EasyLanguage code for a very fast sort routine. This code is an
indicator that test the sort code so you should be able to extract the code
that actually does the sort.

I use it all the time. (I think I got the algorithm from Bob Brickey of
Scientific Approaches but I have forgotten.)

Bob Fulks



Input:    Max(100);
Vars:     K(0), J(0);
Array:    Arr[100](0);

if Date > 970901 then Print("1  ", Date:6:0, CurrentBar:5:0, K:3:0,
   Arr[K]:5:2);

if Date = 970908 then begin
  for K = 1 to Max begin
     Arr[K] = Close[K];
     Print("2  ", Date:6:0, CurrentBar:5:0, K:3:0, Arr[K]:5:2);
  end;
  K = 0;
end;

if LastBarOnChart then begin

  for K = 1 to Max - 1 begin
     for J = K + 1 to Max begin
       if Arr[J] < Arr[K] then begin
          Value1 = Arr[K];
          Arr[K] = Arr[J];
          Arr[J] = Value1;
          Print(K:3:0, J:3:0, Arr[K]:5:2, Arr[J]:5:2);
       end;
     end;
  end;

  for K = 1 to Max begin
     Print("3  ", Date:6:0, CurrentBar:5:0, K:3:0, Arr[K]:5:2);
  end;

end;

Plot1(0,"Plot1");