Phillip Trelford's Array

POKE 36879,255

UML Sequence Diagrams

This week in the Software Architecture evening course I’m giving for non-developers the topic was UML Sequence Diagrams. The class task was to create a basic sequence diagram for behaviour of an Auction house, and here are the results from the class, watch out e-bay ;)

Auction Sequence Diagram 1

Auction Sequence Diagram 2 

Auction Sequence Diagram 3

Left-Truncatable Primes

Yesterday a colleague asked me how a function to calculate the nth left-truncatable prime might look in F# for comparison against a C++ implementation, so lets start with the definition from Wikipedia:

In number theory, a left-truncatable prime is a prime number which, in a given base, contains no 0, and if the leading ("left") digit is successively removed, then all resulting numbers are prime. For example 9137, since 9137, 137, 37 and 7 are all prime. Decimal representation is often assumed and always used in this article.

The following is the F# implementation, using recursion, coded up on the train home last night (the function takes about 5ms to calculate the 1000th left-truncatable prime, just 2ms off very close to the optimized C++ time):

let IsPrime n =
    if n = 1 then false
    else    
        let max = n |> float |> sqrt |> int
        let rec Test = function
            | x when x > max -> true
            | x -> if (n % x) = 0 then false else Test (x+1)
        Test 2
 
let NthLeftTruncatedPrime index =
    let rec Find digit factor primes primes' count acc =
        match digit, primes' with
        | 10, _ -> 
            let primes = List.rev acc
            Find 1 (10*factor) primes primes count []
        | _, [] ->
            Find (digit+1) factor primes primes count acc
        | _, prime::tail -> 
            let k = (digit * factor) + prime
            let count, acc =
                if IsPrime k then count+1, k::acc else count, acc 
            if count = index then k
            else Find digit factor primes tail count acc
    let primes = [2;3;5;7]
    if index <= 4 then List.nth primes (index-1)
    else Find 1 10 primes primes 4 []
 

Initially the comparison was intended to be simply on readability, where the F# code was unsurprisingly found to be shorter, and the imperative style (lots of for loops) of the C++ code more familiar to some.

Just out of curiosity I ran a quick performance check to see whether performance was in the same order of magnitude, fully expecting the C++ to faster. In fact initially the C++ was half the speed of the F# code (i.e. the C++ took twice as long). After a little head scratching, I tried a few teaks on the C++, for example giving the STL vector an initial capacity which increased performance by about 20%. Then I spotted that the C++ was using Int64 underneath and the F# Int32. Making the C++ use Int32 brought comparable performance to the F# code give or take a millisecond. At no point did I bother trying to optimize the F# code (except for running the function once before doing the timing to ensure the code had been just-in-time (JIT) compiled).

At the time of first posting this entry it was thought that the C++ was a couple of milliseconds faster. Actually later in the day it was found that there was an error in the calculation of the C++ result and in fact there was no discernable difference between the performance of the C++ and F# code. There are further algorithmic optimizations that could be applied to both implementations but I will leave that as an exercise for the reader.

This is quite interesting, it really does show that you can *NOT* assume that writing code in unmanaged C++ will intrinsically make it faster than code written in managed languages like C# and F#.

Software Architecture for Non-Developers

Its the 3rd of 7 weekly instalments of a Software Architecture evening course I’m giving for 20 or so non-developers. So far each session has been split in two with a half hour of lecture and a half hour workshop. For the workshop the class is split into teams of 3, 4 or 5 and given a task to solve with UML:

  • Week 1: Use Cases for an Auction system
  • Week 2: Class Diagrams for an Auction system
  • Week 3: Class Diagrams for an Exchange
    Each team presented their diagram to the class, and here are the results for this week -developers better beware. ;)

  Exchange Class Diagram 2Exchange Class Diagram 1 Exchange Class Diagram 3 Exchange Class Diagram 4Exchange Class Diagram 5