|
PureBytes Links
Trading Reference Links
|
I've got a system that does an EXPENSIVE calculation
and right now I'm using an algorithm with O(N * logN)
asymptotic behavior. I hope somebody can offer a
suggestion on how to reduce this to O(N), or better
yet, O(logN).
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.
Notice that N and K are variables ("Inputs" actually);
N and K are *not* constant. It is expected that users
will operate with N =approx= 120 and with K =approx= 50
or thereabouts. But it is mandatory to allow users
to modify N and K. We cannot "hardwire" them to
fixed constant values.
Because the number of trading days to examine, "N",
is not a constant, we can't use the builtin function
KthMaxList. We don't know at compile time what the
length of the "list" is, so we don't know how many
items to type and how many commas to use.
I would think that there might be SOME way to pay
O(N * logN) on the first day, and then O(logN)
on all subsequent days. But the problem is that
I keep sliding the window; it always incorporates
the N most recent Open prices. Every day I drop
the open of (N+1) days ago, and I add the open of
today, and I want to find the K'th biggest again
after this deletion and this insertion.
My present version of code uses Shell's algorithm from
Knuth Volume 3, section 5.2.1. It's an O(N * logN)
algorithm in the average case, uses no scratchpad
memory or linked lists, and works nicely with
Easy Language "Arrays". Still, N*logN is
EXPENSIVE when you're coding in Easy Language and
N =approx= 120. And I'm paying this N*logN every
single day. Owwwww.
I'd LOVE to hear any ideas of how to make this
more efficient, if indeed there are any. If
not, at least I've got code that runs. Albeit
slowly.
Many thanks,
--
Mark Johnson Silicon Valley, California mark@xxxxxxxxxxxx
"... The world will little note, nor long remember, what we
say here..." -Abraham Lincoln, "The Gettysburg Address"
|