Back to Questions
2.0k
views7
comments
time based algorithms?
f#

How can 'time-based' algorithms be coded in F#?

Lots of people in the financial industry are apparently looking F#. One way this industry differs from many others is the importance of time in systems. For example, moving averages based on number of elements in the moving window is relatively simple. However, how does one do moving average over a five minute window? Further, how does one do moving average over a five minute window when data is being stream in real-time vs when data is being read from a file (which contains a time-stamp field)?

I suppose one could schedulers or timers...but there should be a way to abstract that away, perhaps with List or Seq like combinators which take time into account?

.

Hi,

There's the issue of data integrity : the real-time data vendor may correct some invalid ticks, which means that if you store data as it arrives (i.e. without updating the whole series), you may find yourself with invalid data.

To answer your question, the solution Mario Fortier (from TA-Lib) recommended (I think) was to call all of the data you need every time. This means you receive more data - which is ok since prices series aren't that long anyway (even 5mn data unless you take data since 1975! In which case you might call 5mn data prior to today only once and update today's data on every call...) - but your data is probably more reliable. It is not 100% real-time, but each approach has its disadvantage !

As for the implementation, why not use a recursive call ? your function would call the data, do the job, and call itself to run again... 

1
2
3
4
5
6
7
8
9
10
11

let rec run everyNSecs =
let rec run everyNSecs =
  async
    { let nextCall = DateTime.Now.AddSeconds(everyNSecs)
      //Load and handle the data
      do! System.Threading.Thread.AsyncSleep(1000 * int <| (nextCall - DateTime.Now).TotalSeconds)
      do! run everyNSecs
    }

Async.Spawn (run 300.0) //runs every 5 minutes

You may want to look at / use [link:ta-lib.org] and [link:fidalsoft.org], both are BSD license so... it may be of some interest for you!

By on 10/11/2008 6:20 AM ()

Hi Julian,

This algorithm needs to continuously give moving average numbers, not every five minutes. In other words, if a new price comes in, the algorithm needs to incrementally update the moving average number and spit it out. If, a second later, another price comes in, the algorithm needs to immediately give an updated moving average number. In each case, the moving average number will be calculated over an X second interval (where X is a parameter to the algorithm). Another way to say it is that I need to use the 'scan' function rather than the 'fold' function (which are typically available in functional languages...I assume in F# as well).

I also want to avoid explicit calls to timers or putting threads to sleep. I want to somehow hide this low level implementation detail.

By on 10/11/2008 11:10 AM ()

The very question seems to be an implementation detail, though.

Keeping a running average is algorithmically trivial, as you noted before. You keep the average and the count, and each time you get a new number, you update:

average = (average*count + newnumber)/(count + 1)

count++

The only question seems to be how to have this function run, and that depends a lot on implementation context.

For example, is there an event handler for when new data arrive? How do you intend to access the current average (do you want to have one thread that computes the running average and another that reports it, implying a shared variable?)?

By on 10/11/2008 12:46 PM ()

Oh, and updating this for an interval isn't that hard. You must then keep a queue of all the values within the interval and, each time around, inspect the bottom of the queue.

For each number on the bottom of the queue that is to be removed, the average becomes

(average * count - number_to_remove)/count--

I trust this is obvious.

By on 10/11/2008 12:49 PM ()

My main concern is how to convert a time based algorithm into a composable combinator. Not only should I be able to calculate a time based moving average, but also make use of time in other list/seq based functions. For example,

every 3seconds map +1 someList

if event1 occursWithin 2minutes event2 do something

25seconds after event3 do something else

(sorry for the made up code convention, I'm very familiar with F# just yet)

This idea of "each time around," means that I have to set a system wide minimum interval granularity (which could be a second or a millisecond). After passage of each millisecond or second, I wake up a thread, get a call-back or handle an event which checks the state of the queue and decides if any elements need to be expired. I supposed there is no way around this periodic polling.

By on 10/11/2008 1:29 PM ()

I am unclear if it applies, but have you read

[link:blogs.msdn.com]

Sounds like possibly an event pipeline is what is desired.

By on 10/12/2008 2:31 PM ()

Actually this blog post is what made me ask the question. I mean to post this link as well but forgot.

Unfortunately the blog post doesn't work for time based windows, only element based windows (or a moving average window based on the number of elements in the window rather than the expiration time).

I'm starting to get the sense that this problem is probably better addressed by people using functional programming to do animation or robotics. The need to manipulate objects in terms of time is fairly intrinsic to those fields.

Functional reactive programming, obviously, does some work in this area. I think the best source of inspiration might be Paul Hudak's work in using Haskell to do music.

By on 10/12/2008 3:39 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper