Tuesday, 5 March 2013
Span part 2 - this time the file is XML
Oh ho! It transpires that the Australian Stock Exchange (ASX) publishes their Span data in XML. I haven't found the schema description but, because XML is human-readable, I was able to build a parser. This time I did it using discriminated unions. Much better, although disappointingly more difficult to query after construction. That merits further investigation. (edit: URL at ASX which explains what Span is all about: ASX) and here is a link to the input files used by the parser: Risk parameter files
Go and check out Span2 on Google Code
Aha! I've found the schema definition. It's here
Span (or SPAN?) - they use it for margin calculations but I need to build a parser
London Clearing House provide daily Span files at LCH which list, as far as I can determine, a large number of contracts and the inter-contract spreads. These inter-contract spreads may apply to 2, 3, 4 or more particular contracts and they are applied in a specific order. Therefore, if the portfolio contains contracts AA, BB and CC and there is a listed spread between AA and BB and another between BB and CC then we take the one with the highest priority and calculate margin for the remaining contract by itself. For example, if AA - BB has priority 1 and BB - CC has priority 2 we will be left with CC in our portfolio on which we must calculate the full amount margin. AA and BB are mutually (although not necessarily completely) offsetting.
The Span files given at the LCH URL above are fixed-format. Ewwww! When was the last time you had to build a parser for a fixed-format file? Especially one containing hierarchical data. Moreover, when I started this the specific column format of the file was unclear and required reverse-engineering. Hmm, nice. Luckily, before I had mistaken too much error as progress, I found a specification for the format. Phew!
The Span v4 file format specification
There it is. What a beauty! It seems that the format specification is incomplete. That is, it is sufficient for files received from LCH but for the general case, there is a fuller description. This format is specified at the CME and this is it.
So I set about creating a parser for this little gem. Oh, and I should mention that I did it in F#.
Check it out at Google Code in the Span directory. Yes, I know it's in the wrong place but it'll do. So go and look at it. Note that the fixed-format parser does not currently support the fuller format from CME, just the one supplied by LCH.
Lovely. Now, assuming you've made it this far you'll be thinking that that code is not very nice. Well, you'd be right! I'm not afraid to admit that it's pretty evil stuff. In my defense, however, I would like to say that it was done quite quickly with a view to being rewritten later and that it's been quite a while since I wrote any F#.
Ho hum ...
Wednesday, 30 January 2013
Which is quicker? Iteration or Recursion?
For a simple problem, see Project Euler #1, I thought it would an interesting exercise to code alternative implementations and time them. You see, when I originally solved the problem way back in the mists of time (well, perhaps not that long ago as it was done using F# 1.9.9 as far as I recall) I was using PE as a tool to teach myself F#. Nowadays I'm comfortable with F# so I thought I would return to PE and explore a little more.
So, follows is some F# code which solves problem #1. Spoiler alert! If you haven't already solved it and intend to do so, stop reading now!
let first = fun (a,b) -> a
let second = fun (a,b) -> b
let upperLimit = 1000 // ie we want to act upon the integers which are less than 1000
let maxLoops = 25000 // an arbitrary large integer - the number of times to repeat the core calculation in a single (timed) execution
let howMany = 15 // ie the number of times we want to perform the calculation in order to find the average calculation time
let st = new System.Diagnostics.Stopwatch()
let Impl1a = fun () ->
let whichImpl = "Iteration"
st.Restart()
for loop = 1 to maxLoops do
let mutable sum = 0
for i = 1 to upperLimit-1 do
sum <- if (i%3 = 0 || i%5 = 0) then sum + i else sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl1b = fun () ->
let whichImpl = "Iteration with mutable creation outside loop"
st.Restart()
let mutable sum = 0
for loop = 1 to maxLoops do
sum <- 0
for i = 1 to upperLimit-1 do
sum <- if (i%3 = 0 || i%5 = 0) then sum + i else sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl1c = fun () ->
let whichImpl = "Reverse iteration"
st.Restart()
for loop = 1 to maxLoops do
let mutable sum = 0
for i = upperLimit-1 downto 1 do
sum <- if (i%3 = 0 || i%5 = 0) then sum + i else sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl1d = fun () ->
let whichImpl = "Reverse iteration with mutable creation outside loop"
st.Restart()
let mutable sum = 0
for loop = 1 to maxLoops do
sum <- 0
for i = upperLimit-1 downto 1 do
sum <- if (i%3 = 0 || i%5 = 0) then sum + i else sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl2a = fun () ->
let whichImpl = "Iteration using List higher-order fns"
st.Restart()
for loop = 1 to maxLoops do
let sum = [1..upperLimit-1] |> List.filter (fun i -> i%3=0 || i%5=0) |> List.fold (fun state i -> i+state) 0
ignore sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl2b = fun () ->
let whichImpl = "Iteration using List higher-order fns with pre-compiled integer range"
st.Restart()
let input = [1..upperLimit-1]
for loop = 1 to maxLoops do
let sum = input |> List.filter (fun i -> i%3=0 || i%5=0) |> List.fold (fun state i -> i+state) 0
ignore sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl2c = fun () ->
let whichImpl = "Iteration using Seq higher-order fns"
st.Restart()
for loop = 1 to maxLoops do
let sum = seq {1 .. upperLimit-1} |> Seq.filter (fun i -> i%3=0 || i%5=0) |> Seq.fold (fun state i -> i+state) 0
ignore sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl2d = fun () ->
let whichImpl = "Reverse Iteration using List higher-order fns"
st.Restart()
for loop = 1 to maxLoops do
let sum = [upperLimit-1 .. -1 .. 1] |> List.filter (fun i -> i%3=0 || i%5=0) |> List.fold (fun state i -> i+state) 0
ignore sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl2e = fun () ->
let whichImpl = "Reverse Iteration using List higher-order fns with pre-compiled integer range"
st.Restart()
let input = [upperLimit-1 .. -1 .. 1]
for loop = 1 to maxLoops do
let sum = input |> List.filter (fun i -> i%3=0 || i%5=0) |> List.fold (fun state i -> i+state) 0
ignore sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl2f = fun () ->
let whichImpl = "Reverse Iteration using Seq higher-order fns"
st.Restart()
for loop = 1 to maxLoops do
let sum = seq {upperLimit-1 .. -1 .. 1} |> Seq.filter (fun i -> i%3=0 || i%5=0) |> Seq.fold (fun state i -> i+state) 0
ignore sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl3a = fun () ->
let whichImpl = "Recursion with Accumulator"
let rec Impl3p counter acc =
if counter=upperLimit then
acc
else if counter%3=0 || counter%5=0 then
Impl3p (counter+1) (acc+counter)
else
Impl3p (counter+1) acc
st.Restart()
for loop = 1 to maxLoops do
let sum = Impl3p 1 0
ignore sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl3b = fun () ->
let whichImpl = "Recursion"
let rec Impl3p counter =
if counter=upperLimit then
0
else if counter%3=0 || counter%5=0 then
counter + Impl3p (counter+1)
else
Impl3p (counter+1)
st.Restart()
for loop = 1 to maxLoops do
let sum = Impl3p 1
ignore sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl4a = fun () ->
let whichImpl = "Iteration incrementing a pair of counters"
st.Restart()
for loop = 1 to maxLoops do
let mutable sum = 0
let mutable loopDiv3,loopDiv5 = 0,0
while loopDiv3<upperLimit do // because loopDiv3 increases slower than loopDiv5
loopDiv3 <- loopDiv3 + 3
loopDiv5 <- loopDiv5 + 5
// if we haven't already added it in loopDiv5 ...
sum <- sum + (if loopDiv3 < upperLimit then (if loopDiv3 % 5 <> 0 then loopDiv3 else 0) else 0)
sum <- sum + (if loopDiv5 < upperLimit then loopDiv5 else 0)
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl4b = fun () ->
let whichImpl = "Recursion using a pair of counters"
let rec Impl4p counterDiv3 counterDiv5 =
if counterDiv3>=upperLimit then
0
else
(if counterDiv3 % 5 <> 0 then counterDiv3 else 0) + (if counterDiv5 < upperLimit then counterDiv5 else 0) + Impl4p (counterDiv3+3) (counterDiv5+5)
st.Restart()
for loop = 1 to maxLoops do
let sum = Impl4p 0 0
ignore sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let Impl4c = fun () ->
let whichImpl = "Recursion with Accumulator using a pair of counters"
let rec Impl4p counterDiv3 counterDiv5 acc =
if counterDiv3>=upperLimit then
acc
else
Impl4p (counterDiv3+3) (counterDiv5+5) ((if counterDiv3 % 5 <> 0 then counterDiv3 else 0) + (if counterDiv5 < upperLimit then counterDiv5 else 0) + acc)
st.Restart()
for loop = 1 to maxLoops do
let sum = Impl4p 0 0 0
ignore sum
st.Stop()
st.ElapsedMilliseconds, whichImpl
let run (whichImpl : unit -> int64 * string) =
let res = [ for count = 1 to howMany do yield whichImpl() ]
let name = res |> List.head |> second
let elapsed = res |> List.map first
elapsed |> List.iter (fun elem -> printfn "%s : %i iterations took %i milliseconds" name maxLoops elem)
let avg = float (elapsed |> List.fold (fun state i -> state+i) 0L) / float (List.length elapsed)
name, avg
let implementations = [ Impl1a; Impl1b; Impl1c; Impl1d; Impl2a; Impl2b; Impl2c; Impl2d; Impl2e; Impl2f; Impl3a; Impl3b; Impl4a; Impl4b; Impl4c ]
implementations |> List.map (fun impl -> run impl)
[("Iteration", 252.8);
("Iteration with mutable creation outside loop", 255.0666667);
("Reverse iteration", 225.0);
("Reverse iteration with mutable creation outside loop", 236.1333333);
("Iteration using List higher-order fns", 3509.933333);
("Iteration using List higher-order fns with pre-compiled integer range", 386.6);
("Iteration using Seq higher-order fns", 4848.933333);
("Reverse Iteration using List higher-order fns", 3679.466667);
("Reverse Iteration using List higher-order fns with pre-compiled integer range", 396.7333333);
("Reverse Iteration using Seq higher-order fns", 4883.266667);
("Recursion", 242.4);
("Recursion with Accumulator", 231.9333333);
("Iteration incrementing a pair of counters", 48.6);
("Recursion using a pair of counters", 90.4);
("Recursion with Accumulator using a pair of counters", 53.26666667)]
Monday, 29 October 2012
Monads ... hang on, I'm thinking
So I'm thinking about monads and the shockingly non-functional try...catch...finally in C# and I what I want to do is something like this.
var results = Try(()=>doSomething()).CatchI think that reads reasonably well and is a close approximation to a monad. The question in my mind at the moment is whether it will work as an extension to my already-created Exception Monad (MException if you're following me on Google Code) or whether I will need to create a new monad class, which would be annoying. In the latter case I would probably require an adapter, but that's okay because what do you think Bind() is supposed to be? LoL(()=>catchIt()). Catch (()=>YouveGotABiggerProblemNow()).Finally(()=>TidyUp());
Thursday, 6 September 2012
LINQ group by
This one caught me out a couple of days ago. Recall to mind the good old IEnumerable . It's a good idea to act and code as if they can be traversed once only. As it happened we had some test code which iterated through two streams. Foolishly and without applying enough thought we wrote some linq which joined the two datastreams (ok so far) and then grouped them.
Var a = from b in Bs
From c in Cs
Select new { b , c};
Var aa = from j in a group j by j.c.name;
Oh dear. The group caused the Cs to be looped through one complete traversal for each element in Bs! Not good, because the stream was not restartable and so it went horribly wrong.
The temporary solution is to turn Bs and Cs into lists and take the cross-product on the chin for now.
Friday, 8 June 2012
Countdown - solver in C#
Countdown: presented with six integers they should be combined using the four arithmetic operators +, -, * and / to approach the target as closely as possible.
Example code:
using System;
using System.Linq;
using System.Collections.Generic;
using NUnit.Framework;
namespace Test.Unit.Utils
{
class NonIntegralDivisionResult:Exception {}
[TestFixture]
class Countdown
{
[Test]
public static void CountdownTest1()
{
var operators = new Dictionary<string, Func<int, int, int>>
{
{"+", (a, b) => a + b},
{"-", (a, b) => a - b},
{"*", (a, b) => a*b},
{"/", (a, b) =>
{
var resAsDouble = a/(double) b;
var dbl = (double) (a/b);
if (resAsDouble != dbl) throw new NonIntegralDivisionResult();
return a/b;
}
}
};
var startNos = new[] {1, 5, 6, 7, 9, 10};
var target = 127;
var result = new Dictionary<int,List<string>>();
foreach (var num1 in startNos)
foreach (var op1 in operators)
foreach (var num2 in startNos.Except(new[] { num1 }))
foreach (var op2 in operators)
foreach (var num3 in startNos.Except(new[] { num1, num2 }))
foreach (var op3 in operators)
foreach (var num4 in startNos.Except(new[] { num1, num2, num3 }))
foreach (var op4 in operators)
foreach (var num5 in startNos.Except(new[] { num1, num2, num3, num4 }))
foreach (var op5 in operators)
foreach (var num6 in startNos.Except(new[] { num1, num2, num3, num4, num5 }))
{
try
{
var value = op5.Value(op4.Value(op3.Value(op2.Value(op1.Value(num1, num2), num3), num4), num5), num6);
var name = String.Format("{0}{1}{2}{3}{4}{5}{6}{7}{8}{9}{10}", num1, op1.Key, num2, op2.Key, num3, op3.Key, num4, op4.Key, num5, op5.Key, num6);
var key = Math.Abs(value - target);
if(result.ContainsKey(key)) result[key].Add(name);
else result.Add(key, new List{name});
}
catch(DivideByZeroException) {}
catch(NonIntegralDivisionResult) {}
}
var output = result.OrderBy(kvp => kvp.Key).Take(25);
foreach(var line in output)
foreach(var value in line.Value)
Console.WriteLine("Key: {0} Value: {1}", line.Key, value);
}
}
}
Tuesday, 15 May 2012
Linq makes creating dictionaries easy
Previously, I wrote example code that used one of my library functions to construct a dictionary when given a list or pair of list. Since the place of gainful employment moved to .NET 3.5 I have been able to write some truly linq-y code, and have observed many wonderful things, in particular the extension methods of IEnumerable. Check out
ToDictionary( keyFn, valueFn)
It's exactly what I was writing in my Functional.array.toDict function. Good work, Microsoft!
Subscribe to:
Posts (Atom)