Wednesday, May 20, 2009

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

Monday, May 18, 2009

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

Saturday, May 09, 2009

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]

Tuesday, May 05, 2009

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

Sunday, May 03, 2009

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