Type based API's and Duck Typing Shocker!!

The Voidspace tech blog has an article in which the author, Michael Ford, blames duck-typing for a problem in trying to find the type of an argument.

After a very good explanation of how duck typing in Python  comes about Michael starts his section on the problem by stating the principal of duck typing as:

"The principle of duck typing says that you shouldn't care what type of object you have - just whether or not you can do the required action with your object."

All well and good but then later on Michael states:

"If we want our code to treat different types of object differently then the approach in example two fails. This isn't contrived - this is exactly the situation we found ourselves in with ConfigObj."

So, type is important in his case. Fine. But why lay the blame at duck typings door ?

His example interface relies on knowing what constitutes a "listy" object, or a "stringy" object, etc, in Python 2.x, which he notes is a pain, but I think the cause of the problem w.r.t. duck typing is choosing an API that relies on an ill-defined idea of what constitutes close enough to a dict/list/string or whatever, then not having the language provide an easy solution.

Abstract base classes are an attempt to help out in such cases that is new in Python 2.6 and 3.0, but if you want to link functionality with type then you can't expect to get duck typing too.

Where Duck Typing Does Not fit.

If a function has an expensive or non-reversible operation that depends on an  attribute of an argument, then it may be wise to check all arguments for compatibility up-front; but even then, whats wrong with reading the code?  Defensive programming can creep up on you...

Killer Script

Following on from my Batch process runner script, I got thinking that a nice capability would be to have a maximum runtime limit for the jobs.

My first thought was to create an at command set to execute the reuired time after the start of each job, one for each job, that would kill the job.
Nah.
Discussions with a friend lead to consideration of using ulimit in the script to limit the run time, but unfortunately on the Unix box I was testing on, ulimit could only limit the maximum CPU time, not run time. If the job was stuck in a non-busy wait then it would not be auto-killed.

I decided to try creating a script to run a time eating processing task that created a background kill task so the script would be self killing.

The script

Line 1:    The KILLAFTER environment variable will kill the script after 3 seconds
Line 5:    Store the process ID for the 'bash -c'  script for killing later
Line 8:    This is the slleping background sub-process that wakes after KILLAFTER seconds and kills the script.
Line 9:    But if the normal script commands finish, store the sub-process PID so it can be cleanly killed itself.
Line 12:  Some dummy command that counts up every second.
Line 13:   And save its exit status so it can be restored after removing the background kill process.
Line 16:   Terminate the background kill process so we are not left waiting.
Line 18:   Exit with the saved exit status.
Line 19:   Prints the exit status of the whole 'bash -c' script

Lines 20-24 show the output of the first run. Notice how although the for loop in line 12 is set to count to 5, the count gets killed after printing 3, i.e. the three seconds of $KILLAFTER.

Lines 27 onwards show a second run where KILLAFTER is set to more time than is used by the for loop. Notice how the script prints the full count up to 5, and has a return status of zero.

 1 bash-paddy: env KILLAFTER=3 bash -c '
 2 # New bash script shell environment
 3 
 4 # Its PID
 5 export thisshellpid=$$
 6 
 7 # Sleeping killer will blast this script after given time
 8 (sleep $KILLAFTER ; kill -9 $thisshellpid)&
 9 killerpid=$!
10 
11 # Any time consuming command
12 for y in 1 2 3 4 5; do sleep 1; echo $y; done
13 trueexitstatus=$?
14 
15 # If time consuming command worked OK then...
16 kill -9 $killerpid
17 
18 exit $trueexitstatus
19 ' ; echo Returned status: $?
20 1
21 2
22 3
23 Killed
24 Returned status: 137
25 bash-paddy:
26 bash-paddy:
27 bash-paddy: env KILLAFTER=10 bash -c '
28 # New bash script shell environment
29 
30 # Its PID
31 export thisshellpid=$$
32 
33 # Sleeping killer will blast this script after given time
34 (sleep $KILLAFTER ; kill -9 $thisshellpid)&
35 killerpid=$!
36 
37 # Any time consuming command
38 for y in 1 2 3 4 5; do sleep 1; echo $y; done
39 trueexitstatus=$?
40 
41 # If time consuming command worked OK then...
42 kill -9 $killerpid
43 
44 exit $trueexitstatus
45 ' ; echo Returned status: $?
46 1
47 2
48 3
49 4
50 5
51 Returned status: 0
52 bash-paddy:
53 

XKCD Simpler Knapsack Solution

 After reading the feedback on my earlier solution to the XKCD knapsack problem, I decided to re-write it without itertools.product and with integer maths.

I came up with a solution that used explicit while loops that worked, and used much less traversals through nested loops, but I then boiled that down to a recursive solution which retains the ability to easily modify the number of dishes , whilst restricting the number of times through the loops to the bare minimum.

In the previous solution I worked out the maximum number of each dish that cost less than or equal to the amount and looped from zero to that many times. In the solution below the while loops cut off looping on any particular dish when adding another would put the cost over the maximum.

And now the code:

items = ( ('MIXED FRUIT',   2.15),
          ('FRENCH FRIES',  2.75),
          ('SIDE SALAD',    3.35),
          ('HOT WINGS',     3.55),
          ('MOZZ STICKS',   4.20),
          ('SAMPLER PLATE', 5.80),
          ('BARBEQUE',      6.55) )

exactcost = 15.05

dishes, prices = zip(*items)
# All calcs in integer cents.
prices = [int(price*100) for price in prices]
ecost = int(exactcost*100)

# counts of each dish
dishcounts = [0]*len(prices)
possibleorders = []
cost = 0
maxnesting = len(dishcounts)

def enumeratedish(nest, cost, possibleorders):
    global dishcounts, prices, ecost, maxnesting
    while cost <= ecost:
        if nest+1 < maxnesting:
            enumeratedish(nest+1, cost, possibleorders)
        elif cost == ecost:
            possibleorders.append(dishcounts[:])
            break
        dishcounts[nest] += 1
        cost += prices[nest]
        #print (dishcounts)
    cost -= prices[nest] * dishcounts[nest]
    dishcounts[nest] = 0

enumeratedish(0, 0, possibleorders)
print('\nALL POSSIBLE CHOICES OF MENU ITEMS THAT COST %.2f, ONE PER LINE' % exactcost)
for order in possibleorders:
    order = zip(dishes, order)
    print( '  ',
           ', '.join('%s: %i' % dishcount for dishcount in order if dishcount[1]))

feel free to compare the two solutions. 

XKCD Knapsack Solution

A brute force solution to the following comic from XKCD:




Assuming the one sandwich represents the end of the menu, I used an exhaustive search algorithm. Things to note are the use of zip(*table) to transpose the items and itertools.product instead of nested for loops.

'''
from: http://xkcd.com/287/
'''

from itertools import product

items = ( ('MIXED FRUIT',   2.15),
          ('FRENCH FRIES',  2.75),
          ('SIDE SALAD',    3.35),
          ('HOT WINGS',     3.55),
          ('MOZZ STICKS',   4.20),
          ('SAMPLER PLATE', 5.80),
          ('BARBEQUE',      6.55) )

exactcost = 15.05

dishes, prices = zip(*items)
rangeofdishes = [tuple(range(1+int( (exactcost+0.005)/price ))) for price in prices]

possibleorders = [tuple(zip(dishes, numbers))
                  for numbers in product(*rangeofdishes)
                  if int(exactcost*100)
                       == int(100* sum(num*price
                                       for num,price in zip(numbers, prices)))
                  ]
print('\nALL POSSIBLE CHOICES OF MENU ITEMS THAT COST %.2f, ONE PER LINE' % exactcost)
for order in possibleorders:
    print( '  ',
           ', '.join('%s: %i' % dishcount for dishcount in order if dishcount[1]))

The answers I get are:

ALL POSSIBLE CHOICES OF MENU ITEMS THAT COST 15.05, ONE PER LINE
   MIXED FRUIT: 1, HOT WINGS: 2, SAMPLER PLATE: 1
   MIXED FRUIT: 2, MOZZ STICKS: 1, BARBEQUE: 1
   MIXED FRUIT: 7

(I'd go with the hot wings).

Zed and community

Who is Zed?
Zed it seems knows about his blogging style: asking questions as statements;and ranting.but it seems that he has written good code for the Rails community in the past and has earned some peoples respect. Now he is a new member of the Python community I would hope that current members realize his style and try not to emulate it.

Zed may be here for a long stay, or gone tomorrow, but I wouldn't want the lasting effect to be a rise in the abrasiveness of the Python community, or an unthinking abandonment of community  practices. Even if Zed does produce Pythons Holy Grail, we have to remember that that is software. Community  matters,  and we have to work with the Zeds, the Alex's, the Xah's, the Tim's without being seen to sink to the lowest common denominator.

Pipe Fitting with Python Generators

I was investigating the Hofstadter-Conway $10,000 sequence which, for mathematics, has a very interesting story.  To 'follow the money', you have to generate the sequence of values and calculate maxima and minima of the sequence values so I decided to create a generator of the sequence values and pass it through filters that would emit local maxima/minima. I ended up with something like:

high_generator = maxima(sequence_generator())
highs = [high_generator.next() for i in range(1000)]

Now I just hated the nested call of generators. If it were a Unix shell, I would have hoped to have written:

sequence_generator | maxima |head 1000 > highs

Notice how the data flows from source at the left to sink at the right. I like that.

I spent some time trying to use classes and redefine bitwise or for class instances, but it was looking messy and my heart wasn't really in a class based solution.

I left it for a week. And in that week I remembered seeing a function called pipe being used to pipe things so decided to write my own pipe function for combining generators in a more natural way.

Pipe

What I wanted was a function called pipe, that when called with several generators, returned a nested call of all its arguments, with the leftmost argument being in the center of the nest. For example, a call of:

pipe(a,b,c,d)

Would return the equivalent of:

d(c(b(a)))

The eventual definition turned out to be quite straight-forward:

def pipe(*cmds):
    ''' pipe(a,b,c,d, ...) -> yield from ...d(c(b(a())))
    '''
    gen = cmds[0]
    for cmd in cmds[1:]:
        gen = cmd(gen)
    for x in gen:
        yield x

Pipe in use

Lets create some simple generators; count is just itertools.count; sqr yields the square of items on its input iterator

from itertools import count

def sqr(x):
    for val in x:
        yield val*val

I can now generate the squares of integers:

>>> p = pipe(count(), sqr)
>>> [p.next() for i in range(5)]
[0, 1, 4, 9, 16]

But I need a more complex definition for head as it needs to have a parameter of the maximum number of items to pass through.

def head(n):
    ''' return a generator that passes through at most n items
    '''
    def head(x):
        i = n
        for val in x:
            if i>0:
                i -= 1
                yield val
            else:
                raise StopIteration
    return head

And now with head I can more naturally express nested generator functions as I can stop an infinite generator stream easily for example:

>>> list(pipe(count(), sqr, head(4)))
[0, 1, 4, 9]
>>> for i in pipe(count(), sqr, head(10)):
    print i,

0 1 4 9 16 25 36 49 64 81

Generalized function generator and filter

I thought it might be handy to have a function that skipped an input if the prefilter(input) was false; applied a given function, fn(input) to the input stream and passed on fn(input) to the output if postfilter(fn(input)) was true. Think of a stream of data. You can filter it, apply a function to it, or filter after applying the function - all via this pipe filter. I called it fnf for function filter:

def fnf(fn, prefilter=None, postfilter=None):
    ''' functionfilter:
            for s in x:
                yield fn(s) subject to prefilter(s), postfilter(fn(s)) returning True if present,
                or skip this s
    '''
    def _fnf(x):
        for s in x:
            if prefilter is None or prefilter(s):
                fns = fn(s)
                if postfilter is None or postfilter(fns):
                    yield fns
    _fnf.__doc__ = '_fnf = fnf(%s, %s, %s)' %(fn, prefilter, postfilter)
    return _fnf

I'll show fnf in action.

>>> # turns the input stream of numbers, x into a stream of tuples x,x/2.0
>>> def n_nby2(x): return x, x/2.0

>>> list(pipe( count(), sqr, head(5), fnf(n_nby2) ))
[(0, 0.0), (1, 0.5), (4, 2.0), (9, 4.5), (16, 8.0)]
>>> # Lets create a prefilter
>>> def even(x): return x%2 == 0

>>> list(pipe( count(), sqr, head(5), fnf(n_nby2,even) ))
[(0, 0.0), (4, 2.0), (16, 8.0)]
>>> # And now a postfilter which must work on the result of applying fn
>>> def frac(x): return int(x[1]) != x[1]

>>> list(pipe( count(), sqr, head(5), fnf(n_nby2,None,frac) ))
[(1, 0.5), (9, 4.5)]
>>> # Note the presence of None in the above call as we don't use a prefilter

Thats it for now with the pipe fitting. I do have a tee function for printing intermediate results,  but it's late early and I'm tired....

- Paddy.

Extended unpacking in Python 3.0

After reading about pattern matching on Rosetta Code, I wondered, (and still am wondering), if it has anything to do with list unpacking in Python, which lead me to do some simple explorations of the extended iterable unpacking that is new in Python 3.0.

Introducing a star

The feature builds on the pre-existing capability of being able to unpack a list or tuple into multiple names in Python 2.x, so in Python 2.x you could do:

>>> import platform
>>> platform.python_version()
'2.6.1'
>>> lst = [1,2,3]
>>> a,b,c = lst
>>> print a,b,c
1 2 3
>>> tpl = (1,2,3)
>>> a,b,c = tpl
>>> print a,b,c
1 2 3
>>> iter = (x for x in range(4))
>>> iter
<generator object <genexpr> at 0x01300468>
>>> a,b,c,d = iter
>>> print a,b,c,d
0 1 2 3
>>> # You could also do the (fancy), but non-* stuff too
>>> a,b,(c,d) = (1,2,(3,4))
>>> print a,b,c,d
1 2 3 4
>>> # But not
>>> a,*b = (1,2,3,4)
SyntaxError: invalid syntax
>>> 

In Python 3.0 you get all of the above plus the ability to 'soak up' the rest of the values using * (which I pronounce as 'star' in this context).
It is similar to how you can use *args in a function definition to assign extra positional arguments to a name. In an assignment however it means 'take whatever's left of the what is being assigned and assign it to me as a list'.

Here are some examples:

>>> import platform
>>> platform.python_version()
'3.0.1'
>>> a,*b = [1,2,3,4]
>>> print(a,b, sep='    ')
1    [2, 3, 4]
>>> a = [1,2,3,4]
>>> # Note the comma after the *b to make it a tuple
>>> *b, = [1,2,3,4]
>>> a == b
True
>>> # Only one * per iterable (or sub-iterable) being assigned
>>> *a,*b = [1,2,3,4]
SyntaxError: two starred expressions in assignment (<pyshell#87>, line 1)
>>>
>>> # but note:
>>> a,*b,(c,*d) = [1,2,3,[4,5,6]]
>>> print(a,b,c,d, sep='    ')
1    [2, 3]    4    [5, 6]
>>> # Notice that * always creates a list
>>> *a, = (1,2,3)
>>> a
[1, 2, 3]
>>> a,b,(*c,) = (x if x<2 else range(5) for x in range(3))
>>> print(a,b,c, sep='    ')
0    1    [0, 1, 2, 3, 4]
>>>
>>> # Although you can have only one * per (sub)iterable, its position is flexible
>>> a,*b,c = [1,2,3,4]
>>> b
[2, 3]
>>> *b,a,c = [1,2,3,4]
>>> b
[1, 2]
>>> a,c,*b = [1,2,3,4]
>>>
>>> # And look!
>>> a,c,*b,d,e = [1,2,3,4]
>>> b
[]
>>> a,b,c,d,e
(1, [], 2, 3, 4)
>>> # So * can accumulate no values in some cases

I'm looking forward to using this feature in 3.1.

Critique of pseudocode explanations of the Closest Pair Algorithm

I watched this task on Rosetta Code from its inception on the 6^th of May, but had problems understanding the pseudo-code given, and some of the stuff I googled too. after a couple of days though I was more familiar with attempts at O(nlog(n)) divide-n-conquer algorithms having seen a few and happened to find this explanation (.ppt file) where it seemed to click for me.

After problems with the other references I thought I might go through and identify what I found problematic with them.

The Rosetta Code Pseudo-code:

closestPair of P(1), P(2), ... P(N)
if N ≤ 3 then
  return closest points of P using brute-force algorithm
else
  xP ← P ordered by the x coordinate, in ascending order
  PL ← points of xP from 1 to ⌈N/2⌉
  PR ← points of xP from ⌈N/2⌉+1 to N
  (dL, pairL) ← closestPair of PL

  (dR, pairR) ← closestPair of PR
  (dmin, pairmin) ← (dR, pairR)
  if dL < dR then

    (dmin, pairmin) ← (dL, pairL)
  endif
  xM ← xP(⌈N/2⌉)x

  S ← { p ∈ xP : |xM - px| < dmin }
  yP ← S ordered by the y coordinate, in ascending order
  nP ← number of points in yP
  (closest, closestPair) ← (dmin, pairmin)
  for i from 1 to nP - 1
    k ← i + 1
    while k ≤ nP and yP(k)y - yP(k)y < dmin

      if |yP(k) - yP(i)| < closest then
        (closest, closestPair) ← (|yP(k) - yP(i)|, {yP(k), yP(i)})
      endif
      k ← k + 1
    endwhile
  return closest, closestPair

endif

The author had noted that the above could have problems so I was warned, but still started by trying to follow the above. I was blindly following the pseudo-code until I got the the statement: x_M ← xP(⌈N/2⌉)_x which I couldn't understand.

This prompted my wider search for a better explanation. After finding it (linked in the first paragraph), I modified my Python program to follow the new explanation.

The RC references

There were several references quoted.

• The Wikipedia article
  Did not give pseudo-code

• Closest Pair (McGill)
  Section 3.4 on improving their previous O(nlog²n) into an O(nlogn) algorithm I found to be very vague. Just how do you “returning the points in each set in sorted order by y-coordinate “ without doing an nlogn sort leading again to an O(nlog²n) solution?

• Closest Pair (UCBS)
  This seems to concur with my preferred reference but is given at a higher level than pseudo-code, and so would be harder to implement from the description given.

• Closest pair (WUStL) by Dr. Jeremy Buhler
  Their seems to be a problem with having N, the number of points as an argument of the function. What if N is odd? The pseudo-code seems to rely on other material probably presented in a class and is at a higher level than my preferred solution as it seems to be set as an exercise for students.

My Python Solution

The only tests done is to generate random points and compare the brute force algorithms solution with that of the divide and conquer.

'''

  Compute nearest pair of points using two algorithms
  
  First algorithm is 'brute force' comparison of every possible pair.
  Second, 'divide and conquer', is based on:
    www.cs.iupui.edu/~xkzou/teaching/CS580/Divide-and-conquer-closestPair.ppt 
'''

from random import randint

infinity = float('inf')


# Note the use of complex numbers to represent 2D points making distance == abs(P1-P2)

def bruteForceClosestPair(point):
    numPoints = len(point)
    if numPoints < 2:
        return infinity, (None, None)
    return min( ((abs(point[i] - point[j]), (point[i], point[j]))
                 for i in range(numPoints-1)
                 for j in range(i+1,numPoints)),
                key=lambda x: x[0])


def closestPair(point):
    xP = sorted(point, key= lambda p: p.real)
    yP = sorted(point, key= lambda p: p.imag)
    return _closestPair(xP, yP)

def _closestPair(xP, yP):
    numPoints = len(xP)
    if numPoints <= 3:
        return bruteForceClosestPair(xP)
    Pl = xP[:numPoints/2]
    Pr = xP[numPoints/2:]
    Yl, Yr = [], []
    xDivider = Pl[-1].real
    for p in yP:
        if p.real <= xDivider:
            Yl.append(p)
        else:
            Yr.append(p)
    dl, pairl = _closestPair(Pl, Yl)
    dr, pairr = _closestPair(Pr, Yr)
    dm, pairm = (dl, pairl) if dl < dr else (dr, pairr)
    # Points within dm of xDivider sorted by Y coord

    closeY = [p for p in yP  if abs(p.real - xDivider) < dm]
    numCloseY = len(closeY)
    if numCloseY > 1:
        # There is a proof that you only need compare a max of 7 other points

        closestY = min( ((abs(closeY[i] - closeY[j]), (closeY[i], closeY[j]))
                         for i in range(numCloseY-1)
                         for j in range(i+1,min(i+8, numCloseY))),
                        key=lambda x: x[0])
        return (dm, pairm) if dm <= closestY[0] else closestY
    else:
        return dm, pairm


def times():
    ''' Time the different functions
    '''
    import timeit

    functions = [bruteForceClosestPair, closestPair]
    for f in functions:
        print 'Time for', f.__name__, timeit.Timer(
            '%s(pointList)' % f.__name__,
            'from closestpair import %s, pointList' % f.__name__).timeit(number=1)



pointList = [randint(0,1000)+1j*randint(0,1000) for i in range(2000)]


if __name__ == '__main__':
    pointList = [(5+9j), (9+3j), (2+0j), (8+4j), (7+4j), (9+10j), (1+9j), (8+2j), 10j, (9+6j)]
    print pointList
    print '  bruteForceClosestPair:', bruteForceClosestPair(pointList)
    print '            closestPair:', closestPair(pointList)
    for i in range(10):
        pointList = [randint(0,10)+1j*randint(0,10) for i in range(10)]
        print '\n', pointList
        print ' bruteForceClosestPair:', bruteForceClosestPair(pointList)
        print '           closestPair:', closestPair(pointList)
    print '\n'
    times()
    times()
    times()

Sample output:

[(5+9j), (9+3j), (2+0j), (8+4j), (7+4j), (9+10j), (1+9j), (8+2j), 10j, (9+6j)]
  bruteForceClosestPair: (1.0, ((8+4j), (7+4j)))
            closestPair: (1.0, ((8+4j), (7+4j)))

[(6+8j), (4+1j), 7j, (4+10j), (10+6j), (1+9j), (10+10j), (5+0j), (3+1j), (6+4j)]
 bruteForceClosestPair: (1.0, ((4+1j), (3+1j)))
           closestPair: (1.0, ((3+1j), (4+1j)))

[(5+5j), (10+9j), 3j, (6+1j), (9+5j), 1j, (8+0j), 8j, (3+2j), (10+4j)]
 bruteForceClosestPair: (1.4142135623730951, ((9+5j), (10+4j)))
           closestPair: (1.4142135623730951, ((9+5j), (10+4j)))

[(9+2j), (1+2j), 5j, (10+0j), (6+6j), (6+4j), (5+1j), (2+5j), (8+6j), (3+2j)]
 bruteForceClosestPair: (2.0, ((1+2j), (3+2j)))
           closestPair: (2.0, ((6+6j), (6+4j)))

[(2+3j), (9+0j), (9+7j), 8j, (4+5j), (6+7j), (6+2j), (3+3j), (3+10j), (7+5j)]
 bruteForceClosestPair: (1.0, ((2+3j), (3+3j)))
           closestPair: (1.0, ((2+3j), (3+3j)))

[(7+2j), (2+10j), (3+7j), (8+6j), (2+1j), 3j, (8+5j), (6+9j), (1+0j), 0j]
 bruteForceClosestPair: (1.0, ((8+6j), (8+5j)))
           closestPair: (1.0, ((8+6j), (8+5j)))

[(10+7j), (6+3j), (2+7j), (3+6j), (9+3j), (8+5j), (5+7j), (3+10j), 5j, (3+7j)]
 bruteForceClosestPair: (1.0, ((2+7j), (3+7j)))
           closestPair: (1.0, ((3+6j), (3+7j)))

[(4+6j), (5+4j), 2j, (7+0j), 4j, (6+5j), (7+5j), (8+9j), (10+5j), (8+2j)]
 bruteForceClosestPair: (1.0, ((6+5j), (7+5j)))
           closestPair: (1.0, ((6+5j), (7+5j)))

[(4+0j), (7+9j), 7j, 8j, (7+1j), (2+5j), (7+3j), (1+3j), (3+9j), (10+7j)]
 bruteForceClosestPair: (1.0, (7j, 8j))
           closestPair: (1.0, (7j, 8j))

[(9+1j), (5+0j), (8+3j), (6+9j), (3+7j), (4+6j), (7+6j), (8+6j), (10+8j), (2+5j)]
 bruteForceClosestPair: (1.0, ((7+6j), (8+6j)))
           closestPair: (1.0, ((7+6j), (8+6j)))

[(2+2j), (10+8j), (3+0j), (8+0j), (1+1j), (6+5j), 10j, (6+8j), (10+4j), (4+10j)]
 bruteForceClosestPair: (1.4142135623730951, ((2+2j), (1+1j)))
           closestPair: (1.4142135623730951, ((1+1j), (2+2j)))


Time for bruteForceClosestPair 4.59288093878
Time for closestPair 0.120782948671
Time for bruteForceClosestPair 5.00096353028
Time for closestPair 0.120047939054
Time for bruteForceClosestPair 4.86709875138
Time for closestPair 0.123363723602

Note how much slower the brute force algorithm is for only 2000 points.

(Oh, I guess I should add that the above is all my own work – students might want to say the same).

On "RailsConf: What killed Smalltalk could kill Ruby, too"

Browsing Reddit introduced me to RailsConf: What killed Smalltalk could kill Ruby, too The keynote speech by Robert Martin. I found it to be quite interesting as I had been monitoring odd posts on the Rails community and its general attitude.

Some of the points made by Robert on why Smalltalk contracted in popularity included:

1. It was too easy to make a mess.
   And the mess was found late in the project timeline, leading to failed projects.

2. Smalltakers didn't want to deal with the boring 'corporate' tasks.
   Leading to the rise of programmers using other languages to earn a corporate living.

3. When Smalltalk was 'riding high', a tendency to look down on other languages.
   This would alienate the general population of programmers.

Robert put in a big, recurring, plug for both TDD and refactoring IDEs as ways to keep Ruby alive.

One comment he made was that he thought that in the dynamic vs static typing, language wars: Dynamic won and cited as evidence that most mainstream 'static' languages such as Java, C++ and C# have ways to do dynamic type checking – although badly. I wouldn't go that far, as I suspect that little of the mindset of programming in a dynamic language such as Python would be adopted by a C# or Java programmer. I suspect that they will use the dynamism available to them as a last resort as part of a design pattern to solve a particular sub-problem.

Tech Issues For The Euro Elections

Elections for members of the European Parliament are coming up soon. At the moment, it seems certain companies are lobbying to have software patents  extended into Europe which is something I don't agree with, as on algorithms - how can you distinguish between the maths and the code? On something like look-and-feel of a GUI - how can you distinguish between the idea and its implementation? If you see that person A used a pinching motion of the fingers to zoom-out centered on the pinch then I don't think that should stop person B from coding his own implementation using different code. I do think that the screen technology that allows a particular implementation of multi-touch should be patentable however.

There is another tech issue that I need to talk to prospective candidates about: their stance on ODF vs OOX ML, and more widely: their stance on the promotion of the use of open standards within government.

Can't think of any more tech issues at the moment but if you can think of any...

P.S. Happy birthday to me. Happy birthday to me,...