Thursday, December 27, 2007

Development: Optimize Prime Number Search Using Sieve of Eratosthenes

For some reason I have been playing one of those online games where you have a series of hacking or programming related challenges to pass. The most recent challenge I did was one involving a series of silly computations on large numbers involving retrieving all of that numbers preceding prime numbers. Not too difficult, however, performance was a key component of the exercise since you had to have your program give an answer in under 3 seconds. And to add to my frustrations, I decided to do the whole thing in Java due to Javas utilities for network communication.

First, I figured I would take the input number, loop through all numbers up to it, and add any prime number to a List. What resulted was something like below:

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


public class BadPrimer {

/*
* Generic prime number check
*/
public boolean isPrime(int number)
{
if (number == 1)
return false;

for (int x = 2; x < number; x++)
{
if ((number % x) == 0)
{
return false;
}
}

return true;
}

/**
* Find all prime numbers before number
* @param number
* @return
*/
public List findAllPrimes(int number)
{
List l = new ArrayList();

for (int x = 2; x <= number; x++)
{
if (isPrime(x))
{
l.add(x);
}
}

return l;
}

public static void main(String[] args) {
BadPrimer p = new BadPrimer();

List l = p.findAllPrimes(8000000);
for (java.util.Iterator i = l.iterator(); i.hasNext();)
{
Integer number = (Integer)i.next();
System.out.println(number);
}
}

}


Needless to say, that was not quite up to task. Worked great on small numbers, but for numbers in the area of 8,000,000 or so, it was just horrendously bad. So, back to the drawing board. My next thought was, why not generate the list of primes beforehand. But generating the list took just as long, and wasn’t very efficient. There are things I could have done to speed things up, but the bottom line was this just wasn’t efficient enough.

So I had to hit the books a little and find some of those really old school math algorithms that weird Greeks came up with thousands of years ago to do large calculations without the aid of computers. What I came up with was the Sieve of Eratosthenes, a way of taking a set of numbers in a list, and eliminating numbers that aren’t prime numbers, really quickly. So, with pre-generating a list of Prime numbers using the found algorithm, my next attempt looked like this:

import java.util.Arrays;

public class BadPrimer {
public int [] primeArray;

/**
* using the sieve of Eratosthenes algorithm, quite cool actually
*/
public void buildPrimeSet()
{
int MAX_SIZE = 10000000;

//create a boolean array and set all elements to true
boolean [] numArray = new boolean[MAX_SIZE];
Arrays.fill(numArray, true);

//we already know 0 and 1 are not prime numbers, so ignore them
numArray[0] = false;
numArray[1] = false;

//x will be out driving prime loop, y will be the elimination loop
for (int x = 2; x < MAX_SIZE; x++)
{
//if x is still true, it is a prime, and we need to keep it
if (numArray[x])
{
//advance our inner loop, starting at twice the current position of x, and start dividing
//If you use y++ as the counter advance, the generation takes to long
for (int y = (x * 2); y < MAX_SIZE; y += x)
{
//if y is already false, dont bother setting
if (numArray[y])
{
numArray[y] = false;
}
}
}
}

int totalCount = 0;

//find the total number of primes
//this could be done in the above loop, but for logic
//illistration, I kept it here
for (int x = 2; x < MAX_SIZE; x++)
{
if (numArray[x])
{
totalCount++;
}
}

//create our array based on the number of primes
//and populate the array with the prime numbers
//Note: there are better ways of doing this, such as adding
//the prime numbers in the above loop when they are found, but
//I did it this way for logic reason, not efficiency
primeArray = new int[totalCount];
int pos = 0; //a position counter
for (int x = 2; x < MAX_SIZE; x++)
{
if (numArray[x])
{
primeArray[pos] = x;
pos++;
}
}
}

/**
* Find all prime numbers before number
* @param number
* @return
*/
public int findAllPrimes(int number)
{
//using x as our arary position
//go through the list until the value in our
//array is greater than the number used. We now have the cut off position
//to mark all prime numbers lower than our current number
int x = 0;
while (primeArray[x] <= number)
{
x++;
}

return x;
}

public static void main(String[] args) {
BadPrimer p = new BadPrimer();

p.buildPrimeSet();
int primeCutOff = p.findAllPrimes(31337);

for (int x = 0; x < primeCutOff; x++)
{
System.out.println(p.primeArray[x]);
}
}

}


I saved you a lot of the iterations I went through. The final chunk above was after learning quite a few things. First, working with primitives is much faster than working with objects. I abandoned the idea of using a List of integers and instead went with an Array of integers. This made a large improvement in performance since I didn’t have to do any conversions of object types, and I found out the hard way that Java will take int from a List and convert them to Integer objects. The second biggest thing was eliminating unnecessary iterations in my loops. At first, I was going through the inner loop in buildPrimeSet() using y++ instead of y+=x. This wasted a lot of iterations since the most a number divided by something else will do is halve it (integer wise). So if x was 50, it didn’t make sense to test 51 – 99 since they aren’t valid multiples of X, and that kind of defeats the purpose of the Sieve of Eratosthenes algorithm, which states to eliminate numbers that are multiples of the current prime.

So, the end result, what took hours to run before gets run in a matter of milliseconds now. Valuable lesson... I might need to brush up on some of my algorithm development skills. Regardless, this took care of the first part of the calculation in finding all the prime numbers for the requested number, the remaining parts will remain a mystery so I don’t give away the answer to the challenge.

Monday, December 10, 2007

BIRT: Dynamic Images

There was a question on the BIRT newsgroup about how to put a dynamic image into a report file. This is typically done in multi-company sites, where a different header or logo will appear based on some environmental parameter. In the following example I will show how to do this with a report parameter, although the same thing can be done based on a URL.

The following example will show one of two logos, depending on the value of a report parameter. If the value is equal to 0, we will show the Eclipse logo at

http://www.eclipse.org/eclipse.org-common/themes/Phoenix/images/eclipse_home_header.jpg

If the value is 1, we will show the BIRT Exchange logo:

http://www.birt-exchange.com/themes/birt/images/homep_r1_c1.gif

This image will reside in the Master Page of the report. So lets take a look at how to do this.

  1. First, create a new report called DynamicImage.rptDesign

Figure 1. Create new Report

  1. In the new report design, open up the Master Page tab.
  2. Drag over a grid, and make it 2 column, 1 row.
  3. In the 1st column, drag over an Image component.
  4. For the URL, put in “http://www.eclipse.org/eclipse.org-common/themes/Phoenix/images/eclipse_home_header.jpg”. Be sure to keep the quotes. This is more as a place holder than anything else.

Figure 2. Master Page with Image

  1. Create a new report parameter called imageSelector. It needs to be an Integer type. In the following screen shot, I am using a List Box and a List of Values for this purpose.

Figure 3. Create new Parameter

  1. Select the Image.
  2. Open the Script tab in the Report Designer
  3. Change the Event to onRender.
  4. Use the following BIRT Script
if (params["imageSelector"] == 0)
{
this.setURL("http://www.eclipse.org/eclipse.org-common/themes/Phoenix/images/eclipse_home_header.jpg");
}
else
{
this.setURL("http://www.birt-exchange.com/themes/birt/images/homep_r1_c1.gif");
}

  1. Save and run.

When you set the value to Eclipse, it will show the Eclipse logo. When set to the BIRT Exchange, it will show that logo.

Figure 4. The Final Report

Saturday, December 08, 2007

BIRT: Passing Serialized Objects as Parameters

Recently I had a question about being able to serialize Java Objects and use them as the data source. I have a few possible solutions, but I wanted to look at one of the options a little deeper.

In this scenario, the Java Objects are actually generated outside of the report application, and need to be passed to the report as a parameter. The easiest way was to create a Java class that extends the java.io.Serializable class. In additional to using the Serializable class, I also want to URL encode the serialized class. What this means is that I need to Decode and Deserialize the class inside of the report.

The following is a walkthrough of the classes that I built, and an external Java Event Handler for a Report Design that will handle the object.

To demonstrate this, I used the following Java class.

package com.digiassn.blogspot;

import java.io.Serializable;

public class EmployeeParameter implements Serializable {
static final long serialVersionUID = 11111112;

private int employeeNumber;
private String date;
public int getEmployeeNumber() {
return employeeNumber;
}
public void setEmployeeNumber(int employeeNumber) {
this.employeeNumber = employeeNumber;
}
public String getDate() {
return date;
}
public void setDate(String date) {
this.date = date;
}


}



Not much to this class. The serialVersionUID was defined to avoid issues with the URLEncode and URLDecode process, which if not implicitly defined, causes the URLDecode of the object to fail. This is also the same reason I used String as my Date type instead of the java.util.Date. For some reason there were errors with the Date and its use of the serialVersionUID (yet, String, and a few other classes didn’t have any issues).

I wanted to test to see if the whole serialize and URLEncode process would work, so I created the following Unit test.

package com.digiassn.blogspot.tests;

import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.UnsupportedEncodingException;
import java.net.URLDecoder;
import java.net.URLEncoder;

import junit.framework.TestCase;

import com.digiassn.blogspot.EmployeeParameter;

public class TestEmployeeParameter extends TestCase {
private EmployeeParameter param;

protected void setUp() throws Exception {
super.setUp();

param = new EmployeeParameter();

param.setEmployeeNumber(1);
param.setDate("01-01-2005");
}

protected void tearDown() throws Exception {
super.tearDown();
}

public void testGetEmployeeNumber() {
assertEquals(1, param.getEmployeeNumber());
}

public void testGetDate() {
assertEquals("01-01-2005", param.getDate());
}

public void testSerialize()
{
ByteArrayOutputStream bos = null;
try {
bos = new ByteArrayOutputStream();
ObjectOutputStream obj_out = new ObjectOutputStream (bos);
obj_out.writeObject ( param );
} catch (IOException e) {
e.printStackTrace();
fail("Error with serialization\n\n");
}

String encoded = bos.toString();
try {
encoded = URLEncoder.encode(encoded, "UTF-8");
} catch (UnsupportedEncodingException e1) {
e1.printStackTrace();

fail("Unsupported formatting");
}
System.out.print("The serialized output is: " + encoded);

try {
String toDecode = URLDecoder.decode(encoded, "UTF-8");
ByteArrayInputStream bis = new ByteArrayInputStream(toDecode.getBytes());
ObjectInputStream obj_in = new ObjectInputStream (bis);

Object obj = obj_in.readObject();

if (obj instanceof EmployeeParameter)
{
assertEquals(1, ((EmployeeParameter)obj).getEmployeeNumber());
assertEquals("01-01-2005", ((EmployeeParameter)obj).getDate());
}
} catch (IOException e) {
e.printStackTrace();
fail("Error with deserialization");
} catch (ClassNotFoundException e) {
e.printStackTrace();
fail("Error with deserialization");
}

}

}


So, my next task is to create the Event Handler. In BIRT, event handlers need to extend their appropriate event handler type. Since this is a Scripted Data Source, I need to extend the org.eclipse.birt.report.engine.api.script.eventadapter.ScriptedDataSetEventAdapter type.

package com.digiassn.blogspot.handlers;

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.UnsupportedEncodingException;
import java.net.URLDecoder;

import org.eclipse.birt.report.engine.api.script.IReportContext;
import org.eclipse.birt.report.engine.api.script.IUpdatableDataSetRow;
import org.eclipse.birt.report.engine.api.script.ScriptException;
import org.eclipse.birt.report.engine.api.script.eventadapter.ScriptedDataSetEventAdapter;
import org.eclipse.birt.report.engine.api.script.instance.IDataSetInstance;

import com.digiassn.blogspot.EmployeeParameter;

public class EmployeeEventHandler extends ScriptedDataSetEventAdapter {
private EmployeeParameter param;
int count = 0;

@Override
public boolean fetch(IDataSetInstance dataSet, IUpdatableDataSetRow row) {

if (count < 1)
{
try {
if (param == null)
{
row.setColumnValue("employeeNumber", -1);
row.setColumnValue("setDate", "Error, param is null");
}
else
{
row.setColumnValue("employeeNumber", param.getEmployeeNumber());
row.setColumnValue("setDate", param.getDate());
}
count++;

return true;
} catch (ScriptException e) {
e.printStackTrace();
}
}


return false;
}

@Override
public void beforeOpen(IDataSetInstance dataSet,
IReportContext reportContext) {

String myParam = null;

try {
myParam = URLDecoder.decode((String) reportContext.getParameterValue("employeeParam"), "UTF-8");
} catch (UnsupportedEncodingException e1) {
e1.printStackTrace();
}
System.out.println("Got parameters");
ByteArrayInputStream bis = new ByteArrayInputStream(myParam.getBytes());

try {
ObjectInputStream obj_in = new ObjectInputStream(bis);

param = (EmployeeParameter)obj_in.readObject();
} catch (IOException e) {
e.printStackTrace();
} catch (ClassNotFoundException e) {
e.printStackTrace();
}
}
}




So, now I have the event handler made, I need to create the report. To create the report I use the following steps:
1: Create a new report.
2: Create a Scripted Data Source.
3: Create a data set.
4: Add in the following two fields into the data set
-employeeNumber
-setDate
5: Add a report parameter called employeeParam.
6: Drag the data set over to the report design window.
7: Select the new data set in the Data Explorer.
8: In the Property Editor. Select the Event Handler tab.
9: Under the Event Hander, browse and select the Java Object Event handler.

Now, when I run the report, my report will use the external object. I need to pass in the serialized version of the object. In my case, I used the following test string.

%C2%AC%C3%AD%05sr5com.digiassn.blogspot.EmployeeParameter%C2%A9%C5%A0%C3%88%02%02I%0EemployeeNumberL%04datet%12Ljava%2Flang%2FString%3Bxp%01t%0A01-01-2005



I would recommend that you use the Unit test and copy the serialized object from the standard output device.

And that’s it. Now, I deployed this to an Apache Tomcat server using the BIRT Web Viewer to view my report. I had to copy the .class files for EmployeeParameter and the event handler into the shared class folder under Tomcat. I also needed copy all the JAR files in the Web Viewer into the shared lib folder to get around some silly bug in the Web Viewer (note: this was not a problem prior to version 2.2.1).

I still ran into one outstanding issue with this approach. If I tried to use the serialized object in a URL parameter in a browser, I would get a SaxParser error. This wasn’t a problem if I passed the parameter using the dialog in the web viewer, or if I assigned the parameter using the Report Engine API, so it must have something to do with the way the Viewer app handles its SOAP requests.