Back To The Code

How do you do that again?

Some C# Features for Java

Programming in different languages is both great and frustrating. Frustrating because you want to be able to use feature X of a language in another language, but the language you’re using doesn’t support that feature. This is very true for anyone that has used a somewhat more functional or dynamic language and then started (or went back to) programming in a language like Java. One of the key philosophies of the Java language is to keep things simple. I appreciate this philosophy, and in fact feel that perhaps adhering to OO-programming has made things more complex than what they need to be. This is one of the reasons I started playing around with Clojure – a simple and flexible language that allows you to be very productive. But, It’s not easy to switch and start thinking in terms of verbs instead of nouns.

I digress.

Most of the features that I look for are implemented in C# and since it bares close resemblance to Java, I attempted to implement some of those features:

  • coalesce operator ??
  • TryParse methods
  • IsNullOrEmpty test for strings
  • Loan pattern implementation with using
  • a subset of LINQ for objects

TryParse isn’t really what I had hoped since one cannot use references for numbers, not even when they are boxed. All these methods are implemented as static methods:

coalesce(null, objectThatIsNull, someObject)
>> someObject

tryParseInt("10")
>> 10

tryParseInt("g")
>> null

isNullOrEmpty(null)
isNullOrEmpty("")
>> true 

// closes the OutputStream automatically, calls
// close on any class that implements Closeable
tryWith(new OutputStream(), /* some function here */)

LINQ-ish

I focused on a subset of the LINQ implementation, only implementing operations that seemed fundamental, plus some more that were easy to write. The underlying code uses Iterable interface, we don’t hold any collections and values are only generated when we traverse the items.

Generators

Methods that produce an iterable such as range(start, end, step) as well as repeat(item, repetitions).

List expecteds = new ArrayList();
expecteds.add(5);
expecteds.add(9);
expecteds.add(13);
expecteds.add(17);
expecteds.add(21);
expecteds.add(25);
expecteds.add(29);

Iterators.rangeInt(5, 30, 4)
    .zip(expecteds)
    .each(new Proc1<Tuple2>() {
        @Override
        public void apply(Tuple2 arg) {
            Assert.assertEquals(arg.getItem1(), arg.getItem2());
        }
    });

all and any

Do any or all items in the list satisfy a certain predicate.

Collection strings = new LinkedList();
strings.add("a");
strings.add("a");
strings.add("a");

boolean expected = true;

boolean actual = from(strings).all(new Func1() {
    @Override
    public Boolean apply(String arg) {
        return arg.equals("a");
    }
});

Assert.assertEquals(expected, actual);

map, reduce and filter

These operations give you the basic toolkit for data manipulation. Note that you can pass up to four functions into map to produce a list of tuples. Filter, in theory, can be implemented using the reduce operation but I chose to make it independent of reduce.

List strings = new LinkedList();
strings.add("a");
strings.add("a");
strings.add("b");
strings.add("a");
strings.add("a");

int total = from(strings)
		.map(new Func1() {
			@Override
			public Integer apply(String arg) {
				return arg.hashCode();
			}
		},
		new Func1() {
			@Override
			public String apply(String arg) {
				return arg.toUpperCase();
			}
		})
		.filter(new Func1<Tuple2, Boolean>() {
			@Override
			public Boolean apply(Tuple2 arg) {
				return arg.getItem1 == 97;
			}
		})
		.reduce(0, Functions.sumInt());

take and drop

Take (use) the first x items, drop (ignore) the first x items.

final Integer expected[] = {30, 31, 32};

Iterators.rangeInt(30, 100).take(3).each(new Proc1() {
    int count = 0;
    @Override
    public void apply(Integer arg) {
        Assert.assertEquals(expected[count++], arg);
    }
});

wrap

This one is a bit special and is inspired something I found in Clojure. It wraps an already existing list so that the list repeats itself to infinity – 1, 2, 3 becomes 1, 2, 3, 1, 2, 3, 1, 2, 3, …

String expected = "a/b/c/a/b/c/a/b/c/a";
String actual = from("a", "b", "c")
                    .wrap()
                    .take(10)
                    .reduce("", Functions.join("/"));

Assert.assertEquals(expected, actual);

I’ve implemented more methods that I didn’t discuss here such as sort and zip. The source code can be found here on GitHub. All this would be so much nicer with lambda expressions ūüė•

MySQLdb for Python on Mac OS X Snow Leopard

Short step-by-step guide to installing the python MySQL connector. Previously, one had to edit the source files to be able to compile the connector on OS X, this is no longer necessary. Just follow the steps below and hopefully everything works as it should.

Download the package from Sourceforge (currently 1.2.3 is the most recent version):
http://sourceforge.net/projects/mysql-python/files/mysql-python/

Extract the tar.gz file. In a terminal, write:
$> tar xzvf MySQL-python-1.2.3.tar.gz

Add the directory containing mysql_config to your path:
$> export PATH=$PATH:{path_to_mysql/bin}

Go to the new directory and run the following commands:

$> sudo python setup.py clean
$> sudo python setup.py build
$> sudo python setup.py install
$> sudo ln -s /usr/local/mysql/lib/libmysqlclient.18.dylib /usr/lib/libmysqlclient.18.dylib
$> sudo ln -s /usr/local/mysql/lib/ /usr/local/mysql/lib/mysql

Check if you can import MySQLdb in python:

$> python
>>> import MySQLdb

How to create strong memorable unique passwords

I recently decided to change all my passwords in order to make them easier to remember and stronger. One would think that making a password stronger would mean that it becomes less memorable – not if you use a method and thus only need to remember the method for creating the password instead of the actual password.

Most sites have some requirements on password complexity such as:

  • length has to be 8 or more characters
  • must have at least 2 numeric characters
  • must have at least 2 non-alphanumeric characters, e.g., $
  • must not be a word or name

Methods

Memorizing finger movements. One method for creating such a password is memorizing finger movements like zig-zag qwerty using shift in some places which could result in the following password <1q@w#e4r>. A drawback with this method is that if you need to use a keyboard with a different layout, it will become nigh impossible to enter the password. Since I travel a lot and spend some time in internet cafes, this method is a no-no for me.

Replacing letters with numbers. Take a word or a name and replace the letters with numbers, this means that your moms name <Barbara> becomes <84r84r4> and we throw in a few non-alphanumeric characters to seal the deal <@84r84r4#> and we have a strong password. As long as we use non-alphanumeric characters as well, this is actually a pretty good method. Using only the letter -> number replacement is too weak.

Ensuring uniqueness

The above methods are pretty great but do not result in a unique password. A safe password should be unique so that if one of your passwords leak, other services that you use are still safe. One way is to mix in the name of the service that you use into the password. Time for an example:

  1. I have to choose a password for my picasa account
  2. I choose <Samoa> as my base password in my mind
  3. I apply letters to numbers method and get <54m04>
  4. throw in a @ and # and finally get <@54m04#>
  5. I want unique passwords, so now I will mix in ‘picasa’ into my password
  6. the final password is <@54m04#p1c454>
  7. done

Now we have a strong unique password that is easy to remember.

Scala: Hello Memo Fibonacci

The previous Fibonacci program works, to a certain degree. We’re doing a lot of repetitive computation that we could avoid by storing results as they become available. So the second time we need the result, we just do a look-up and retrieve the previously calculated result. This technique is called memoization and can be applied to pretty much any function that is deterministic, i.e., for input x, the function will always return y.

Ideas and examples are based on the blog post found here on memoization: http://michid.wordpress.com/2009/02/23/function_mem/

Ideally, we would like to be able to apply a memoization function that will return a function that uses memoization. We define our function f(x) = y that does all the work. Now we want a function f'(x) = y that stores results for f(x) and returns the result from a look-up table.

f'(x) = Memoize(f)

Example function f(x) that does some computation of complexity O(n!) we can say that:

  • f(x) has O(n!) complexity always!
  • f'(x) has O(n!) complexity only the first time it is invoked and O(1) complexity after the first invocation.

Memoizing is nothing more than caching the result from a previous computation for instant look-up. Implementations usually look like a key-value store such as a Map.

class Memoize1[-T, +R](f: T => R) extends (T => R) {

  private[this] val memorized = scala.collection.mutable.Map.empty[T, R]

  def apply(x: T): R = {
    memorized.getOrElseUpdate(x, f(x))
  }
}
object Memoize1 {

  def apply[T, R](f: T => R) = new Memoize1(f)

  def Y[T, R](f: (T => R) => T => R): (T => R) = {
    lazy val yf: T => R = Memoize1(f(yf)(_))
    yf
  }
}

Scala is amazing! It allows us to pass a function to getOrElseUpdate in case the value hasn’t already been evaluated. So f(x) is only evaluated iff the key x is not available. Note we call this a Memoize1 class since it extends Function1, i.e., a function that takes 1 argument.

What About Recursive Functions

When we try to apply Memoize to a recursive function, we have a problem since we call the function from within the function itself. The recursive function calls use the original function (f), not the memoized function (f‘). Using the fib function from the previous post:

def fib(n: Long): Long = n match {
  case 0 | 1 => 1
  case _     => fib(n - 2) + fib(n - 1)
}
val fibMem = Memoize1(fib)

Problem here, the internal recursive functions do not call fibMem, but the original fib function. There is no elegant way to fix this, all we can do is change the Fibonacci function fib to take a new parameter where we can tell it what function to use for the recursive calls. This can be achieved by currying fib to return a new function using the memoized fib functions.

def fibCurry(f: Long => Long)(n: Long): Long = n match {
  case 0 | 1 => 1
  case _     => f(n - 2) + f(n - 1)
}
lazy val fibMem = Memoize1(fibCurry(fibMem)(_))

Lazy is required to defer evaluation of fibMem. The recursive calls f are now using the memoized version fibMem.

All Together

Here’s the source code to play around with together with some comments to explain things that I didn’t think were very clear. I noticed that the memoized version becomes superior at around n = 34 mark beating the original fib function by a few milliseconds.

/**
  * Based on http://michid.wordpress.com/2009/02/23/function_mem/
  */
object FibApp extends App {

  /**
   * Basic fibonacci number generator
   *
   * @param n index of fibonacci number
   * @return the fibonacci number
   */
  def fib(n: Long): Long = n match {
    case 0 | 1 => 1
    case _     => fib(n - 2) + fib(n - 1)
  }

  /**
   * Fibonacci number generator that takes a recursive function as
   * an argument and returns a fibonacci function
   *
   * @param f function used for recursion
   * @param n index of fibonacci number
   * @return the fibonacci number
   */
  def fibCurry(f: Long => Long)(n: Long): Long = n match {
    case 0 | 1 => 1
    case _     => f(n - 1) + f(n - 2)
  }

  /**
   * This piece of code seems a bit strange, sometimes get negative times
   *
   * @param code code to execute
   * @return result from calling code
   */
  def time[T](code: => T) = {
    val tic = System.nanoTime
    val result = code
    val toc = System.nanoTime

    println("Time: " + ((toc - tic).doubleValue / 1e6) + "ms")
    result
  }

  /**
   * class extends Function1, written as (T => R)
   * e.g., f(x) = y where x is in subset of T and y in superset of R
   *
   * @link http://www.hars.de/2009/10/variance-with-horses-and-people.html
   * @link http://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science)
   *
   * @param f Function1 function
   */
  class Memoize1[-T, +R](f: T => R) extends (T => R) {

    private[this] val memorized = scala.collection.mutable.Map.empty[T, R]

    // function apply is automatically called when using operator ()
    def apply(x: T): R = {
      memorized.getOrElseUpdate(x, f(x))
    }
  }

  /**
   * declare object (singleton) Memoize1, like a Memoize1 factory
   */
  object Memoize1 {

    /**
     * apply is used when we write Memoize1(f), same as Memoize1.apply(f)
     */
    def apply[T, R](f: T => R) = new Memoize1(f)

    def Y[T, R](f: (T => R) => T => R): (T => R) = {
      lazy val yf: T => R = Memoize1(f(yf)(_))
      yf
    }
  }

  val fibMem = Memoize1.Y(fibCurry)
  val max = 34

  time(println(fibMem(max)))
  println("--------------")
  time(println(fib(max)))
}

Note that I switched the recursive calls to start with f(n – 1) instead of f(n – 2). This is so that we directly memoize all results, in place of stepping by two which is what we do with f(n – 2).

Scala: Hello Fibonacci

Let’s start with some easy Scala coding, like generating the Fibonacci sequence. A nice problem because it uses recursion and we can expand upon the solution by creating a memoizer to save the intermediate results for when we need them again.

Fibonacci sequence: 1, 1, 2, 3, 5, … , f(n) = f(n-2) + f(n-1)

This gives us the following first 3 terms

  1. f(0) = 1
  2. f(1) = 1
  3. f(2) = 2

The third term can be written in the following way

f(2) = f(0) + f(1) = 1 + 1 = 2

Using the same premise, we can write the fourth term as

f(3) = f(1) + f(2)
f(3) = f(1) + (f(0) + f(1)) = 1 + 1 + 1 = 3

So the base terms are f(0) = 1 and f(1) = 1 and the recursive term is f(n) = f(n-2) + f(n-1). In Scala, this is

def fib(n: Long): Long = n match {
  case 0 | 1 => 1
  case _     => fib(n - 2) + fib(n - 1)
}

To run this as a stand alone program, write

object FibApp {

  def fib(n: Long): Long = n match {
    case 0 | 1 => 1
    case _     => fib(n - 2) + fib(n - 1)
  }

  def main(args: Array[String]) {
    println(fib(30))
  }
}

You’ll notice that the results for n < 40 take a “reasonable” time to compute, whereas results for n > 40 take a long time or even result in a stack overflow. We can use memoization to store the result of the previous calculations, this should decrease the amount of time required for generating results for larger values of n.

Getting started with Scala

A while ago, I started playing around with Scala. To make things as easy as possible for me to write Scala code, I wanted to found out which IDE had the best support. The easiest to install was the Eclipse Scala plugin. All you need to begin writing Scala code is a JDK, Eclipse and the plugin URL. IntelliJ has a good plugin too, the installation requires one extra step where you have to install the Scala system before downloading the plugin.

Eclipse Scala Plugin

  1. Install a JDK – assume you’ve already done this, otherwise google “JDK” and download the latest version from Oracle.
  2. Install Eclipse Рgo to http://www.eclipse.org/downloads/ and download the most appropriate version for you.
  3. Copy the plugin URL from http://www.scala-ide.org/ by clicking on the button that looks like the one below
    Plugin URL button
  4. Open Eclipse, go to Help > Install New Software…¬†and paste the URL into the address field (the one that says Work with:)
  5. Download the plugin and restart Eclipse.
  6. IMPORTANT: Now, start a Scala project. Once the project is set up, go to Scala > Run Setup Diagnostics… and make sure to check the field “Use Scala-compatible JDT content assist proposals”
  7. Done.

If you don’t do step 6, you will not get any suggestions when writing code, so make sure that you have completed step 6 before deciding not to continue with Eclipse.

IntelliJ Scala Plugin

  1. Make sure you have a JDK as in step 1 above for Eclipse.
  2. Install IntelliJ Рthe community edition is available for free and allows you to write Scala code. Go to http://www.jetbrains.com/idea/download 
  3. Download the Scala IzPack Installer from http://www.scala-lang.org/downloads and run the package.
  4. Start intelliJ and click on Open Plugin Manager (top of right column that has the title “Plugins”)
  5. Click on the “Available” tab and look for Scala. Right click on the plugin and choose to install it.
  6. Done.

Fun with Generics and Java Concurrency

I had previously worked with C#’s asynchronous framework and wanted to play around with Java’s concurrency framework to see how similar they are. This is just a small program that is supposed to be fun and nothing to do with coding effectively. I also threw in some overkill code to sum the items of an array – a reduce operation using generics.

The program blurs an image by calculating the average colour values of neighbouring pixels. One can apply a colour bias to “prefer” certain colours or colour combinations. A blur operation is inherently parallel, i.e., we have no dependencies between the results of the blur – all work is performed using the original image as the input. This makes it quite easy to split the work across different threads. Optimally, one chooses as many threads as one has cores.

Here is the Java code (again, this is just for fun, not best practice)

import <...>

public class SandboxOne {

    static private int numActiveThreads;
    static private long tic;
    static private ExecutorService threadPool;

    public interface AsyncCallback<T> {
        void call(T data);
    }

    public interface Reducer<S,T> {
        T reduce(S current, T result);
    }

    public static class Algorithms {

        public static <S,T> T reduce(Collection<S> items, Reducer<S,T> reducer, T initial) {

            for (S item : items) {
                initial = reducer.reduce(item, initial);
            }
            return initial;
        }
    }

    private static class BlurImage implements Callable<Object> {

        private final int start;
        private final int step;
        private final AsyncCallback callback;
        private final BufferedImage original;
        private final BufferedImage processed;

        private final Reducer<Integer, Integer> sumIntegers = new Reducer<Integer, Integer>() {
            public Integer reduce(Integer current, Integer result) {
                return result + current;
            }
        };

        public BlurImage(BufferedImage original, BufferedImage processed, int start, int step, AsyncCallback<BufferedImage> callback) {
            this.original = original;
            this.processed = processed;
            this.start = start;
            this.step = step;
            this.callback = callback;
        }

        public Object call() {

            int imageWidth  = original.getWidth();
            int imageHeight = original.getHeight();

            System.out.println("started");

            int red;
            int green;
            int blue;
            int colors[] = new int[8];
            Integer colorBias[] = {1, 5, 1};

            int sumColorBias = Algorithms.reduce(Arrays.asList(colorBias), sumIntegers, 0) / 3;

            int end = Math.min(start + 1 + step, imageWidth - 2);

            for (int x = start + 1; x < end; x++) {
                for (int y = 1; y < imageHeight - 2; y++) {

                    red   = 0;
                    green = 0;
                    blue  = 0;

                    colors[0] = original.getRGB(x - 1, y - 1);
                    colors[1] = original.getRGB(x    , y - 1);
                    colors[2] = original.getRGB(x + 1, y - 1);
                    colors[3] = original.getRGB(x - 1, y);
                    colors[4] = original.getRGB(x + 1, y);
                    colors[5] = original.getRGB(x - 1, y + 1);
                    colors[6] = original.getRGB(x    , y + 1);
                    colors[7] = original.getRGB(x + 1, y + 1);

                    for (int color : colors) {
                        red     += colorBias[0] * ((color & 0x00ff0000) >> 16);
                        green   += colorBias[1] * ((color & 0x0000ff00) >> 8);
                        blue    += colorBias[2] *  (color & 0x000000ff);
                    }

                    int newColor = (Math.min(255, (red   / (8 * sumColorBias))) << 16)
                                 + (Math.min(255, (green / (8 * sumColorBias))) << 8)
                                 +  Math.min(255, (blue  / (8 * sumColorBias)));

                    processed.setRGB(x, y, newColor);
                }
            }

            callback.call(processed);
            return null;
        }
    }

    private static final AsyncCallback render = new AsyncCallback<BufferedImage>() {

        public void call(BufferedImage data) {
            numActiveThreads--;

            if (numActiveThreads != 0) return;

            long toc = System.currentTimeMillis() - tic;

            JFrame frame = new JFrame();
            frame.getContentPane().add(new JLabel(new ImageIcon(data)), BorderLayout.CENTER);
            frame.pack();
            frame.setVisible(true);
            frame.setTitle("Time taken: " + toc + "ms");
        }
    };

    private static int calcStepSize(int total, int numThreads, int currentThread) {

        int step = total / numThreads;
        int rem  = total % numThreads;

        if (currentThread >= rem) return step;
        return step + 1;
    }

    private static ExecutorService getThreadPool() {
        if (threadPool == null) {
            threadPool = Executors.newFixedThreadPool(getNumProcessors());
        }
        return threadPool;
    }

    private static int getNumProcessors() {
        return Runtime.getRuntime().availableProcessors();
    }

    public static void main(String[] args) {

        BufferedImage original  = null;
        BufferedImage processed = null;
        URL url;

        try {
            url = new URL("some_image_url.jpg");
            original  = ImageIO.read(url);
            processed = new BufferedImage(original.getWidth(), original.getHeight(), BufferedImage.TYPE_INT_RGB);
        } catch (MalformedURLException e) {
            e.printStackTrace();
            System.exit(1);
        } catch (IOException e) {
            e.printStackTrace();
            System.exit(1);
        }

        int numThreads = getNumProcessors();
        numActiveThreads = numThreads;

        tic = System.currentTimeMillis();

        Collection<Callable<Object>> apps = new ArrayList<Callable<Object>>();

        for (int thread = 0; thread < numThreads; thread++) {
            int step = calcStepSize(original.getWidth(), numThreads, thread);
            apps.add(new BlurImage(original, processed, thread * step, (thread + 1) * step, render));
        }

        try {
            getThreadPool().invokeAll(apps);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

The speed-up I experienced using two threads instead of one is close to optimal, meaning the time it took to calculate the blurred image took almost twice the amount of time with one thread compared to the time taken with two threads.