JavaOne Talk: Scala Reversible Numbers

See this post about why this code is being shown. See this post for the Java version to compare against.

class ScalaReversible(max:Int){
  import java.lang.Character._
  lazy val numReversible = (11 to max).filter(reversible(_)).size
  private
  def reverse(n:Int)=n + parseInt(n.toString.reverse)
  def allOdd(n:Int) = n.toString.map(digit(_,10)).forall(_ % 2 == 1)
  def reversible(n:Int) = allOdd(reverse(n))
}

JavaOne Talk: Python Reversible Numbers

See this post about why this code is being shown. See this post for the Java version to compare against.

class PyReversible(object):
    __slots__ = ['max','numReversible']

    def __init__(self, max):
        self.max = max
        self.numReversible = self.countReversible()

    def countReversible(self):
        return  len([i for i in xrange(11,self.max+1) if self.reversible(i)])

    def allOdd(self,n):
        for ch in str(n):
            if int(ch) % 2 != 1:
                return False
        return True

    def reverse(self,n):
        return n + int(str(n)[::-1])

    def reversible(self,n):
        return self.allOdd(self.reverse(n))

JavaOne Talk: Ruby Reversible Numbers

See this post about why this code is being shown. See this post for the Java version to compare against.

class RubyReversible
  def initialize(max)
    @max = max
    @numReversible = nil
  end

  def allOdd(n)
    digits = n.to_s.split(//)
    digits.length == digits.map{|c| c.to_i}.select{|i| 
        i % 2 == 1}.length
  end

  def reverse(n)
    n + n.to_s.reverse.to_i
  end

  def reversible(n)
    allOdd(reverse(n))
  end

  def countReversible()
    @numReversible ||= (11..@max).select{|i| 
        reversible(i)}.length
    @numReversible 
  end
end

JavaOne Talk: Groovy Reversible Numbers

See this post about why this code is being shown. See this post for the Java version to compare against.

public class GroovyReversible {
  final Integer max
  final Integer numReversible = 0
  public GroovyReversible(max){
    this.max = max
    this.numReversible = this.countReversible()
  }

  def countReversible(){
    numReversible ?: (11..max).findAll{reversible(it)}.size()
  }

  def reversible(n){
    allOdd(reverse(n))
  }

  def allOdd(n){
    n.toString().toList().collect {it.toInteger()}.every{it % 2 == 1}
  }

  def reverse(n){
    n + n.toString().toList().reverse().join().toInteger()
  }
}

JavaOne Talk: Reversible Numbers

See this post about why this code is being shown. This is a different algorithm, it is a brute force solution to Project Euler problem #145. Here is the Java "reference" implementation.

public class Reversible {
    final int max;
    final int numReversible;

    public Reversible(int max){
        this.max = max;
        this.numReversible = this.countReversible();
    }

    private int countReversible(){
        if (numReversible > 0){
            return numReversible;
        }
        int cnt = 0;
        for (int i=11;i<=max;i++){
            if (reversible(i)) {
                cnt++;
            }
        }
        return cnt;
    }

    private boolean reversible(int n){
        return allOdd(reverse(n));
    }

    private boolean allOdd(int n){
        while (n > 0){
            int remainder = n % 2;
            if (remainder == 0) return false;
            n = n / 10;
        }
        return true;
    }
    
    private int reverse(Integer n){
        char[] digits = n.toString().toCharArray();
        char[] rev = new char[digits.length];
        for (int i=digits.length-1;i>=0;i--){
            rev[i] = digits[digits.length -i-1];
        }
        return n + Integer.parseInt(String.valueOf(rev));
    }
}

JavaOne Talk: Scala Word Sort

See this post about why this code is being shown. See this post for the Java version to compare against.

class ScalaWordSort(fileName:String){
  lazy val sortedWords = {
    Source.fromFile(dataFile).getLines.foreach(_.split(" ").foreach(words ::= _))
    words.sort(_.toLowerCase < _.toLowerCase)
  }
  private
  val dataFile = new File(fileName)
  var words:List[String] = Nil
}

JavaOne Talk: Python Word Sort

See this post about why this code is being shown. See this post for the Java version to compare against.

class PyWordSort(object):
    def __init__(self, fileName):
        print "init " + fileName
        self.dataFile = open(fileName)
        self.words = []
    def sortedWords(self):
        if len(self.words) == 0:
            for line in self.dataFile:
                for word in line.split():
                    self.words.append(word)
            self.words.sort(lambda w,w1: cmp(w.lower(), w1.lower()))
        return self.words

JavaOne Talk: Ruby Word Sort

See this post about why this code is being shown. See this post for the Java version to compare against.

class RubyWordSort
  def initialize(fileName)
    @dataFile = File.new(fileName)
    @words = Array.new
  end
  def sortedWorts
    if (@words.length == 0)
      @dataFile.each_line{ |line| line.split(' ').each{ |word| @words << word}}
      @words = @words.sort{ |w,w1| w.upcase <=> w1.upcase }
    end
    @words
  end
end

JavaOne Talk: Groovy Word Sort

See this post about why this code is being shown. See this post for the Java version to compare against.

public class GroovyWordSort {
  File dataFile
  List words = []
  public GroovyWordSort(fileName){
    dataFile = new File(fileName)
  }

  def sortedWords(){
    if (!words){
      dataFile.eachLine{it.tokenize().each {words.add(it) }}
      words = words.sort{w,w1 -> w.toLowerCase() <=> w1.toLowerCase()}
    }
    words
  }
}

JavaOne Talk: Word Sort

See this post about why this code is being shown. This is a different algorithm than the previous examples, so once again I will start with the Java version. The program takes a file name, and reads the file into memory. The file contains a list of randomly generated words, separated by spaces. The program does a case-insensitive sort of all of the words. Here is the Java "reference" implementation:

import java.io.*;
import java.util.*;

public class WordSort {
    private final File dataFile;
    private final List<String> words;
    public WordSort(String fileName){
        dataFile = new File(fileName);
        words = new ArrayList<String>();
    }

    public List<String> getSortedWords(){
        if (words.size() > 0){
            return words;
        }
        try {
            BufferedReader reader = new BufferedReader(new FileReader(dataFile));
            try{
                String line;
                while ( (line = reader.readLine()) != null){
                    for (String string : line.split(" ")){
                        words.add(string);
                    }
                }
            } finally {
                reader.close();
            }
            Collections.sort(words, new Comparator<String>(){
                public int compare(String s, String s1) {
                    return s.toLowerCase().compareTo(s1.toLowerCase());
                }
            });
            return words;
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }
}

JavaOne Talk: Fan Prime Sieve

See this post for an explanation on why this code is being shown and what kind of responses would be useful. See this post for the Java algorithm to compare against.

Note: This solution is courtesy of Mr. Fan himself, Brian Frank. Thanks Brian!

class Primes {
  Int[] primes := Int[,]
  Int size

  new make(Int n) {
    size = n
    primes.capacity = n
    init
  }

  private Void init() {
    i := 2
    max := calcSize
    nums := Bool[,]
    nums.fill(true, max)
    while (i < max && primes.size < size) {
      p := i
      if (nums[i])
      {
        primes.add(p)
        j := 2*p;
        while (j < max - p) {
          nums[j] = false
          j += p;
        }
      }
      i += 1;
    }
  }

   Int last() { primes.last }

   private Int calcSize() {
     max := 2
     while ((max.toFloat/max.toFloat.log).toInt < size && max < 0x7fff_ffff && max > 0) {
        max *=2; // memory inefficient, but fast
     }
     return max;
  }
}

JavaOne Talk: Scala Prime Sieve

See this post for an explanation on why this code is being shown and what kind of responses would be useful. See this post for the Java algorithm to compare against.

import java.lang.Integer._
import java.lang.Math._
import scala.collection.mutable.ArrayBuffer

class ScalaPrimes(val size:Int){
  val primes = new ArrayBuffer[Int]
  var cnt = 0
  init
  def last = primes(primes.size - 1)

  private
  def init {
    var i = 2
    val max = calcSize
    val nums = new ArrayBuffer[Boolean]
    for (i<-0 until max) nums += true
    while (i < max && cnt < size){
      val p = i
      if (nums(i)){
        primes += p
        cnt += 1
        (p until max/p).foreach((j) => nums.update(p*j,false))
      }
      i += 1
    }
  }
  def calcSize = {
    var max = 2
    while ( (max/log(max)) < size && max < MAX_VALUE && max > 0) {
      max *= 2
    }
    max
  }
}

JavaOne Talk: Python Prime Sieve

See this post for an explanation on why this code is being shown and what kind of responses would be useful. See this post for the Java algorithm to compare against.

from math import log
import sys

class PyPrimes(object):
    __slots__ = ['cnt','primes','size']

    def __init__(self,n):
        self.primes = n*[0]
        self.cnt = 0
        self.size = n
        i = 2
        max = self.calcSize()
        nums = max*[True]
        while i < max and self.cnt < self.size:
            p = i
            if nums[i]:
                self.primes[self.cnt] = p
                self.cnt += 1
                for j in xrange(p, max/p):
                    nums[p*j] = False
            i+= 1

    def calcSize(self):
        max = 2
        while max/log(max) < self.size:
            max = max *2 # this makes the sieve too big, but fast
        return max

    def last(self):
        return self.primes[self.cnt - 1]

JavaOne Talk: Ruby Prime Sieve

See this post for an explanation on why this code is being shown and what kind of responses would be useful. See this post for the Java algorithm to compare against.

class RubyPrimes
  attr_accessor :cnt, :primes
  def initialize(n)
    @primes = Array.new(n,0)
    @cnt = 0
    i = 2
    max = calcSize
    nums = Array.new(max,true)
    while (i < max && @cnt < @primes.length)
      p = i
      if (nums[i])
        @primes[@cnt] = p
        @cnt += 1
        (p .. (max/p)).each{ |j| nums[p*j] = false }
      end
      i += 1
    end
  end
  def calcSize
    max = 2
    max = max * 2 while ( max/Math.log(max) < @primes.length)
    max
  end
  def last
    @primes[@cnt -1]
  end
end

JavaOne Talk: Groovy Prime Sieve

See this post for an explanation on why this code is being shown and what kind of responses would be useful. See this post for the Java algorithm to compare against.

public class GroovyPrimes {
  int cnt = 0
  final def primes = []
  final int size

  public GroovyPrimes(int n){
    size = n
    init()
  }

  int last() {
    primes[cnt-1]
  }
  
  private void init(){
    int i = 2
    int max = calcSize()
    def nums = [true]*max
    
    while (i < max && primes.size() < size) {
      int p = i
      if (nums[i]) {
        primes << p
        (p..(max/p)).each{ j-> if (p*j < max) nums[p*j] = false}
      }
      i += 1
    }
  }

  private int calcSize(){
    int max = 2
    while ((max / Math.log(max)) < size && 
        max < Integer.MAX_VALUE && max > 0) {
      max *= 2
    }
    max
  }
}

JavaOne Talk: Being Less Efficient

See previous post if you have not already. I was getting ready to post some of implementations of the prime sieve in other languages, when I realized I had probably unfairly over-optimized the Java solution by using arrays. This kind of optimization is available in some languages, but not others. So it would be hard to do a fair comparison if this optimization was used at all. So here is the Java prime sieve, but using resizable lists instead of primitive arrays:

import java.util.List;
import java.util.ArrayList;

public class Primes {
    final private List<Integer> primes;
    private final int size;
    
    public Primes(int n){
        size = n;
        primes = new ArrayList<Integer>(n);
        init();
    }

    private void init(){
        int i=2;
        int max = calcSize();
        List<Boolean> nums = 
            new ArrayList<Boolean>(max);
        for (int j=0;j<max;j++){
            nums.add(true);
        }
        while (i < max && primes.size() < size){
            int p = i;
            if (nums.get(i)){
                primes.add(p);
                int j = 2*p;
                while (j < max - p){
                    nums.set(j,false);
                    j += p;
                }
            }
            i += 1;
        }
    }

    public int last(){
        return primes.get(primes.size()-1);
    }

    private int calcSize(){
        int max = 2;
        while ((max/Math.log(max)) < size && 
            max < Integer.MAX_VALUE && max > 0){
            max *=2;
        }
        return max;
    }
}

JavaOne Talk: Prime Sieve

Next month I am speaking at JavaOne on the performance of various programming languages running on the JVM. For the talk, I am taking several algorithm/programming problems solved in each of the various languages, and comparing the relative performance and tuning tips. For each problem, I am using "native Java" as a reference point. This is the first of many blog posts that show these various programming problems solved in the various languages. I am posting these programs as a way for other folks to let me know where I've screwed up, i.e. done something that will negatively affect performance, etc.

I am not too interested in significantly different ways to solve these problems. For example, the first algorithm is a prime sieve. So I would not be interested in somebody letting me know that there are other ways to generate primes besides a sieve. However, I am interested in finding mistakes in my implementations. I will not claim to be an expert in any of these languages -- in fact I have been learning two of the languages, Fan and Clojure, specifically for this talk -- so there is a good chance that I did screw something up. Even in the languages that I'd like to think I am pretty good at (including Java), I figure there is always a good chance of me doing something screwy there too. So without further ado, here is my prime sieve in Java.

import java.util.Arrays;

// calculates the first n primes
public class Primes {
    final private int[] primes;
    private int cnt = 0;
    
    public Primes(int n){
        primes = new int[n];
        init();
    }

    private void init(){
        int i=2;
        int max = calcSize();
        boolean[] nums = new boolean[max];
        Arrays.fill(nums, true);
        while (i < max && cnt < primes.length){
            int p = i;
            if (nums[i]){
                // add it to the list of primes
                primes[cnt++] = p;
                int j = 2*p;
                // remove all the multiples of the prime
                while (j < max - p){
                    nums[j] = false;
                    j += p;
                }
            }
            i += 1;
        }
    }

    public int last(){
        return primes[cnt-1];
    }

    // calculates number of integers needed to find n primes
    private int calcSize(){
        int max = 2;
        while ((max/Math.log(max)) < primes.length && max < Integer.MAX_VALUE && max > 0){
            max *=2; // memory inefficient, but fast
        }
        return max;
    }
}

Mobile OS Wars: Upgrades

Right now Apple and Google are in the midst of major upgrades to the OS on their devices, the iPhone OS and Android. If you develop for these platforms, you need to make sure your applications have no issues on the new versions. The simplest first step is to upgrade your SDK and development tools, and re-compile. Neither OS updates remove (any?) APIs, they mostly add to them. So it is unlikely your application does not compile under the new SDK. You can also launch your application in the emulator provided with each SDK. Now there is a little more chance of a bug popping up.

Still, a lot of upgrades are only found when you run your app on the new OS on a device. Why is this? A lot of the bugs that come from these upgrades are memory management issues, multi-threaded issues, or networking issues. When you run on an emulator, many of these issues just never happen (memory/networking) or behave differently because of the difference in processor seed (multi-threading.) So you need to upgrade the OS on your test devices (you do have dedicated testing devices, not just your personal phone, right?)

Upgrading your iPhone OS is really quite easy. You download the new OS. You right-click on the "restore" button in iTunes, or you can use the Organizer in XCode. Either way, device is wiped, the new OS is installed, and then your data is reloaded from a backup (iTunes backs everything up automatically.) The only gotcha is that apps that weren't installed via iTunes, i.e. apps you developed and are testing, do not get backed up, so they disappear. This should not be a problem since you have the source code for such apps. However, in order to re-install from source code via XCode, your SDK must also be upgraded to the same version as the OS. Again, you probably upgraded the SDK first anyways, so no big deal.

Upgrading your Android device is not quite as straightforward. There are a lot of steps, so I won't repeat them all here. The upgrade is fundamentally different in that you replace parts of the system in place. Your device is not wiped. This is necessary because there is no automatic backup process on Android phones. On the iPhone, this is handled by iTunes. There is no analogous desktop software companion to Android. This is viewed by many as a pro, but in this case I consider it a con. Anyways, there are a lot of steps, but it is very smooth and very fast. In fact, it is much faster than the iPhone process because there is no delete/restore going on.

All of this points to some of the core differences between these platforms. Others have pointed to the Mac vs. PC scenario of the 80's as being similar to the iPhone vs. Android scenario of today. Apple went with a closed platform where they controlled everything, vs. the "open" combination of Windows plus Intel. Any manufacturer could slap an Intel chip in their machine and install Windows on there, with full freedom on what else went in to the machine. Same thing is going on here. Apple controls the OS and hardware of the iPhone. Android can go on many different types of hardware. Right now this is not making a big difference, since there are not yet a lot of Android phones. However, it seems likely that at some point you will see Android phones that are free with a contract or maybe $100 from Metro PCS or even pay-as-you-go carriers.

Ok so that was a tangent, what does it have to do with this issue? Well, by having a closed system, Apple can provide a lot of advantages. Upgrading is simple. For consumers, you get the upgrade from Apple directly. You might notice the Android link above is from HTC, the maker of the first Android phone. Most consumers will get the upgrade from T-Mobile. Notice that Google is not even in this conversation, even though not only do they make the OS, but it is open source. In addition, many developers I know are dreading the proliferation of Android. Currently development for Android is nice, in fact a lot nicer than for iPhone. The development/emulator scenarios are equivalent, but debugging on devices is much simpler. However, when more variants of Android appear, and those variants are more specific to the devices they run on, then right once / run anywhere fades away. Again, notice that the OS upgrade came from the handset manufacturer already. That is very significant.

Tail Recursion in Scala

Earlier this week, I gave a talk about Scala with Bill Venners and David Pollak. In my slides, I had an example of a factorial function in Scala and in Java. I made that point that not only is Scala usually almost as fast as Java, but sometimes it is even faster. One reason for this is that the Scala compiler can perform tail recursion optimizations on your code. This is something that has been proposed for Java as well as other languages, but has its downside as well.

Back to Scala... Bill also had a slide that showed a factorial function in Scala, though it was much simpler as it made use of Scala's implicit conversions between integers and BigInts. Afterwards, Bill and I were talking, and he pointed that he did not think the Scala compiler would be able to optimize either my code or his code. Here is code that is very similar to Bill's code (I don't have the exact code handy, so I recreated it from memory):

def factorial(n:BigInt):BigInt={
 if (n == 0) 1
 else n*factorial(n-1)
}

Why can't this be optimized as a tail call? Instead of explaining it myself, I will introduce the hero of this story, Daniel Spiewak (check out his blog or follow him on Twitter.) Bill emailed Daniel about his suspicion, and Daniel confirmed it :
You're quite correct: this version of factorial is not tail recursive.
I find it sometimes helps to split the last expression up into atomic
operations, much as the Scala parser would:

else {
 val t1 = n - 1
 val t2 = factorial(t1)
 n * t2
}

It is possible to devise a tail-recursive factorial. In fact, it
might be possible to convert any recursive function into a
tail-recursive equivalent, but I don't have a proof for that handy.
Back to factorial:

def factorial(n: Int) = {
 def loop(n: Int, acc: Int): Int = if (n <= 0) acc else loop(n - 1, acc * n)
 loop(n, 1)
}

I'm cheating a bit by taking advantage of the fact that multiplication
is commutative, but this is the general idea. Some functions are
naturally tail recursive, but for those which are not, this
"accumulator pattern" is a fairly easy way to achieve the equivalent
result. Technically, the accumulator must be combined with an
inversion of the computation direction (bottom-up rather than
top-down) to generate a truly-equivalent tail-recursive function, but
it is not necessary for examples like this one.
This accumulator pattern is a great tip. To drive home the difference this produces in the behavior of the Scala compiler, it is useful to use our good 'ol friend javap. For the original code, here is the output:

public scala.BigInt factorial(scala.BigInt);
  Code:
   0: aload_1
   1: iconst_0
   2: invokestatic #27; //Method scala/runtime/BoxesRunTime.boxToInteger:(I)Ljava/lang/Integer;
   5: invokestatic #31; //Method scala/runtime/BoxesRunTime.equals:(Ljava/lang/Object;Ljava/lang/Object;)Z
   8: ifeq 21
   11: getstatic #36; //Field scala/BigInt$.MODULE$:Lscala/BigInt$;
   14: iconst_1
   15: invokevirtual #40; //Method scala/BigInt$.int2bigInt:(I)Lscala/BigInt;
   18: goto 40
   21: aload_1
   22: aload_0
   23: aload_1
   24: getstatic #36; //Field scala/BigInt$.MODULE$:Lscala/BigInt$;
   27: iconst_1
   28: invokevirtual #40; //Method scala/BigInt$.int2bigInt:(I)Lscala/BigInt;
   31: invokevirtual #45; //Method scala/BigInt.$minus:(Lscala/BigInt;)Lscala/BigInt;
   34: invokevirtual #47; //Method factorial:(Lscala/BigInt;)Lscala/BigInt;
   37: invokevirtual #50; //Method scala/BigInt.$times:(Lscala/BigInt;)Lscala/BigInt;
   40: areturn

I know this looks scary if you have not used javap much, but if you have then you will recognize that this is a straightforward compilation. You can see the de-sugaring (try scalac -print for a better way to view the de-sugaring that the compiler performs) like the implicit conversions being made (#15 above) and the operators as method invocations (#31 and #37.) Especially important is that you can see the recursive call to factorial on #34, and then a call to BigInt.$times, i.e. multiplication for BigInts.

Now let's rewrite the method using Daniel's suggestions:

def factorial(n:BigInt):BigInt={
 def loop(n:BigInt, acc:BigInt):BigInt = if (n <= 0) acc else loop(n-1,acc*n)
 loop(n,1)
}

And now when we run javap, things are a lot different (make sure you use the -private flag with javap to get all of the details):

private final scala.BigInt loop$1(scala.BigInt, scala.BigInt);
  Code:
   0: aload_1
   1: getstatic #26; //Field scala/BigInt$.MODULE$:Lscala/BigInt$;
   4: iconst_0
   5: invokevirtual #30; //Method scala/BigInt$.int2bigInt:(I)Lscala/BigInt;
   8: invokevirtual #36; //Method scala/BigInt.$less$eq:(Lscala/BigInt;)Z
   11: ifeq 16
   14: aload_2
   15: areturn
   16: aload_1
   17: getstatic #26; //Field scala/BigInt$.MODULE$:Lscala/BigInt$;
   20: iconst_1
   21: invokevirtual #30; //Method scala/BigInt$.int2bigInt:(I)Lscala/BigInt;
   24: invokevirtual #40; //Method scala/BigInt.$minus:(Lscala/BigInt;)Lscala/BigInt;
   27: aload_2
   28: aload_1
   29: invokevirtual #43; //Method scala/BigInt.$times:(Lscala/BigInt;)Lscala/BigInt;
   32: astore_2
   33: astore_1
   34: goto 0

public scala.BigInt factorial(scala.BigInt);
  Code:
   0: aload_0
   1: aload_1
   2: getstatic #26; //Field scala/BigInt$.MODULE$:Lscala/BigInt$;
   5: iconst_1
   6: invokevirtual #30; //Method scala/BigInt$.int2bigInt:(I)Lscala/BigInt;
   9: invokespecial #51; //Method loop$1:(Lscala/BigInt;Lscala/BigInt;)Lscala/BigInt;
   12: areturn

At the bottom is the decompilation of the factorial function. Notice that it calls something called loop$1. That is the compiled version of the inner function loop. It is shown at the top of the decompiler output. The most important thing to notice here is the #34 -- the goto statement. This is a goto-loop. Notice that there is no recursive call back to the loop$1 inside the function, just as there is no call back to factorial inside the factorial function. The compiler removed the tail recursion and replaced it with a goto loop, just as Daniel said it would.

For more proof, you can run the code. On my MacBook, the original loop will blow up in a stack overflow when trying to calculate 60,000! I'm sure it blows up well before then, but you get the point. The optimized version of the code has no problems with 60,000! though it does take a while to calculate.

The one last mystery in all of this for me, goes back to my slides on Scala. In the slides, I used tail recursion as the reason why the factorial code ran faster in Scala than in Java. Clearly I was wrong. The code definitely ran faster on Scala, but I do not know why exactly. Perhaps javap can shine some light on this, too...

ActionScript Quickie: Check for Required Params

You ever need to test that a bunch of variables are not null/empty/true? Here is a quick and dirty way to do it in ActionScript 3.0:

private function validArgs(...args):Boolean{
 return args.every(function(arg:Object, ...crap):Boolean {
  return arg ? true : false; });
}

Usage:

var firstName:String = ...
var lastName:String = ...
var iq:int = ...
var friends:Array = ...
validArgs(firstName, lastName, iq > 100, friends.length);