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;
    }
}