non-authoritative information

desktop data structures

2011-01-18T02:40:00.005+13:00

Most humans when sorting—ordering a deck of cards, for example—use a method that is similar to insertion sort. —Wikipedia - Insertion Sort

The obvious lessons:

Insertion sort is a simple and intuitive algorithm
The obvious algorithm is sometimes slow
Humans optimise for human-sized problems

Hang on though, when I sort a deck of cards, I do this:

Sort 5 cards through some intuitive process.
Grab another card (if there is one)
Find where it goes
Insert it
Go to step 2

But I certainly don't lay all the sorted cards out in a line, and move them all across by one when I insert one into the list. I just make a gap and stick the card in. This doesn't take longer if i have more cards!

What does take longer is finding the right place to insert a card, but when this gets hard I end up using a modified binary search. (Modified because I know something about the distribution of cards, and because it's easy to look at (and cache) a few consecutive cards). So this is log(n), and the overall algorithm is O(n log n), or as we say in Germany, 'fast'^[1].

The ringbinder

We get away from it because real life has a 'data structure' that's half array, half linked list:

'Get the nth item' is constant time (ish. You get pretty good at estimating how thick 10 cards are)
Insert an item is constant time.
Remove an item is constant time

I'm going to call this structure the 'Ringbinder' because 'Stack' is already taken by something that behaves nothing like any real-life stack I've ever seen. For sufficiently large values of N, your program will run faster using a USB robotic ring-binder operator rather than an ArrayList. You heard it here first.

Divserion: quantum bogosort

Cheating at algorithms using real-life's weirdnesses isn't new. qfork() is a version of fork() that returns a different value in each quantum universe. So we sort in O(n) like so:

srand(qfork());
shuffle(data);
if(!sorted(data))
   exit(1); // todo cleanup world

I mention this only because it amuses me.

So, seriously?

I guess at some point physically moving the cards to make a gap doesn't actually take constant time. If our robot can exert some fixed force and has to move n items just enough to make room for one more, then this takes O(√n) time^[2]. Revised performance:

Go to index: O(√n)
Get next/prev: O(1)
Insert/delete: O(1)

This makes our insertion sort O(n^1.5 log n) which is no longer state of the art. But surely there are currently-optimal algorithms where using this data structure would give better asymptotic performance than we get on our fancy-pants von Neumann machines^[3]. Or maybe I'm missing something. I'm probably missing something.

Any others?

What other data structures can you build from common household items that put our silicon masters to shame when it comes to data processing?

(Using people to demonstrate the power of parallelism doesn't count, It's been done).

[1] working for American software companies is a lousy way to learn German.

[2] F=ma, s = at^2, etc.

[3] and way worse real-world performance, as we're shoveling around avocado-sized chunks of matter instead of deftly handling individual atoms. Still.

the old man and the cspan

2010-03-25T22:56:00.003+13:00

I've been watching the USA healthcare fiasco (surely, the appropriate word) with a sort of morbid curiosity.

Although comparisons to the American Civil Rights movement seem a little strained, there is one element that draws the two together in my mind. It's hard to understand, looking back, how reasonable people could have found segregation to be just; similarly I can't find the right cultural lens to see a medical safety net to be unneccessary or even immoral, in a country that can manifestly afford it.

Of course the difference is that this America is here now, with few cultural barriers from where I sit, and so you can watch it tick in real-time and even converse with it. And sometimes marvel at the schizophrenic behaviour that loves teams but hates collectivism, and values the Constitutional means over the moral ends.

The high-stakes game theory involved in passing controversial legislation has been fascinating recently. There is a disconnect between the centrist reality^[1] and the "left-wing" label that the bill is receiving from left and right alike. Ben Hyde writes:

If you map out the left-right spectrum of the nation and the legislatures the reform we got falls at the center. That was exactly what Obama signaled he would aspire to deliver; going all the way back to the earliest days of his campaign. As a practical matter this bill is about exactly as far to the left as anybody should have hoped for. The party on the left doesn’t get to pass a bill that is at the center of it’s party member’s opinions. You only get to pass a bill that gets you the vote of that last necessary right most legislator.

That's only the case if those on the right are willing to go without reform. The Republicans clearly are (for this electoral cycle), having made the calculation that an ineffectual government with a Democratic majority will give them a win at the next election. However, the right flank of the Democrats don't have this strategy available to them. If they truly wanted healthcare reform, Ben's logic would equally well suggest that a bill would have to cater to the left of the party. Simple symmetry says that with Republicans out of the picture as potential votes, the bill should indeed be written by the median Democrat if as Ben says:

But yet [the] old system was on the fast track to making American industry entirely unable to compete. And hence even those who think that Government’s only function is to help large economic actors were largely in support of reform.

One would hope so, and the refrain from the holdouts has been "Everyone agrees we need reform, but". The evidence is thin on the ground.

[1] By US standards. From my perspective, comprehensive government-run healthcare like in NZ or the UK would be favoured by the left, private healthcare funded by taxes (e.g. Canada) or public health insurance would be considered centrist, and the regulated private healthcare just passed would be a right-wing proposal.

what encoding is that?

2009-11-17T01:20:00.005+13:00

A few times in a project I'm working on, I've got some binary data that represents encoded text in some unknown encoding. Sometimes I know what it should decode to, and sometimes not.

Encoding Tools is a small application that decodes a byte string in a bunch of ways, and tries to guess which is correct.

It runs on Mac OS X 10.5 or later, and the source is available from the link above.

Hadn't used "real" Cocoa (as opposed to Touch) in a while, so this was a good excuse to play with Bindings and NSTokenField.
The former is very cool, but not quite as seamless as I thought - you get your UI and model synced without writing any extra code, as long as you do things in a KVO-compliant way, which requires writing non-idiomatic extra code.
NSTokenField would be nice if it wasn't broken by default.

in which I actually write some software

2009-08-30T11:45:00.005+12:00

Biostats Calculator appeared on the iTunes App Store the other day, after an approval process that felt like it took years (but actually was only a couple of weeks). It's my first iPhone app so it's kind of exciting, and some have been sold already (Hi, Colombia!), which is really exciting in the paying-my-rent kind of way.

The application performs various biostatistical significance tests - relative risks, t-tests, chi-squared etc - and a couple of other calculations. (Full details are on the website). It aims to provide the most common statistical calculations a medical researcher might need, without having to go back to their computer and deal with a full statistics package. Also, it's totally awesome and you should buy it and tell your friends.

</plug>

Other notes:

Objective C is awesome. Garbage collection is disabled on the iPhone, which I thought would bother me but is actually hardly a problem at all. It really gives you a sense of how simple the language as an extension of C - basically just objc_msgSend and a little bit of preprocessor magic. And knowing how the OO constructs work allows me to feel completely comfortable mixing in plain C instead when it's more natural. (I'm still not sure how autorelease works. I'm pretty sure it's magic.)
Apple did a really good job on Cocoa Touch. The simple things seem to just work, and the hard things aren't all that hard. Except where they're impossible by design, per the next point.
They're serious about their Human interface guidelines. The first submitted version of the application used an 'add contact' button icon (rendered as a blue plus-sign) to add data to a data set, and they rejected it for misusing a standard icon. I took a screenshot of the button, tinted the image green, and they had no problem with that.
The approval process is frustating. They have an actual human test your application, make sure it doesn't crash, follows guidelines, and does what it says on the box. I think this is a really good thing that drives up application quality and platform consistency, but it means waiting a couple of weeks between finishing the app and it hitting the store. Plus you get to repeat the whole process when you didn't read the HIG and used the wrong button icon. Ahem.
Despite not being quite as streamlined a process as I would have assumed (lots of forms to fill out, certificates to download, having to get a credit card in my name to open an account, etc) the App Store is an amazing service. You develop the software, describe it, and decide how much it should cost, and that's it - you don't have to work out how to sell it, just what the next app will do.

Enjoy - a JoyToKey clone for mac

2009-05-14T06:24:00.005+12:00

JoyToKey lets you map joysticks to keyboard buttons to control programs that aren't joystick-aware. Gamepad Companion is a similar thing for Mac but it's nagware and it annoyed me. Also I wanted the ability to automatically switch configurations depending on the active application. So: Enjoy.

Somewhat related: half-working hack to get the tilt-sensor on a generic PS3 guitar hero controller to work with Frets on Fire.

poker paradox?

2009-03-03T00:23:00.006+13:00

hold'em in a nutshell

Each player has 2 secret cards, and later 5 shared cards are revealed. Players bet on who has the best combination of cards both before and after the shared cards are revealed. Most secret cards are not worth betting on, good players will play between 10% and 30% of their hands.

three common principles

Deception (fundamental theorem of poker): if your opponent has less (or wrong) information, you make more money than if they have more information
Hand strength: all else equal, you make more money with higher cards than lower cards. (E.g. 9♣8♣ vs 8♣7♣)
Style: a range of styles can be equally profitable, for example you may be able to maximise your winnings by playing anything from 10% to 30% of hands.

the problem

These principles seem axiomatic (except perhaps the third, but empirically it seems true). But they conflict:

Take two optimal strategies: a tight 10%-of-hands game "A" and a loose 30% game "B".
At the start of each hand, flip a coin, and play either strategy "A" or "B" accordingly. Call this compound strategy "C".
A player who's played against either A or B for long enough knows they play 10% or 30% of hands respectively, and they're winning so it's probably the best 10% or 30% of hands. (Strictly, a best 10%. Hand strength is only a partial order, it doesn't compare 9♣8♣ to 2♢2♠).
A player who's played against C knows that he plays 20% of hands. If the player is very observant he might know about the coin-flipping, but if the coin is hidden he doesn't know whether he's playing against A or B for a particular hand. In either case, he's playing against an optimal strategy with less information than last time, so when the coin comes up heads C makes more money than A, and when it comes up tails C makes more money than B. So C is more profitable than A and B (which were supposed to be equal and optimal).
Strategy C involves sometimes playing hands in the 20-30th percentile, and sometimes not playing hands in the 10-20th percentile. According to hand strength, we'd make more money by replacing some worse hands we're playing with some better ones we're not playing. This gives a strategy "D" where we flip a coin play the top 20% of hands according to strategy A or B.

So D > C > A and B, but A and B were supposedly optimal.

resolutions

The first weakness I can see is the assumption that it's always incorrect to throw away a more profitable and play a less profitable one. A hand like 5♡7♡ that rarely wins may be profitable if played occasionally because when it does win your opponent will discount the possibility that you have it. However you have to fold it most of the time, even though playing it would be profitable for that individual hand, to maintain this value.

I'm surprised that the benefit from playing a probabilistic strategy is big enough to counteract the 'paradox'. Most analysis online tends to focus on opponent ranges - the range of cards they might have based on their actions in the hand - and it's assumed in calculations that the opponent would play their cards that way every time. Against good opponents, the edges of the ranges will be significantly fuzzy, and not accounting for this makes for flawed analysis that loses money (fundamental theorem again).

The second weakness (thanks Kyle!) is the assumption that C gives our opponent less information than A or B. This is intuitively true if A and B are deterministic, in the same way that a coin-flip is more uncertain than 'heads' or 'tails' individually; but if they A and B are probabilistic then C may be no more uncertain - the average of two random numbers is not 'more random'.

guessing games 1

2009-01-26T01:37:00.012+13:00

One of the first programs I ever wrote was a number guessing game:

I'M THINKING OF A NUMBER BETWEEN 1 AND 20
> 7
HIGHER
> 15
HIGHER
> 18
LOWER
> 17
YOU WIN

(The Commodore 64's green was brighter of course, but I wouldn't do that to you). The best strategy for beating the game, of course, is to pick the middle number of the range first in order to break the range in half. If that didn't happen to be the right number, you have a new possible range that's half the size, and you repeat the process. This is binary search at its purest. It's the best strategy in two ways: it always finishes in at most 5 guesses (worst-case performance), and the average number of guesses needed if you pick randomly is 3.7 (average-case performance).

I tried to write a program to do the guessing, but I couldn't work out how to let the user type "higher" or "lower" instead of numbers, and I gave up.

twenty questions

It's the same game, except instead of a number you can pick anything, and the guesser is allowed twenty yes-or-no questions to try to work out what it is.

I'M THINKING OF A SOMETHING
> IS IT ORGANIC?
YES
> IS IT ALIVE?
YES
> IS IT A PLANT OR AN ANIMAL?
YES
> LOL, IS IT A PLANT XOR AN ANIMAL?
NO
> IS IT ROBERT PLANT?
YOU WIN

Obviously it wouldn't be an easy program to write, but in theory it's possible if we formalise the game. First we need a dictionary, a list of all the possible objects the computer can be thinking about. There can only be a finite number if we want the game to be winnable.

Next we need a set of questions. Every yes-or-no question breaks the dictionary up into two sets: things that answer 'yes' and things that answer 'no'. We can characterise all questions by the sets of things that answer 'yes' (the objects they accept). Two questions that accept the same objects are really the same question.

Suppose our dictionary is {barrel, cat, dog, ball, fish, box, building}. The question "is it an animal?" accepts the objects {cat, dog, fish}. It's the same question, for our purposes, as "is it a cat or a dog or a fish" or "does it not begin with b".

If we allow any question (that is, any set of objects) to be asked, then the game becomes trivial: we can reduce it to the number guessing game. Just number all the objects, break them into ranges, and ask questions like: "Is it barrel or cat or dog". This is the optimal strategy, which implies that you can't always win at twenty questions if there are more than a million possible answers. But it makes for long and boring questions, so in the informal game we might say you're only allowed twenty words per question. In the formal game we'll say you're provided with a list of questions you're allowed to ask.

So our dictionary might be: {barrel, cat, dog, ball, fish, box, building}. And our questions might be:

{cat, dog, fish} ("is it an animal?")
{cat, dog, ball, box} ("can you play with it?")
{barrel, ball, box, building} ("does it begin with b?")
{barrel} ("is it a barrel?")
{cat} ("is it a cat?)
etc...

The "is it a X" questions aren't strictly required, you could say you 'win' as soon as you know exactly what the object is. They do guarantee it's possible to win though.

A strategy for 20 questions is a tree flowchart like the one for the guess-the-numbers game. Here's one for a poor strategy: just guessing.

The height of the tree is 6 which indicates it may take us six guesses to work out the object in the worst case. This next one is better (height 3). In fact it's optimal: since it is as good as binary search we know there is no better strategy. Usually the optimal strategy won't be as good as binary search.

The question is: how do we efficiently calculate the optimal strategy? Either on the fly - i.e. given the information we have so far, determine the next question to ask - or by pre-computing the entire flowchart.

More formally: given a set S and a collection of subsets T ⊆ ℘(S), construct a binary tree with leaves S and internal vertices T of minimal height, such that every left-descendant of t is in t, and no right-descendant is.

An obvious heuristic, reminiscent of binary search, is to always ask a question that splits the remaining possibilities as close to evenly as possible. While we might expect that this 'greedy algorithm' is optimal, it isn't due to interactions between questions. In the diagram below, question A divides the space of objects neatly in half, but whatever question we ask next we can be left with around a third of the objects afterward. Starting with questions B and C guarantees only a little more than a quarter of the possibilities remain after two questions.

A naive but approach is to recursively find the best left and right subtrees for the subsets induced by each first question, and choose the question that gives minimal max-height. Ultimately this runs takes exponential time since we find the tree for all 2ⁿ subsets of the dictionary. It has the feel of a hard problem, I wonder if exponential time is the best possible.

and you shall know a webcomic by the questions he (frequently) answers

2008-11-16T00:52:00.002+13:00

Amazing Super Powers is still funny when sober? Signs point to yes.

on envelopes

2008-11-11T17:43:00.002+13:00

The two-envelopes problem, via xkcd. I'm not goint to re-hash it here, because it makes me dizzy, and the wikipedia page is fine. It's a 'paradox' of probability/game theory - like Monty Hall problem but without goats, cars, or a convincing solution.

There doesn't seem to be any dispute that if you can take a 50-50 bet that will either double or halve your money, then you should - your average profit is 25%. On the other hand, looking in your envelope doesn't give you any useful information, and switching without looking can't possibly earn you money in the long run. So what's going on?

Clearly the odds bet isn't 50-50! And the problem is that in order to fill the envelopes, we have to randomly pick an amount of money $X to put in the small envelope. But what does random mean? We can't have a uniform distribution over an infinite range - it doesn't make sense. You're trying to pick a number at random between 1 and infinity, whatever you pick will be in the bottom 1%.

Once we look in the envelope and see $Y, we know X = Y or X = Y/2. It's only a 50-50 bet if those possibilities are equally likely, and there aren't any probability distributions that have P(Y) = P(Y/2) for all Y.

So the game, as stated, can never be played. Any real randomizer for the game is going to give the player worse than 50-50 odds in some cases, and they won't make profit by switching in the long run.

that other election

2008-11-10T10:29:00.005+13:00

So New Zealand just had our election. My take on the results: disappointing, not surprising, and not the end of the world.

The process was pretty uneventful compared to certain recent elections. Most of the difference can, I think, be attributed to a less polarised political culture; but part is the proportional representation system that prevents some votes being worth much more than others according to which part of the country you live in. The importance of a few 'swing' states (Ohio, Florida, et al) makes it tempting to try to tip the scales, and the rush of attention, money, and pressure to them provides the opportunity. If every vote is worth the same, election fever is spread out and doesn't boil over. (You like that metaphor? I mixed it myself).

mmp is broken

But we don't quite use proportional representation. New Zealand's system gives everyone a vote for a party, and a vote for a local MP. The party votes decide the proportional makeup of the parties in parliament. The electorate votes decide who your 'local MP' is. This is a carry-over from our old system where a parliament was made up of all the local MPs.

The upshot is that if the Banana party wins half the votes, they get 60 seats (out of 120) to fill with bananas. If Alice, Bob, and Carol from the Banana party all won local seats, then they have to be included. The other 57 seats are filled from a party list.

But there's a situation called 'overhang' that happens when a party wins too many electoral seats. Suppose the Banana party wins 65 electorates - more seats than their proportional fair share. What happens is 5 extra seats are created, so parliament has 125 instead of 120. All the electorate MPs are seated, and of course they don't get any list MPs. The proportionality has been distorted - the party with 50% of the vote got 52% of the seats.

This is pretty much impossible, there are only 70 electorate seats and to win that many without getting more than 50% of the vote isn't going to happen. But it can happen with smaller parties, in particular those with regional appeal. In our last election in 2005, we had an overhang for the first time. The Maori party won 4 electorate seats, but only had 3 seats worth of party vote.

and getting worse

This time around they got 5 electorate seats with basically the same party vote, creating an overhang of two seats. So far, so slightly odd. Now I'm going to do something very odd and assume both politicians and voters are rational.

Suppose you're a Maori party supporter. You know they tend to win more electorate seats than their party share. If you give them your party vote, you're not going to increase the number of seats they get, you're just going to decrease the size of their overhang by one. This increases their power a little (5/121 seats beats 5/122) but not much. Suppose they have a naturally allied party that doesn't have an overhang. You're better off giving that party your party vote, to better increase the size of your bloc and therefore the chances Maori make it into a coalition government.

Now suppose you're the Maori party. You realise this vote-splitting is better for you too, so you put out a TV ad directing supporters to vote that way. The Maori party vote drops to almost zero, they have the same number of seats, and more powerful allies.

If you're the allied party, you realise that running local candidates helps your profile a bit, but doesn't actually increase your share of parliamentary power. The Maori party winning electoral seats does help you, though, because it increases your voting bloc. So you stop running electoral candidates against them, and possibly encourage your popular local candidates to switch parties.

So given two allied parties, once one achieves an overhang, rational behavior leads to one becoming completely electorate-based, and one completely party-based. We have two single-seat parties in parliament at the moment, although both got enough party votes to 'cover' their electoral seat and avoid overhang. I think at least Jim Anderton may explicitly aim for an overhang next time, effectively running as an independent.

major parties?

Could a major party split in half to achieve the same thing? There are some practical problems:

You can't give list seats to people if they lose their electorate, if they're not in the same party. You'd probably just want to split off the party's 'safe' seats.
People will see it as cheating, and react negatively. A minor party has less choice, and more dedicated supporters, so can get away with gaming the system. A major party is likely to suffer blowback. However once one party succeeds with it, the others need to follow suit to be competitive.
You'd lose some support just due to the confusion - we're assuming rational and informed voters, but not everyone's going to split their vote in the desired way. For example, they might vote for the 'electorate' party.

If a major party did this the rules would almost certainly be changed quickly. The temptation is great, though - splitting your supporters' electorate votes to an overhang party increases its power by around 57%, and not taking advantage of this leaves votes on the table.

solutions?

Wikipedia discusses forms of MMP without overhang seats. The only one that sounds unreasonable is a system used in some German states, where extra party seats are allocated to restore proportionality. Supposing a party won 0.1% of the vote and 1 electorate seat (which would no longer be strategically clever, but can easily happen). To restore proportionality you need to inflate parliament to 1000 members!

My personal opinion is that sacrificing proportionality to provide strong voices to particular groups is misguided. If parliament can protect against injustice to minorities in general, then it can protect against injustice to certain parts of the country. (And if a parliament doesn't protect minorities from mob rule, it needs to be redesigned). If the need for advocacy is there and local governments aren't strong enough, perhaps the electorate vote could be changed to non-voting advocates to parliament.

It's like looking into the eye of a duck

2008-10-27T09:18:00.009+13:00

If colour is a spectrum of frequencies from low to high, why does it form a circle? And why can we make it all up out of three 'primary' frequencies?

I never quite got this, and this article on Pitch and Color Recognition is a fascinating read.

In short, our eyes have specific receptors ('cones') for red, green, and blue light. But they don't just pick up one particular frequency from the spectrum, they respond strongly to a small range of frequencies, with a bell-curve decay as the colour changes.

The odd-one-out is the red receptor, which starts to trigger again at low frequencies (violet). The perceived 'hue' is determined by the ratio of the responses, which is similar at low and high frequencies, thus the cycle.

Now if you work your way through the spectrum, measuring the response to pure monochromatic light of each colour, you get the blue horseshoe path in this diagram which I had often seen but never understood.

X is full red response with nothing else, Y is full green response, and Z is full blue response. Note that no pure frequency of light can get this response - there's no point on the previous graph where only one receptor responds.

If you mix two colours together, the responses get added together (that is, averaged) so the response lies inside the horseshoe. So the horseshoe contains all the colours that we could observe in the physical world. What do the points outside, such as X, Y, and Z represent? There are 'colours', which we are biologically capable of perceiving, that don't exist in the real world.

As for the RGB colour triangle - it's an approximation. Mixing light from the three points labeled R, G, and B can achieve any colour inside the triangle they form. The small area outside the triangle but inside the horseshoe contains colours that occur (rarely) in nature, and cannot be accurately displayed on a monitor or television. Adding more primary colours is limited help - they have to be actual frequencies of light, so they lie on the horseshoe and approximate it with a polygon. You can never represent all colours by mixing a finite number together, although you can get arbitrarily close.

There's so much more in the article though...

interviews

2008-10-02T16:55:00.005+13:00

discursive

2007-11-30T03:05:00.000+13:00

Am I discussing something, swearing at you, or just writing in a way that's painful and difficult to read? Actually, all of the above. But what it really means is off-topic rant.

Blog is still a fucking ugly word, is it too late to elect a new one?

static typing gets a bad rap

2007-11-28T09:52:00.000+13:00

it’s not necessarily about dynamic languages - Chuck Hoffman draws nicely the distinction between the enterprisey static-typers and the academic static-typers. Java vs ML, if you will.

The fact that you write

new JButton(new AbstractAction("test") {
  public void actionPerformed(ActionEvent e) {
    System.out.println("hi!");
  }
});

has little to do with static typing and everything to do with design philosophy. The language itself was supposed to be explicit and purely object-oriented, and the library aims to be extensible through abstraction. I'm sure those sounded like great ideas at some point.

Equally viable, but not present in the "languages you can make money in" class, is

new JButton("test") {(e)
  println("hi")
}

Personally, I find static typing very useful in external APIs and mostly unhelpful elsewhere. While you gain rock-solid code completion and catch the occasional type error, you introduce new type errors - the 'compile-time types' that static analysis deals with can cause errors in otherwise correct code.

So dynamic JavaScript 2's optional type declarations seem preferable to D or C# 3's reduced-pain static type system, but it's not the religious issue for me that I thought it was.

you know you're a nerd when...

2007-11-23T02:49:00.000+13:00

... finding planar embeddings of graphs by hand is your idea of fun.

Planarity (flash) is addictive though. You get a graph (a bunch of dots, some of the dots joined with lines), and have to move the dots around so that the lines don't cross.

There's a theorem that says bending the lines doesn't help - if you can do it with curved lines, you can do it with straight lines.

Some graphs can't be solved though. There's a superior (IMO) version for gnome called gPlanarity that has 'no more than 4 crossings' type levels which are harder, and not just subjectively. There are efficient algorithms to test for planarity and find embeddings, but for nonplanar graphs even determining the minimum crossing number is NP-hard.

NP, of course, is the technical term for very, because you need a technical term for everything.

bytecode generation for fun and profiling

2007-11-21T22:24:00.000+13:00

interfaces

An interface in Java is just a list of methods that can be implemented by classes. This lets you access objects of different classes in the same way, even if their implementation is unrelated.

At least in principle, the interface is written first, and then the class references it:

class Widget implements Drawable {

But to turn it around, you could define an interface as a subset of a class's methods, and use that to reduce coupling and allow calling code to be compiled without access to library code (common in J2EE).

The problem is that the class has to be tagged implements X at compile time.

example

I was working on a web-app and needed to set a parameter on an Oracle data source. I had a generic DataSource object, and the solution was to cast it to its real oracle.jdbc.pool.OracleDataSource and call the method. Three problems:

I now have to include the oracle driver when I compile
If a driver update or reconfiguration alters the class name, not only will my fix not work, but my if(ds instanceof OracleDataSource) line will cause a crash
This is pretty generally grungy just so i can call setFoo(true).

These can be hacked around by using reflection, but it's ugly, not typesafe, and slow (less so these days).

They can be fixed if the class implemented an interface which was provided in a separate jar, but it doesn't.

build a bridge and get over it

public interface ToggleFoo { public void setFoo(boolean v); }

Bridge.expose(datasource, ToggleFoo.class).setFoo(true);

The Bridge utility creates a wrapper class like this:

public class Bridge_OracleDataSource_ToggleFoo implements ToggleFoo {
   private Object __target;
   public void setFoo(boolean v) {
      ((OracleDataSource)__target).setFoo(v);
   }
}

It then instantiates it and sets __target to the object you pass. Since the wrapper is flagged as implements ToggleFoo, the instance can be cast to ToggleFoo and returned.

The class is generated at runtime using Apache BCEL. The compiled bytecode is created directly, without source code, and loaded using a custom ClassLoader.

When expose(Object, Class) is called (the Class object represents an interface), the library uses reflection to find the correct type to cast the object to. The same rules of visibility normally enforced by the compiler apply at the JVM level, so there has to be a public class/superclass that implements the methods in the interface.

subsetting interfaces

Another use is to convert from an interface type to a more restricted interface - a 'superinterface' that was never specified. For example:

public interface ImmutableList { 
   int size();
   Object get(int i);
}

ImmutableList lst = Bridge.expose(myArrayList, ImmutableList.class);

Now lst can be securely passed to client code without fear of modification.

performance comparison

Setup: When a type exposes a new interface, the bridge class must be generated and loaded. This is actually very fast (~5ms in my tests) but the first time requires BCEL to load, which took about 500ms. I haven't included this in tests below, it's important for short-running tasks.

Each object: calling Bridge.expose() allocates a small new wrapper object, and sets a field in it.

Each call: Calling a method through the interface requires an interface method call (slower than a normal virtual one), a field access, and a virtual method call to the target.

The common alternatives to a bytecode generation approach are direct access and reflection.

Direct access to the object is always going to be fastest, and it's important to know how much speed you're giving up for this decoupling, or security (in the case of subsetting an interface). There is no setup, each object just has to be cast to the correct type, and calling is just a virtual method call.

Reflection was optimised in Java 1.4, but is still carries a penalty. Class.getMethod() must be called for each new class of target. In my test all targets were in fact the same class (even the same instance) but the code did not assume it, so the fact that the class is the same has to be checked for each new object. You call the method with Method.invoke().

Timing results

Test	Direct	Reflection	Bridge
Invoke virtual method on same object	68ms	2772ms	258ms
Invoke virtual method on different object	70ms	2808ms	5621ms
Invoke method through interface on same object	163ms	3384ms	237ms

edit: improved performance by 30% on second test by removing an extra object allocation. Allocating objects in a tight loop is still slow.

Testing was on Sun Java 1.5.0_11 i386 on Linux (Ubuntu 7.02), on my laptop (Athlon XP 1800+). source

code

Is here. If it breaks, you keep both pieces. You need bcel.jar on your -classpath, from here.

There's a new library to generate JVM bytecode from ruby. I'm not so hot on JRuby, but this looks cool for learning the bytecode.

save the world in 2 x 10^15 easy steps

2007-11-21T03:41:00.000+13:00

FreeRice is distraction o' the day. The premise is you play a spot-the-synonym game and improve your vocabulary. There are ads on the page, and they claim to donate 10 grains of rice to charity for every question you get right. There's a counter on the side of the screen showing how 'generous' you are so far. There's no sign-up, and no restrictions on how long you play for.

Assuming they're being straight with us, my first thought is that the advertisers are getting fleeced. You load a new page (and new ads) with each answer, say every 30 seconds, and you're pretty intently focused on the middle of the screen. At 1024x768 (still on the laptop) the ads aren't even visible. I guess we're meant to be getting warm fuzzy feelings about the companies, but it seems more like a clever hack than a business model.

(Hmm, and they only pay out rice for correct answers. On the other hand I bet advertisers would pay double to be able to show ads to dumb people. I take it back, it's a brilliant strategy!)

The game itself is addictive. Knowing what the words mean is a plus, of course, but you can do pretty well boggling at prefixes and suffixes and word roots (periphrasis = circumlocution was a striking example).
And the 'feeding poor children' angle takes the edge off the 'should have stopped ten minutes ago' guilt. Ignoring for the moment that it takes more than 10,000 correct answers to make up the equivalent of a $US100 donation. (Figures from here).

american politics never fails to deliver

Check this out. Words fail me.

HuckChuckFacts @ YouTube - Mike Huckabee's first campaign ad.

edit: it's official - Ric Flair: "Mike Huckabee is the Man, Whooooo!"

uninteresting and non-technical

2007-11-18T18:56:00.000+13:00

So much for 'interesting technical stuff'... They took the Daily Show clips off YouTube so I wrote a script to pull them off the official website, making a couple of cogent points.

I need a bigger hard drive. Okay, this was the only one I'd call cogent.
Using DRM to stop people from archiving free content wouldn't be totally ineffective. If they'd so much as bothered to gzip the xml descriptor that contains the download key for the video, I'd probably have missed it and lost interest. Someone smarter would still have found it, but they probably have better things to do.
The result in my case would have just been not to bother watching it. It actually shows on TV here, but I've got a 50% attrition rate per ad-break - I'm easily distracted.
Result for them: I don't watch any ads, I might buy some of the books of authors interviewed, or action figures of the actors or politicians. I doubt Comedy Central get any income that way. I cost them a bunch of bandwidth.
Same on TV, but replace 'bandwidth' with 'broadcasting costs'.
Same on YouTube, but replace 'broadcasting costs' with 'nothing'.
Great programmers are meant to be lazy. I just spent Sunday watching TV shows using only my spacebar and my big toe. I hope it's a linear relationship.

analyse this

2007-11-15T03:55:00.000+13:00

James Governor:

Microsoft analyst relations (AR) has begun to use a format it is calling the fireside chat, in which a senior executive talks without PowerPoint to a select group of analysts.

What's it called when you present more clearly by throwing away the presentation software that you sell for a living? Oh yeah, innovation!

restful robot

2007-11-15T01:24:00.000+13:00

Despite licensing questions and lock-in concerns, google's android SDK is pretty damn exciting.

For all the anti-hype about it not being a gPhone, the hardware wouldn't have been the cool part anyway. Google would rather be Microsoft than Dell, and the part of Apple has already been cast.

Reading through the documentation (and it's good) shows they've had some smart people thinking hard about how applications should work. The appearance of the applications is your standard stack-of-screens, i.e. you can go back 'up' to the parent screen, but the way you implement them is different from desktop and J2ME applications and closer to web applications.

Each screen type is called an Activity, and activities are well separated from each other. Instead of creating a screen by instantiating it and passing it a bunch of state directly, you identify an 'intent' - a URI representing that state plus the action you want to perform, and pass it to android. For example: instead of creating a ViewContact, passing it a Contact object, you request to VIEW content://contacts/6. It's reminiscent of HTTP in a way that can't be coincidental.

The URIs are managed by ContentProviders that serve as the model in your applications, and they have content types. Activities define which content-types, actions, and URIs they can handle and android selects the right one.

This has lots of benefits for the ways applications work together. On the web, I can link to a photo on my friend's website, and they can change it from a JPEG to a PNG, or to a movie, or to a webpage with 20 photos, and the link still works.

Most of the rules for android apps are actually guidelines - you can refer to activities explicitly, and you can pass more than a URI. There are pragmatic reasons for tight coupling of internal components in some cases. But if applications play by the rules where functionality can be cleanly separated, web mashup type apps might make it to the phone.

tone generation in java

2007-11-13T02:44:00.000+13:00

Frigging java. I claim to hate it and yet I can't resist being able to run in a browser. Anyway, if there's an easy way to play a tone of an arbitrary pitch (not neccesarily on the MIDI scale) I couldn't find it. Here's some code for google. Usage:

SineWave tune = new SineWave();
tune.play(440, 0.5); // C4 - frequency in hertz, duration in seconds
tune.play(554.4, 0.5); // E4 - play() blocks until the end of the note
tune.play(659.2, 0.5); // G4 - I'll probably do an async version later
tune.play(880, 1); // C5
tune.closeLine();

Show code

// this code is in the public domain
import javax.sound.sampled.*;

public class SineWave {
 public static final float SAMPLE_RATE = 44100F;
 public static final int SAMPLE_SIZE = 16;
 public static final short MAGNITUDE = 0x7000;
 // 44.1 kHz 16-bit mono signed little-endian linear PCM
 AudioFormat format = new AudioFormat(SAMPLE_RATE, SAMPLE_SIZE, 1, true, false);
 SourceDataLine line;
 byte[] buf;
 int attackLength, decayLength;

 public SineWave() { this(0.01,0.01); }
 public SineWave(double attackTime, double decayTime){
  attackLength = (int)(attackTime * SAMPLE_RATE);
  decayLength = (int)(decayTime * SAMPLE_RATE);
 }

 private SourceDataLine getLine() {
  if(line == null) {
   DataLine.Info info = new DataLine.Info(SourceDataLine.class, format);
   try {
    line = (SourceDataLine)AudioSystem.getLine(info);
    line.open(format);
    line.start();
    buf = new byte[8192];
   } catch (LineUnavailableException e) {
    throw new RuntimeException(e);
   }
  }
  return line;
 }
 private void closeLine() {
  line.stop();
  line.close();
  line = null;
  buf = null;
 }

 public void play(double frequency, double seconds) {
  long max_sample = Long.MAX_VALUE;
  if(seconds > 0)
   max_sample = (long)(seconds * SAMPLE_RATE);
  long position = 0;

  double signal;
  double multiplier = 2 * Math.PI * frequency / SAMPLE_RATE;
  short sample;
  int bufferPos;

  SourceDataLine line = getLine();

  while(position < max_sample) {
   for(bufferPos = 0; position < max_sample && bufferPos < buf.length; bufferPos += 2) {
    signal = MAGNITUDE * Math.sin(position * multiplier);

    // linear envelope at each end to avoid clicking
    if(position < attackLength)
     signal *= (double)position/attackLength;
    if(position > max_sample - decayLength)
     signal *= (double)(max_sample - position)/decayLength;

    sample = (short)signal;
    buf[bufferPos] = (byte)(sample & 0x00ff);
    buf[bufferPos+1] = (byte)((sample & 0xff00) >>> 8);
    position++;
   }
   line.write(buf,0, bufferPos);
  }
 }
}

letters to the editor

2007-11-12T13:57:00.000+13:00

Just to prove I'm old. And because such unmitigated disingenuous bullshit makes me too angry to even work out a rational opinion on the subject.

Reproduced here ~~because I doubt they give the shit they say they give about speech.~~

If the Herald is concerned that spending limits will impact free speech, it could start by halving the cost of all political advertisements. The primary beneficiaries of the saturation publicity race are the media outlets that sell the advertising. Domination of public awareness by big spenders is a threat, just as suppression of speech is. To present this as a one-sided moral issue is self-serving and irresponsible.

the sound of music

2007-11-12T10:36:00.000+13:00

Another year, another illusion shattered.

regale me with a story!

The thing that fascinated me about learning music, as a proto-geek (I gave up because I didn't have the discipline for practice) was the elegant way the scale fitted together. Playing in C major, G was clearly the next-best note - and G had its own scale, differing by just one note. D was the best note in that scale, and continuing in perfect 5ths took you all the way around - C G D A E B F# C#/Db Ab Eb Bb F C.

the radical antagonist

The pitches formed a nice pattern too - C₄ (middle C) was half the frequency of C₅, and double the frequency of C₃. Semitones, the indivisible atoms of notes, were equally spaced with 12 to an octave. Multiplying rather than adding seemed to be the way to go, so I figured out that to get a semitone higher you multiplied by ¹²√2. I then wrote a cute little program to play Mary Had a Little Lamb, as if to prove that math really can't teach you about music.

discord

I didn't really wonder why C made that G sound so good. That was an Art question, I didn't own a beret, and I was still cutting my hair at that point. But it was closely related to why all Cs sound the same.

Notes forming a 'perfect' fifth have frequencies in the ratio 3/2. A fourth is the ratio 4/3 (so a fourth plus a fifth is an octave, 3/2 x 4/3 = 2). A third is 5/4 (major) or 6/5 (minor). Problem is, these fractions aren't what you get when you glue a bunch of your ¹²√2 semitones together. 7 semitones is 2^7/12 ≅ 1.4983 - 2% away from perfect harmony. The circle of fifths raises the pitch by (3/2)¹² ≅ 129.74 times - 2% more than 7 octaves.

So this music thing less of a deep truth about the universe and more of a weird and meaningless approximate coincidence.

You can tune your piano by

Setting the notes to nice fractions of C (but music in other keys will be out of tune)
Finding notes with a circle of perfect fifths, but the fifth that joins the circle up will be too small, leaving (typically) G# and Eb badly out of tune
Spreading the discrepancy equally across all notes, which is what we generally do now. It's regular and you can modulate betwteen keys freely.

the thing about coincidences

You can find more if you look hard enough. There's no way to find an equal division of the octave that will give you a perfect fifth - or any nice harmonic. n 'semitones' in an m-division scale is 2^n/m which is irrational.

The next equal division size after 12 that can measure a fifth pretty accurately is 29 (3.6% error). 41 does better than 12 (1.6% error) and 53 is very good indeed (0.03% error). Music has been composed in these. I'm curious though, whether our familiar time signatures of 2, 3, 4, and 6 notes work as well in other divisions, or whether dividing evenly into the scale is an important attribute.

And of course you can divide intervals other than an octave to form a scale. In particular I'm curious about an octave + fifth such as C₄ - G₅ - a 3:1 frequency ratio.

Time to write some code, I guess.

I'm alive

2007-11-12T01:50:00.000+13:00

Went down to Dunedin for a couple of weeks to find something to do for a couple of years. Now that's ROI.

My Mac's at the shop with a fried graphics chip. If the fault's of a certain nature, they'll replace the board free (out of warranty). Otherwise it's written off, and I (have|get) to buy a new one. I'm really hoping something, but I'm not sure what.

In related news, linux+ubuntu runs really nicely on my four-year-old laptop - the same one that took weeks of enthusiastic tinkering when it was new. I guess they mature with age, like a fine wine, and long walks along the beach.

I have it on good authority that it's not the internet without multimedia and hyperlinks.

Pachelbel Rant - Rob Paravonian

a softer world - surreal webcomics, via Tim

Oh yeah, and i++ == 21. I sound less wrinkly that way.

Not a tree

2007-09-26T18:30:00.000+12:00

The money's in the marketing

2007-08-31T01:58:00.000+12:00

Often you'll see a book mentioned on a website with a link to buy it on Amazon.com. The website owner has an account with Amazon and gets a commission when someone uses the link to buy the book.

A bit of perspective I found shocking - the website owner earns as much as the author of the book.

Source

Sufficiently advanced technology

2007-08-25T17:01:00.000+12:00

I can't decide if it's magic or a rigged demo, but certainly the coolest thing I've seen in a while - a way to resize images without cropping or distorting the important details, by changing the amount of background. He even explains how it works.

Content-Aware Image Sizing on YouTube, if you can't see it below.

They don't make nostalgia like they used to

2007-08-16T20:39:00.000+12:00

Was digging through an old server looking for something, and ran into a weird array of stuff

Silly flash games
Silly first year compsci assignments, from when I believed in doing assignments properly (and they were games)
Silly second year compsci assignments from when I believed in doing assignments at all
My very own Robot Finds Kitten in an exciting new language called C#
A video of a perfect zero in Truck Dismount

But the weirdest thing, that I don't remember a word of, but must have written because google's never heard of it:

I am the very model of a mildly tricky integral
So easy to approximate on any given interval
But general solutions need a stroke of ingenuity
To find a strategem which rectifies discontinuity.
You'll try the things you learned in class but never gain much traction
With your clever substitutions and techniques of partial fractions
In short, your simple methods fail against one so formidable,
I am the very model of a fairly tricky integral.

Combining basic processes in any way conceivable
Still fails to make the answer appear any more achievable
Rewriting points in polar form pre-partial integration
Does not subtract, but adds, to the solution's complication.
There seems to be no way to find a formula constructively
And thus no proposition one can try to prove deductively
The Riemann sum's don't simplify when working from first principles
I am the very model of a rather tricky integral.

I stood almost unchallenged for the best part of a century
And people wondered if my answer's even elementary
Professors thought they'd solved me and they harboured animosity
When refutations flooded in with frightening ferocity.
And then one day a student who, for rhyme's sake, will be Asian
Was trying hard to visualise the shape of my equation
The integrand examined, the identity, though difficult,
Did give the model answer for the very tricky integral.

(So while it seems that "reader's exercises" should be trivial,
Sometimes it's just a reason not to solve some tricky integral)

iPhone has performed an illegal operation and will be shut down

2007-08-06T22:29:00.000+12:00

Oops.

xkcd

2007-08-03T00:33:00.000+12:00

You know when you see an unfamiliar word in an essay or such, and you look it up, and all of a sudden it's everywhere? It's clearly not a new word and maybe everyone was using it before without you noticing, but it still seems to have turned up overnight. It's essay molasses I guess.
Anyway, the word of the week is xkcd.

Wikipedian Protester

Maybe I read too much wikipedia.

edit hahahhahahahahahahhahaha

Telephone trouble

2007-08-01T00:15:00.000+12:00

It seems that every Monday morning when I get into the office — not on time as such, but 'morning' is usually accurate — there's already an email saying they're having some problem or other with the phone system. A weird but harmless error message, calls randomly connecting to the wrong phone, bizarre error messages, whatever.

Backhanded compliment though, I bet even Simon doesn't have a weekly inaccessible telephone number!

Facebook

2007-08-01T00:00:00.000+12:00

Yeah, you got me. I signed up for the thing. I posted an impassioned disclaimer-rant about how Facebook struck me as potentially flaky and devoid of content. I came back ten minutes later and edited it to complain about the markup mangling, and went to bed.

Today it's gone.

I can't write coherently at the best of times, and I'm out of practice, so it's no great loss to the world. Flaky isn't the word though. I tried to post a note mentioning it (not a fast learner, you see) and among other error messages:

You have not written any notes.
Displaying the only note by you. (followed by a blank space)
Write a New Note → Your friends have not written any notes yet.

Accompanied by a handy tip: You can write your own or find more friends. Ouch.

I haven't played with the other standard apps yet, are they any better?

edit And it's back again. I think I've learned my lesson though.