Cookbook: How to find the date inside the stream fast

Moderator: admin

Cookbook: How to find the date inside the stream fast

Postby Nikolay.Gekht » Tue Apr 06, 2010 12:32 pm

This is not a secret that the linear search of the particular date inside the input or output takes a long time. For example, if there is 5000 bars are loaded into the chart, the linear search requires up to 5000 comparisons to find (or to not find) the specified date inside the stream.

But the candles are always sorted in the ascending order by the date, so, to improve the performance of the indicators, which requires finding the date inside the stream you can use the binary search algorithm which requires only log2(n) comparisons to find (or to not find) the value. For 5000 bars it will be only 13 comparisons or is 384 times faster. For the regular 300 bar chart it requires 8 comparisons or is 40 times faster.

Please find the source code of the function below.

Code: Select all
-- ------------------------------------------------------------------------------
-- Find the specified date in the specified stream
--
-- The function uses the binary search algorithm, so it requires only O(n) = log2(n) operations
-- to find (or to do not find) the value.
--
-- The function compares the date and time rounded to the whole seconds.
--
-- Parameters:
-- stream       The price stream to find the date in
-- date         Date and time value to be found
-- precise      The search mode
--              In case the value of the parameter is true, the function
--              Searches for the the exact date and returns not found in the
--              date is not found.
--              In case the value of the parameter is false, the function
--              returns the period with the biggest time value which is smaller
--              than the value of the date parameter.
-- Returns:
-- < 0          The value is not found
-- >= 0         The index of the the period in the stream
-- ----------------------------------------------------------------------------------

function findDateFast(stream, date, precise)
    local datesec = nil;
    local periodsec = nil;
    local min, max, mid;

    datesec = math.floor(date * 86400 + 0.5)

    min = 0;
    max = stream:size() - 1;

    while true do
        mid = math.floor((min + max) / 2);
        periodsec = math.floor(stream:date(mid) * 86400 + 0.5);
        if datesec == periodsec then
            return mid;
        elseif datesec > periodsec then
            min = mid + 1;
        else
            max = mid - 1;
        end
        if min > max then
            if precise then
                return -1;
            else
                return min - 1;
            end
        end
    end
end
Nikolay.Gekht
FXCodeBase: Site Admin
 
Posts: 1235
Joined: Wed Dec 16, 2009 6:39 pm
Location: Cary, NC

Return to Indicator Development

Who is online

Users browsing this forum: No registered users and 8 guests