Fractal Friday: Another Fractal Pizza

Here’s a pizza modeled after a variant of the Koch snowflake, and it’s perhaps a bit more aesthetically appealing than the previously posted pie.  Sadly, an examination of the pepperoni distribution (not to mention the ever-so-cute tiny pepperoni themselves) will reveal that this is a ‘Shop job, so it seems that the three-recursion/edibility barrier has not yet been broken.  Even were it to be real, you’ll notice that the fourth and fifth levels are incomplete, so we’d have to count it out in any case. [Edit: miscounted due to tiny WordPress editing window; there are four legitimate (if PhotoShopped) fully complete levels.)

(Via proofmathisbeautiful.)

Linux and Sundry

An Emacs Bisection

cricket on a screenA problem has been following me around for a couple of years.  Emacs, in which I have been spending more than a small portion of my time, has had a problem that would manifest in any non-X mode.  It persisted across multiple terminals: putty on Windows back to a Linux box, emacs -nw in a GNOME Terminal , even a bog-standard Linux console.  Specifically, hitting ‘Page Up’ and would result in the string ‘5~‘ being printed and ‘Page Down’ would result in '6~‘.  Not deadly, but just enough to throw me off my stride when moving around files.  I’d never gotten around to sorting in out, since it worked just fine when running as an X server.

This came up after the PLUG meeting last night, over pizza and beer at the Best House last night.  As Walt pointed out, there was almost certainly a very good reason for this, and it would be living somewhere in the years of messy accretions that comprise my .emacs file and its satellites.

I knew this was probably the case.  Like most .emacs files, mine was not planned.  It grew from bits and useful snippets, mode hooks, random configurations, pieces that crept in as distribution cruft, and pastings of now-unknown provenance.  The whole morass needs a good mucking out, but that’s not on the to-do list.  Perhaps, though, I could finally get the nagging problem resolved.

The first test was an obvious one: remove all the startup files and see if the problem went away.

Now, at some point I acquired a set of XEmacs startup files.  The reason for this is hazy…I haven’t used XEmacs in years.  Nonetheless, there it is: an .xemacs folder with an init.el and custom.el.  At some point, something broke when I tried to take my .emacs file and .emacs.d folder without bringing .xemacs along for the ride, so the path of least resistance was to let it follow me from machine to machine ever since.

After renaming all the startup files, the problem was indeed gone and I could happily page up and down.  From there on, the process is a mechanical one: add files back in until it fails, then comment everything out in the file and add chunks back in until the problem returns.  Once it does, you can be pretty sure you’ve isolated the problem.

Indeed, the problem was lurking in .xemacs/init.el, in the following pair of lines:

(global-set-key "e[" 'enlarge-window)
(global-set-key "e]" 'shrink-window)

It seems to me like a slightly odd manifestion, but there you have it.  With those lines removed, my Emacs bliss is unimpeded.

I really ought to get around to getting rid of that XEmacs cruft.

(CC-licensed image of a cricket from TaranRampersad‘s flickr photostream.)

Planet PLUG Programming

Extract n largest values from a Python dict

Having stashed a bunch of data in a python dict, one often needs a quick way to extract the n largest.  Inconveniently for the particular problem I was working on, the key value for the dict was an object and the associated value was a floating-point weight.  A quick-and-dirty method is to use insert all the dict-keys into a heap, using the dict-value as the heap-key Fortuitously, Python has both a heap module and convenient functions for using it in exactly this way.

import heapq

def dict_nlargest(d,n):
    return heapq.nlargest(n ,d, key = lambda k: d[k])

d = { 'a':10.0, 'b':2.0, 'c':5.0, 'd':3.0, 'e':15.0 }
print dict_nlargest(d,3)

Which neatly prints a list of the keys associated with the three largest values:

['e', 'a', 'c']

The heapq.nlargest() function can also use arbitrary object attributes as keys, as well, by supplying a one-argument function to the named parameter key. (This is the role of the lambda in the examples above and below.)

import heapq
class Toy:
    def __init__Toy(self, s, i, f):
        self.s = s
        self.i = i
        self.f = f

l = [ Toy('a', 10, 4.4), Toy('b', 4, 12.0),
      Toy('c', 2, 20.0), Toy('d', 1, 5.0) ]

# largest by the 'f' attribute
print heapq.nlargest(2, l, key = lambda o: o.f)

# largest by the 'i' attribute
print heapq.nlargest(2, l, key = lambda o: o.i)

This is fine for a one-off, but you’ll likely want to maintain this information in a data structure if this you’ll be performing this operation multiple times on a large collection.


Natural Selection for Self-Optimizing Haskell Code

I’ve been playing around with Haskell, Clojure, Scala and Mercury recently, and even though Clojure seems to be winning my heart, I’ve found much to admire about each language.  Haskell and Mercury, in particular, are nicely brain-twisty.

The recent release of a new backend for GHC that can generate code for LLVM is quite exciting.  Even more interesting is this blog post by Don Stewart (co-author of Real World Haskell) exploring genetic algorithms (via the Acovea toolkit) to select sets of LLVM compiler optimizations.  The process isn’t fast (Acovea chews on the options for four hours), but the improvements for even these preliminary explorations are striking.  This approach is worth watching; there is a lot of performance waiting to be squeezed out of modern processors, and it’s even better if we can design approaches that allows automatic optimization for each platform. (Don suggests that he’s working on a wrapper library to allow you to simply issue a main = evolve main' and let it go.)

Natural Computation Self-Organization

Computation with slime mold

Here’s some natural computation at the University of Oxford: using slime mold for efficient network planning.  They selected a somewhat interesting test for efficiency, comparing the patterns of slime-mold tubes to the design of the Tokyo subway system.

The researchers distributed oat flakes in a pattern similar to the locations of major cities and turned the Physarum polycephalum loose in, as it were, downtown Tokyo.  As the slime mold established its transport system, the resulting networks closely resembled design of the real-world human-engineered railways.

From their experiments, the researchers have developed a self-organizing mathematical model and simulation that I’d like to look at more closely.

The full text of the article “Rules for Biologically Inspired Adaptive Network Design” by  Tero, et al. is, alas, behind a paywall, as is too much current research, though Science (the journal where it was published) does have a popular take , as do Wired and BoingBoing.

Photo credit: Science/AAAS