Skip to content

Instantly share code, notes, and snippets.

@bboyle1234

bboyle1234/ITimeStampLocalSeries.cs

Last active August 29, 2015 14:21
Show Gist options
  • Save bboyle1234/76355f393d51538a3556 to your computer and use it in GitHub Desktop.
Save bboyle1234/76355f393d51538a3556 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
Instructions
1. Put this code in a visual studio solution
2. Use ninjatrader to create test data.
a. Load up a ES 09-12 chart with 1-tick data, using Default 24/7 session template and 125 days back.
b. Create an indicator that dumps the timestamp and price of each tick into a file.
c. There should be about 25 million data points, many of them with identical timestamps.
3. Add a unit test project to your solution.
4. Create a functional test.
a. Load the data created in step 2.
b. Build an object inheriting from ITimeStampLocalSeries that provides the data you loaded.
c. Step through the data sequentially and build an ordered list of objects with the following properties:
TimeStamp, FirstIndex, LastIndex
d. For each of those objects, test the following methods and make sure their results match the expected results:
FindTimeStampAt, FindTimeStampAtOrBefore, FindTimeStampAtOrAfter
e. Now run through the object list again, but this time use timestamps between that of each object.
5. If the tests fail, either fix the code or fix the tests.
6. Once the functional tests are succeeding, add a stopwatch to the functional test to measure its speed.
7. Have a go at optimizing the code and getting faster speed test results while maintaining successful functional tests
Raw
ITimeStampLocalSeries.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ApexTough.Data {
/// <summary>
/// Used to mark an object as having a series of timestamps in the local timezone accessible by index.
/// Each timestamp is assumed to be greater than or equal to the timestamp before.
/// </summary>
public interface ITimeStampLocalSeries {
/// <summary>
/// Gets the number of data points in the series.
/// </summary>
int Count { get; }
/// <summary>
/// Gets the timestamp (in the local timezone) at the index specified.
/// </summary>
DateTime GetTimeStampLocal(int index);
}
}
Raw
ITimeStampLocalSeriesExtensionMethods.cs
using ApexTough.Data;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ApexTough {
public static class ITimeStampLocalSeriesExtensionMethods {
const int STEP_SIZE = 5;
/// <summary>
/// Searches the time series for the location containing the targetTimeStamp.
/// Fails unless the exact timestamp match is found
/// </summary>
/// <param name="target">The series to be searched</param>
/// <param name="targetTimeStamp">The timestamp we are searching for</param>
/// <param name="firstIndex">If the search is successful, is set to the index of the first item at the targetTimeStamp</param>
/// <param name="lastIndex">If the search is successful, is set to the index of the last item at the targetTimeStamp</param>
/// <returns>True if the search is successful, False otherwise.</returns>
public static bool FindTimeStampAt(this ITimeStampLocalSeries target, DateTime targetTimeStamp, out int firstIndex, out int lastIndex) {
DateTime timeStampFound;
bool isExactMatch;
var result = target.FindTimeStampAtOrBefore(targetTimeStamp, out timeStampFound, out isExactMatch, out firstIndex, out lastIndex);
if (!result) {
return false;
}
if (!isExactMatch) {
Fail(out timeStampFound, out isExactMatch, out firstIndex, out lastIndex);
return false;
}
return true;
}
/// <summary>
/// Searches the time series for the location containing a timestamp equal to or immediately before the targetTimeStamp.
/// </summary>
/// <param name="target">The time series to be searched</param>
/// <param name="targetTimeStamp">The timestamp being searched for</param>
/// <param name="timeStampFound">The timestamp that was found. It could be equal to the targetTimeStamp, or if targetTimeStamp doesn't exist in the time series, it is the timestamp found immediately before targetTimeStamp</param>
/// <param name="isExactMatch">True if the targetTimeStamp was found. False if the timestamp immediately preceeding it was found instead.</param>
/// <param name="firstIndex">The first index of the range of datapoints containing the timestamp that was found</param>
/// <param name="lastIndex">The last index of the range of datapoints containing the timestamp that was found</param>
/// <returns>Returns true if a timestamp is found, false otherwise</returns>
public static bool FindTimeStampAtOrBefore(this ITimeStampLocalSeries target, DateTime targetTimeStamp, out DateTime timeStampFound, out bool isExactMatch, out int firstIndex, out int lastIndex) {
// Check for silliness, and fail the search if necessary.
// If the first timestamp of the series is greater than the targetTimeStamp,
// obviously we can't find a timestamp equal to or less than it.
if (target.Count == 0 || target.GetTimeStampLocal(0) > targetTimeStamp) {
Fail(out timeStampFound, out isExactMatch, out firstIndex, out lastIndex);
return false;
}
// drop into the private, recursive method, setting left and right bounds at the far left and right of the time series
FindTimeStampAtOrBefore(target, targetTimeStamp, 0, target.Count - 1, out timeStampFound, out isExactMatch, out firstIndex, out lastIndex);
return true;
}
/// <summary>
/// Private, recursive implementation of the public 'FindTimeStampAtOrBefore' method.
/// Note this method assumes the following conditions, which have been checked by calling methods:
/// 1. target.Count > 0
/// 2. xMin >= 0
/// 3. xMax < target.Count
/// 4. timeStamp at xMin <= targetTimeStamp
/// 5. timeStamp at xMax >= targetTimeStamp
/// </summary>
static void FindTimeStampAtOrBefore(ITimeStampLocalSeries target, DateTime targetTimeStamp, int xMin, int xMax, out DateTime timeStampFound, out bool isExactMatch, out int firstIndex, out int lastIndex) {
// setup local variables for left and right search bounds
var xL = xMin;
var xR = xMax;
// setup local variables containing the timestamps corresponding to the left and right search bounds
var timeL = target.GetTimeStampLocal(xL);
var timeR = target.GetTimeStampLocal(xR);
// If the left-most timestamp is equal to the targetTimeStamp, our search is complete!
if (timeL == targetTimeStamp) {
timeStampFound = timeL;
isExactMatch = true;
firstIndex = xL;
lastIndex = TraverseToLastOccurrence(target, targetTimeStamp, xMax, xL);
return;
}
// If the right-most timestamp is equal to or less than the targetTimeStamp, our search is complete!
if (timeR <= targetTimeStamp) {
timeStampFound = timeR;
isExactMatch = timeStampFound == targetTimeStamp;
lastIndex = xR;
firstIndex = TraverseToFirstOccurrence(target, timeR, xMin, xR);
return;
}
// If the left and right bounds are quite close together, the fastest way to complete our search
// is a simple dumb iteration over the few items
if (xR - xL <= STEP_SIZE) {
// Let's just start at the right-most bound and work backwards until we find
// a timestamp less than or equal to targetTimeStamp.
do {
xR--;
timeR = target.GetTimeStampLocal(xR);
} while (xR > xL && timeR > targetTimeStamp);
// Here we assume that a result has been found when the while loop exits,
// even though there is no code explicitly checking for the search condition.
// This assumption holds because initial conditions entering the function are that
// timeL <= targetTimeStamp
// A logical proof can be written to show therefore that at this point,
// timeR is definitely <= targetTimeStamp
// So we setup our output variables and leave.
timeStampFound = timeR;
isExactMatch = timeStampFound == targetTimeStamp;
lastIndex = xR;
firstIndex = TraverseToFirstOccurrence(target, timeR, xMin, xR);
return;
}
// The left and right bounds are quite far apart. So let's take an educated guess
// at where our targetTimeStamp might be located.
var xGuess = GuessIndex(target, xMin, xMax, targetTimeStamp);
var timeGuess = target.GetTimeStampLocal(xGuess);
if (timeGuess == targetTimeStamp) {
// Our guess hit gold. Let's setup our output variables and leave.
timeStampFound = timeGuess;
isExactMatch = true;
lastIndex = TraverseToLastOccurrence(target, targetTimeStamp, xMax, xGuess);
firstIndex = TraverseToFirstOccurrence(target, targetTimeStamp, xMin, xGuess);
return;
} else if (timeGuess > targetTimeStamp) {
// First adjust the right bounds to the guess location.
xR = xGuess;
timeR = timeGuess;
// Now adjust the left bounds closer as well.
// We'll do this using a 'brutish' series of stepping leftward from the new right bounds
// until we have moved to a timestamp that is less than or equal to the targetTimeStamp.
var step = STEP_SIZE;
do {
xL = Math.Max(xMin, xR - step);
timeL = target.GetTimeStampLocal(xL);
step *= 2;
} while (xL > xMin && timeL > targetTimeStamp);
// now it's time to recurse this method
} else {
// First adjust the left bounds to the guess location.
xL = xGuess;
timeL = timeGuess;
// Now adjust the right bounds closer as well.
// We'll do this using a 'brutish' series of stepping rightward from the new left bounds
// until we have moved to a timestamp that is greater than or equal to the targetTimeStamp.
var step = STEP_SIZE;
do {
xR = Math.Min(xMax, xL + step);
timeR = target.GetTimeStampLocal(xR);
step *= 2;
} while (xR < xMax && timeR < targetTimeStamp);
// now it's time to recurse this method
}
// let's setup for the recursion.
// First we make sure our xL and xR fall on the first and last occurrences of the timestamp that they currently point to
xL = TraverseToFirstOccurrence(target, timeL, xMin, xL);
xR = TraverseToLastOccurrence(target, timeR, xMax, xR);
// The operation performed above sometimes sets xL and xR right back to the original xMin and xMax values
// that we started with. That would set us up for infinite recursion. Let's check for that.
if (xL == xMin && xR == xMax) {
// recursing from this point will create a stack overflow exception.
// Let's just start at the right-most bound and work backwards until we find
// a timestamp less than or equal to targetTimeStamp.
do {
xR--;
timeR = target.GetTimeStampLocal(xR);
} while (xR > xL && timeR > targetTimeStamp);
// Here we assume that a result has been found when the while loop exits,
// even though there is no code explicitly checking for the search condition.
// This assumption holds because initial conditions entering the function are that
// timeL <= targetTimeStamp
// A logical proof can be written to show therefore that at this point,
// timeR is definitely <= targetTimeStamp
// So we setup our output variables and leave.
timeStampFound = timeR;
isExactMatch = timeStampFound == targetTimeStamp;
lastIndex = xR;
firstIndex = TraverseToFirstOccurrence(target, timeR, xMin, xR);
return;
}
// We have prepared for recursion successfully. The distance between left and right bounds has been drastically reduced.
FindTimeStampAtOrBefore(target, targetTimeStamp, xL, xR, out timeStampFound, out isExactMatch, out firstIndex, out lastIndex);
}
/// <summary>
/// Searches the time series for the location containing a timestamp equal to or immediately after the targetTimeStamp.
/// </summary>
/// <param name="target">The time series to be searched</param>
/// <param name="targetTimeStamp">The timestamp being searched for</param>
/// <param name="timeStampFound">The timestamp that was found. It could be equal to the targetTimeStamp, or if targetTimeStamp doesn't exist in the time series, it is the timestamp found immediately after targetTimeStamp</param>
/// <param name="isExactMatch">True if the targetTimeStamp was found. False if the timestamp immediately after it was found instead.</param>
/// <param name="firstIndex">The first index of the range of datapoints containing the timestamp that was found</param>
/// <param name="lastIndex">The last index of the range of datapoints containing the timestamp that was found</param>
/// <returns>Returns true if a timestamp is found, false otherwise</returns>
public static bool FindTimeStampAtOrAfter(this ITimeStampLocalSeries target, DateTime targetTimeStamp, out DateTime timeStampFound, out bool isExactMatch, out int firstIndex, out int lastIndex) {
// Check for silliness, and fail the search if necessary.
// If the last timestamp of the series is less than the targetTimeStamp,
// obviously we can't find a timestamp equal to or greater than it.
if (target.Count == 0 || target.GetTimeStampLocal(target.Count - 1) < targetTimeStamp) {
Fail(out timeStampFound, out isExactMatch, out firstIndex, out lastIndex);
return false;
}
FindTimeStampAtOrAfter(target, targetTimeStamp, out timeStampFound, out isExactMatch, out firstIndex, out lastIndex);
return true;
}
/// <summary>
/// Private, recursive implementation of the public 'FindTimeStampAtOrAfter' method.
/// Note this method assumes the following conditions, which have been checked by calling methods:
/// 1. target.Count > 0
/// 2. xMin >= 0
/// 3. xMax < target.Count
/// 4. timeStamp at xMin <= targetTimeStamp
/// 5. timeStamp at xMax >= targetTimeStamp
/// </summary>
static void FindTimeStampAtOrAfter(ITimeStampLocalSeries target, DateTime targetTimeStamp, int xMin, int xMax, out DateTime timeStampFound, out bool isExactMatch, out int firstIndex, out int lastIndex) {
// setup local variables for left and right search bounds
var xL = xMin;
var xR = xMax;
// setup local variables containing the timestamps corresponding to the left and right search bounds
var timeL = target.GetTimeStampLocal(xL);
var timeR = target.GetTimeStampLocal(xR);
// If the left-most timestamp is greater than or equal to the targetTimeStamp, our search is complete!
if (timeL >= targetTimeStamp) {
timeStampFound = timeL;
isExactMatch = true;
firstIndex = xL;
lastIndex = TraverseToLastOccurrence(target, targetTimeStamp, xMax, xL);
return;
}
// If the right-most timestamp is equal to the targetTimeStamp, our search is complete!
if (timeR == targetTimeStamp) {
timeStampFound = timeR;
isExactMatch = timeStampFound == targetTimeStamp;
lastIndex = xR;
firstIndex = TraverseToFirstOccurrence(target, timeR, xMin, xR);
return;
}
// If the left and right bounds are quite close together, the fastest way to complete our search
// is a simple dumb iteration over the few items
if (xR - xL <= STEP_SIZE) {
// Let's just start at the left-most bound and work forwards until we find
// a timestamp greater than or equal to targetTimeStamp.
do {
xL++;
timeL = target.GetTimeStampLocal(xL);
} while (xL < xR && timeL < targetTimeStamp);
// Here we assume that a result has been found when the while loop exits,
// even though there is no code explicitly checking for the search condition.
// This assumption holds because initial conditions entering the function are that
// timeR >= targetTimeStamp
// A logical proof can be written to show therefore that at this point,
// timeL is definitely >= targetTimeStamp
// So we setup our output variables and leave.
timeStampFound = timeL;
isExactMatch = timeStampFound == targetTimeStamp;
firstIndex = xL;
lastIndex = TraverseToLastOccurrence(target, timeStampFound, xMax, xL);
return;
}
// The left and right bounds are quite far apart. So let's take an educated guess
// at where our targetTimeStamp might be located.
var xGuess = GuessIndex(target, xMin, xMax, targetTimeStamp);
var timeGuess = target.GetTimeStampLocal(xGuess);
if (timeGuess == targetTimeStamp) {
// Our guess hit gold. Let's setup our output variables and leave.
timeStampFound = timeGuess;
isExactMatch = true;
lastIndex = TraverseToLastOccurrence(target, targetTimeStamp, xMax, xGuess);
firstIndex = TraverseToFirstOccurrence(target, targetTimeStamp, xMin, xGuess);
return;
} else if (timeGuess > targetTimeStamp) {
// First adjust the right bounds to the guess location.
xR = xGuess;
timeR = timeGuess;
// Now adjust the left bounds closer as well.
// We'll do this using a 'brutish' series of stepping leftward from the new right bounds
// until we have moved to a timestamp that is less than or equal to the targetTimeStamp.
var step = STEP_SIZE;
do {
xL = Math.Max(xMin, xR - step);
timeL = target.GetTimeStampLocal(xL);
step *= 2;
} while (xL > xMin && timeL > targetTimeStamp);
// now it's time to recurse this method
} else {
// First adjust the left bounds to the guess location.
xL = xGuess;
timeL = timeGuess;
// Now adjust the right bounds closer as well.
// We'll do this using a 'brutish' series of stepping rightward from the new left bounds
// until we have moved to a timestamp that is greater than or equal to the targetTimeStamp.
var step = STEP_SIZE;
do {
xR = Math.Min(xMax, xL + step);
timeR = target.GetTimeStampLocal(xR);
step *= 2;
} while (xR < xMax && timeR < targetTimeStamp);
// now it's time to recurse this method
}
// let's setup for the recursion.
// First we make sure our xL and xR fall on the first and last occurrences of the timestamp that they currently point to
xL = TraverseToFirstOccurrence(target, timeL, xMin, xL);
xR = TraverseToLastOccurrence(target, timeR, xMax, xR);
// The operation performed above sometimes sets xL and xR right back to the original xMin and xMax values
// that we started with. That would set us up for infinite recursion. Let's check for that.
if (xL == xMin && xR == xMax) {
// recursing from this point will create a stack overflow exception.
// Let's just start at the left-most bound and work forwards until we find
// a timestamp greater than or equal to targetTimeStamp.
do {
xL++;
timeL = target.GetTimeStampLocal(xL);
} while (xL < xR && timeL < targetTimeStamp);
// Here we assume that a result has been found when the while loop exits,
// even though there is no code explicitly checking for the search condition.
// This assumption holds because initial conditions entering the function are that
// timeR >= targetTimeStamp
// A logical proof can be written to show therefore that at this point,
// timeL is definitely >= targetTimeStamp
// So we setup our output variables and leave.
timeStampFound = timeL;
isExactMatch = timeStampFound == targetTimeStamp;
firstIndex = xL;
lastIndex = TraverseToLastOccurrence(target, timeStampFound, xMax, xL);
return;
}
// We have prepared for recursion successfully. The distance between left and right bounds has been drastically reduced.
FindTimeStampAtOrAfter(target, targetTimeStamp, xL, xR, out timeStampFound, out isExactMatch, out firstIndex, out lastIndex);
}
/// <summary>
/// Searches the time series for the begin and end location for the given firstTargetTimeStamp and lastTargetTimeStamp.
/// </summary>
/// <returns>True if indexes were found, false otherwise.</returns>
public static bool FindIndexesBetween(this ITimeStampLocalSeries target, DateTime firstTargetTimeStamp, DateTime lastTargetTimeStamp, out int firstIndex, out int lastIndex) {
// create some local variables to use as outputs for the "FindTimeStamp" methods
DateTime _timeStampFound;
bool _isExactMatch;
int _firstIndex, _lastIndex;
// Find the location of the timestamp at or immediately after "firstTargetTimeStamp"
// Note that, since we are immediately using the public "FindTimeStamp" methods, silliness checking is being
// done in those methods. So there's no need for us to do our own silliness checking here.
if (target.FindTimeStampAtOrAfter(firstTargetTimeStamp, out _timeStampFound, out _isExactMatch, out _firstIndex, out _lastIndex)) {
// save the start of the location to our own output variable
firstIndex = _firstIndex;
// now find the location of the timestamp at or immediately before "lastTargetTimeStamp"
if (target.FindTimeStampAtOrBefore(lastTargetTimeStamp, out _timeStampFound, out _isExactMatch, out _firstIndex, out _lastIndex)) {
// save the end of the location to our own output variable
lastIndex = _lastIndex;
// exit, indicating that the search was successful
return true;
}
}
// The searches were not successful, so set output variables to fail values and return false
firstIndex = -1;
lastIndex = -1;
return false;
}
/// <summary>
/// Calculates a guess at an index between indexLeft and indexRight that might contain a timestamp close to the targetTimeStamp.
/// Result is guaranteed to be between indexLeft and indexRight, and not equal to either of them.
/// Method assumes:
/// The targetTimeStamp falls between the timestamps at indexLeft and indexRight.
/// It's your responsibility to make sure it does or you will get 'unexpected' results.
/// </summary>
static int GuessIndex(ITimeStampLocalSeries target, int xMin, int xMax, DateTime targetTimeStamp) {
// get the left-most timestamp in ticks
var ticksLeft = target.GetTimeStampLocal(xMin).Ticks;
// get the right-most timestamp in ticks
var ticksRight = target.GetTimeStampLocal(xMax).Ticks;
// get a value between 0 and 1 representing the distance from the left index to the target index
// as a proportion of the distance from the left index to the right index
// notice that we take care to cast the numerator to double so that the division operation
// returns a double instead of an int, which would always be zero.
var ratio = (double)(targetTimeStamp.Ticks - ticksLeft) / (ticksRight - ticksLeft);
// use that ratio to make a guess at the index of the targetTimeStamp,
// casting the index back to an int (dropping the decimal portion, always rounding down)
var result = (int)(ratio * (xMax - xMin)) + xMin;
// this method is required to return a guess BETWEEN the given left and right indexes.
// run checks to make sure that the result is indeed between them, and adjust it if not.
if (result == xMin)
result++;
if (result == xMax)
result--;
return result;
}
/// <summary>
/// Traverses backwards along the time series looking for the first occurrence of the targetTimeStamp.
/// Traversal stops at xMin.
/// Method assumes:
/// The timestamp at 'index' is equal to targetTimeStamp.
/// It's the caller's responsibility to make sure it is or you will get 'unexpected' results.
/// </summary>
/// <returns>The index of the first occurrence of the targetTimeStamp</returns>
static int TraverseToFirstOccurrence(ITimeStampLocalSeries target, DateTime targetTimeStamp, int xMin, int index) {
for (var i = index - 1; i >= xMin && target.GetTimeStampLocal(i) == targetTimeStamp; i--) {
index = i;
}
return index;
}
/// <summary>
/// Traverses forwards along the time series looking for the last occurrence of the targetTimeStamp.
/// Traversal stops at xMax.
/// Method assumes:
/// The timestamp at 'index' is equal to targetTimeStamp.
/// It's the caller's responsibility to make sure it is or you will get 'unexpected' results.
/// </summary>
/// <returns>The index of the last occurrence of the targetTimeStamp</returns>
static int TraverseToLastOccurrence(ITimeStampLocalSeries target, DateTime targetTimeStamp, int xMax, int index) {
for (var i = index + 1; i <= xMax && target.GetTimeStampLocal(i) == targetTimeStamp; i++) {
index = i;
}
return index;
}
/// <summary>
/// Boiler plate code for setting up output variables when the search fails
/// </summary>
static void Fail(out DateTime timeStampFound, out bool isExactMatch, out int firstIndex, out int lastIndex) {
timeStampFound = DateTime.MinValue;
isExactMatch = false;
firstIndex = -1;
lastIndex = -1;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment