Faster median calculation and generic rank selections in MatLab via nth_element

Update (2011-09-03): I've added new functions to the release that edit the arrays in-place. This is not good Matlab style but gives significant speedups for the very performance conscious. It appears it may be useful for me to add a multithreaded version as well, so this may come in an upcoming release.

C++ std::nth_element is a standard specification for an efficient rank selection algorithm. This algorithm can be used to solve a number of rank selection problems efficiently.

One example is median finding. A naive median finding algorithm, as implemented in MatLab (at least up to R2010a) is to sort the entire list of values and then just take the value in the middle position. But sorting the entire list is overkill; it is more efficient to do a sort of partial sort just to the point where the desired value is in the correct position. The version of this typically implemented in nth_element is known as quickselect or Hoare's Selection Algorithm. See Wikipedia: Selection algorithm for more details.

I find that a MatLab fast_median function based on nth_element runs about twice as fast as the native MatLab median function based on sort. Theoretically, the average complexity of quickselect is O(n), while the best performance complexity of the sort based method is O(n log n).

Finding median values is central to robust statistics, for example calculating the Median Absolute Deviation.

If you are interested, my MatLab wrapping of nth_element and an example implementation of fast_median are available at MatLab Central File Exchange.

Startup GNU Screen with multiple regions (split screen)

Since I've been doing a lot of work remotely lately I've been brushing up my GNU Screen skillz.

One thing I'd like is to be able to reattach a screen with a number of regions (AKA split screens) setup automatically. Screen is supposed to get this in the next release, but it's been a while.

In the meantime, the following kludge seems to work well enough: (sleep 0.1; screen -X split) & screen -r. Basically, this says: "reattach to my screen and at the same time in the background wait a fraction of a second and then send the split command to screen from a separate thread".

This was a common enough pattern that I wrote it into a little shell script:

#!/bin/sh

splits=$1
if [ -z $splits ] ; then
  splits=1
fi

sleep=$2
if [ -z $sleep ] ; then
  sleep=0.1
fi

sleep $sleep
i=0
while [ $i -lt $splits ] ; do
  screen -X split
  screen -X focus bottom
  screen -X select `expr $i + 1`
  i=`expr $i + 1`
done

which is used: splitscreen 4 & screen -r.

There's plenty of room for improvement. A more principled replacement for the call to sleep would be to monitor the socket files. In my Mac OS 10.5 these are under /tmp/uscreens/.... (I believe the standard location is /usr/tmp/screens/...) This is purely empirical, but it appears the user permission on the socket file changes from -x to +x (i.e. becomes executable) when the screen is attached. So instead of sleep we should be able to do a wait until that permission change occurs.

In principle I think this could even be used to save and restore region settings. For example, rebind the split key to not only split but also save a flag to filesystem indicating how many regions, then read this flag when reattaching. Or we could just wait for the next release...

Bluegiga WT12 Breakout Board V0.2

I just got my first ever printed circuit boards back from BatchPCB. Pretty exciting! One of the boards is a Toyota audio system interface, but it needs to have a chip replaced and the pinout is different, so that board is not totally usable. The other board is this breakout board for the Bluegiga WT12 bluetooth module.

This breaks out all the pins so you have complete freedom, and it's still pretty small. I have another version I will probably release that breaks out only the UART pins and is compatible with the BlueSmirf pinout. That one is much smaller.

The WT12 has iWrap4 firmware that is a very simple interface to a variety of common Bluetooth profiles. It's quite affordable; please see my Flickr page and BatchPCB page for more information and ordering.

Chords: "Holiday" by the Kinks

The chords posted around online are a bit wrong. And it's such a great, simple song! Fixed it up a little:

Artist-The Kinks
Song-Holiday
Album-Muswell Hillbillies
Writer-Ray Davies
Tabbed by S. McNally, Peter H. Li


Intro
A-F#-B7-E7


Verse 1
A     F#     B7
Holiday,
          E7     A     F#
Oh what a lovely day today,
B7        E7        A       F#
I'm oh so glad they sent me away,
   B7            E7   A    F#   Bm Eb E
To have a little holiday today, holiday.

Verse 2
A     F#
Holiday,
B7           E7              A        F#  
And I'm just standing on the end of a pier,
B7          E7      A        F#
Hoping and dreaming you were here,
B7          E7     A            (turnaround: A F E C A ???)
To share my little holiday.


Verse 3 (type II)
A              F#        B7         E7
Lookin' in the sky for a gap in the clouds,
A           F#                   B7           E7
Sometimes I think that sun ain't never coming out,
        A         A7/G              D          B7
But I'd rather be here than in that dirty old town,
  E                                             (E+)
I had to leave the city cos it really brought me down.


Verse 4
Oh holiday, oh what a lovely day today,
I think I'll get down on my little ol' knees and pray, thank you Lord,
Thank heaven for this holiday today, holiday.


Bridge
    D           B7       A
I'm leaving insecurity behind me,
    D             B7               A
The environmental pressures got me down,
C#              C#7          D       B7
I don't need no sedatives to pull me round,
E                                              (E+)
I don't need no sleeping pills to help me sleep sound.


Verse 5
Oh holiday,
Oh what a lovely day today,
I think I'll get down on my little ol' knees and pray,
That's what I'll do,
Thank heaven for this holiday.

Verse 6 (type II)
Lying on the beach with my back burned rare,
The salt gets in my blisters and the sand gets in my hair,
And the sea's an open sewer,
But I really couldn't care,
I'm breathing through my mouth so I don't have to sniff the air.

Verse 7
Oh holiday,
Oh what a lovely day today,
I'm so glad they sent me away,
To have a little holiday. 

(I sure miss OLGA sometimes...)

Globus Toolkit 5.0.2 on Cygwin 1.7

Updates (2011-02-20): Cygwin patches did not make it into GT5.0.3, but they may make it into a future release.

Updates (2010-12-08): Binghamton University TeraGrid has written up instructions for applying the patches and getting GT compiled. Also, it appears new versions of GT will be coming out over the next few months. I plan to check them out for Cygwin compatibility.

If you are interested in compiling Globus Toolkit 5.0.2 on Cygwin, I have some simple patches that seem to get the job done. Perhaps they will make it into the next release. For now: http://lists.globus.org/pipermail/gt-dev/2010-September/001885.html

Note that I built this on Cygwin 1.7; Cygwin 1.5 will probably not work. Also you must have the gcc4.x Cygwin packages (C and C++) installed. Getting GT to build on gcc3.x is probably not much more work, but going with gcc4 is easier than worrying about unrecognized compiler flags all over the place.

You also need to specify the flag: --with-buildopts="-static=1" when running the main configure script. Building GT on Cygwin with dynamic linking is certainly beyond me, and is a pretty big undertaking, so this tells it to use only static linking. I recommend --with-buildopts="-verbose -static=1" so you can also see what is going on.

(For the record, on dynamic linking: I tried adding some flags to configure.ac or configure.in to let autoconf know that we wanted to make DLLs and do dynamic linking. But trying to run a modern version of autoreconf generated configure scripts that don't work with the GT package. Even if the build worked, this probably wouldn't be a good idea as making DLLs properly requires going through all the source and making sure data exports are handled correctly. At least one package (globus_libtool) is DLL ready and already generates a DLL and RTL properly, so we know it all works theoretically once the individual libraries are DLL ready. There may be other subpackages that are DLL ready, but they will probably have to be handled one at a time. Unfortunately, GPT doesn't really offer a method to build the whole Globus Toolkit with some parts statically linked and some dynamic.)

If you get a build failure with an error like "fork()" or "vfork()" "resource temporarily unavailable", this means your machine ran out of processes while building (due to what I'm going to call a "process leak" bug). Basically just rerun make and it should get farther each time before crashing, until finally it gets all the way through. Or build GT in smaller chunks; if you are just trying to get proxy certificate running you only really need "make gsi-myproxy gsi-openssh".

You may also have to circumvent GPT's somewhat outdated Perl libraries. If you have a problem getting Archive::Tar to open some of the source packages, then you should install the Cygwin CPAN package and then use that to install an updated version of Archive::Tar. You may then need to hide GPT's versions under $GLOBUS_LOCATION/sbin/perl.

Feel free to ping me with any questions/thoughts.

Eclipse Windows 7 Plugin Problems

Wow, Eclipse is really a piece of work. I wasted an hour trying to get it to behave reasonably with multiple plugins installed on Windows 7. Online forums were little help until I finally came across the suggestion to install Eclipse into a user directory, i.e. one that doesn't require administrator privileges. Finally fixed; what a waste of time!

Compiling GnuCAP in CygWin

Update: GnuCAP is now available as an official CygWin package, as is some dialect of SPICE.

Very simple patch to get recent development snapshots of GnuCAP to compile in CygWin:

--- md.h.bak    2010-03-19 00:21:26.030900000 -0700
+++ md.h        2010-03-19 00:34:18.810900000 -0700
@@ -100,6 +100,12 @@
  #define MS_DLL
#endif
/*--------------------------------------------------------------------------*/
+#ifdef __CYGWIN__
+  #ifndef RTLD_LOCAL
+    #define RTLD_LOCAL 0
+  #endif
+#endif
+/*--------------------------------------------------------------------------*/
/* some convenient names */
typedef std::complex COMPLEX;
typedef std::pair DPAIR; 

Mac-style wheel zoom, Exposé/Switcher on Windows 7

Having a Mac at work has been a mixed blessing, mostly good. There are some great OS features that I've become addicted to. Happily, I have discovered ways to duplicate them on my Windows 7 home machine, and with better customizability even.

Wheel zoom

On Mac OS, holding command and using the mouse wheel zooms you in and out of your screen view. This is on the operating system level, so it works in any application. Windows 7 has a similar (i.e. copied) feature where holding the windows key and pushing plus/minus zooms. Obviously it's nicer to use the mouse wheel. Luckily, with AutoHotKey it's easy to set this up on Windows and even make it better.

After installing AutoHotKey, run the following script:

; Only one instance running at a time
#SingleInstance force


; Mac-like zooming
~LCtrl & WheelUp::
  sendinput #{NumpadAdd}
return

~LCtrl & WheelDown::
  sendinput #-
return

~LWin & WheelUp::
  sendinput #{NumpadAdd}
return

~LWin & WheelDown::
  sendinput #-
return 

I derived this from AeroZoom by wandersick, which is an excellent set of shortcuts for presentations. I pulled out just the very simple zooming functionality and made it duplicate the Mac functionality more. Thanks to wandersick for putting his tool out with the source!

My mouse has side buttons that I usually use just for forward/back. I added the following so that now I can do the wheel zoom without the keyboard at all, just by holding the left side button and wheeling:

; Additional mouse-only zooming
~XButton1 & WheelUp::
  sendinput #{NumpadAdd}
return

~XButton1 & WheelDown::
  sendinput #-
return 

Exposé/Switcher

Exposé is the Mac OS feature that makes it easy to find windows when you have a thousand different things open at once. There is a very similar application for Windows called Switcher. I like having Mac OS setup so that when you push the middle button (the wheel) it calls up Exposé. With AutoHotKey, of course, it was simple to set up identical functionality on Windows 7 via Switcher.

On my home mouse, I find it easier to push both side buttons simultaneously than to push the wheel down, so I set it up that way. I also had trouble getting this to work with Switcher's default activation button (windows-`), so I added an additional Switcher hotkey (Switcher is very nicely customizable too) and then just setup AutoHotKey to trigger that:

; Mac-like expose, hooking into switcher
~XButton1 & XButton2::
  send #s
return

Hope that helps some other people suffering from Mac lust. Enjoy!

Cloud patterns from space

WiReD has a cool gallery of satellite cloud photos.

Mourning dove feeding

Finally got around to posting a video of the mourning doves that lived in our tomato plant last summer. I was working from home at the time, and this was the window right next to my desk, so I have a lot of videos and photos, but this is one of the more interesting ones: feeding time!