Timeout anything easily

Sometimes you want to set a timeout for something that doesn’t have a built in timeout functionality. What can you do if a setTimeout method is not present? for example in a web service?.

We can achieve this using some classes from the standard library of the java.util.concurrent package .

As with the last post we are going to keep things simple, for more detailed explanations and if you’re looking for more functionalities, please refer to the docs.

I made a simple class that implements the Callable interface:

import java.util.Random;
import java.util.concurrent.Callable;

import org.apache.log4j.Logger;

public class DummyCallback implements Callable<String>{

    private Logger log = Logger.getLogger(this.getClass());

    public String call() throws Exception {
        Random r = new Random();
        int time = r.nextInt(100);
        log.info("waiting for: "+time+" milliseconds...");
        Thread.sleep(time);
        return "We finish on time!";
    }

}

We are going to simulate a task that takes time by grabbing a random integer and then using it to sleep the thread for that time. Instead of String you could return any object you define in the generic type of the Callable interface.

Now we are going to execute that call:

ExecutorService executorService = Executors.newSingleThreadExecutor();
FutureTask <String>futureTask = new FutureTask<String>(new DummyCallback());
executorService.submit(futureTask);
String result = null;
    try {
        result = futureTask.get(50, TimeUnit.MILLISECONDS);
    } catch (InterruptedException|ExecutionException|TimeoutException e) {
        result = e.getClass().toString();
    }
log.info(result);

We are getting an ExecutorService using the Executors newSingleThreadExecutor() method, that gives us an ExecutorService for a single thread, in this example is all we need.

Then we use a FutureTask  to submit and get the result of the ExecutorService, in this case, we are giving the task a 50 milliseconds timeout.

When using this in a real world situation, remember this, the ExecutionException will wrap any exception thrown inside the callable task,  the TimeoutException is going to be thrown if the callable task doesn’t complete on the time we set, and finally, the InterruptedException will be thrown if something interrupts the task being called. Also keep in my mind that you may need to shutdown any resources that you might have opened inside the callable.

This are sample outputs of the code above:

waiting for: 21 milliseconds…
We finish on time!

waiting for: 58 milliseconds…
class java.util.concurrent.TimeoutException

 

Implementing Retries with Spring Retry

Sometimes you need to retry an action if the first time fails, today I will show you a simple way to do this using Spring Retry.

We wil be using the Spring Retry 1.0.3.RELEASE API version, that you can download from the spring repo here, or if you are using maven you can get the dependency like this:

<dependency>
    <groupId>org.springframework.retry</groupId>
    <artifactId>spring-retry</artifactId>
    <version>1.0.3.RELEASE</version>
    <scope>provided</scope>
</dependency>

We are not going to do nothing fancy here, for more complex things please refer to the documentation.

First we need a RetryTemplate object, this object holds all the information needed to make the retries, like how many retries we want to make, in which exceptions we want to retry, how much time we want to wait before the next retry, and so on.

/**
 * Method that creates a RetryTemplate with fixed backOffPeriod
 * @param maxAttempts Number of attempts
 * @param backOffPeriod Time in milliseconds between tries
 * @return
 */
public static RetryTemplate createRetryTemplate(int maxAttempts, long backOffPeriod){
    RetryTemplate retryTemplate = new RetryTemplate();
    SimpleRetryPolicy simpleRetryPolicy = new SimpleRetryPolicy();
    //how many attempts
    simpleRetryPolicy.setMaxAttempts(maxAttempts);

    FixedBackOffPolicy fixedBackOffPolicy = new FixedBackOffPolicy();

    //how much time (in milliseconds) before next attempt
    fixedBackOffPolicy.setBackOffPeriod(backOffPeriod);

    //setting the values
    retryTemplate.setBackOffPolicy(fixedBackOffPolicy);
    retryTemplate.setRetryPolicy(simpleRetryPolicy);
    return retryTemplate;
}

In this example we are using the  SimpleRetryPolicy  to set the max attempts, this means that no matter what happens inside the code that the RetryTemplate will execute, we will retry until one of two things happen, we run out of attempts, or we complete the execution without an exception being thrown.

There is another constructor of SimpleRetryPolicy where we pass a Map of exceptions that will cause retry, but we are trying to keep things simple here.

The FixedBackOffPolicy is used to set the time (in milliseconds) between every attempt.

There’s also an ExponentialBackOffPolicy where we can set besides the  time between attempts, a multiplier, that will increase the time between every attempt, but as I said before, we are trying to keep this simple enough.

Now the most important thing, the piece of code we want to retry, for this example I will use a dummy class.

...
import org.springframework.retry.RetryCallback;
import org.springframework.retry.RetryContext;

public class DummyRetryCallback implements RetryCallback&lt;String&gt;{
    ...

    public String doWithRetry(RetryContext retryContext) throws Exception {
        Random r = new Random();
        int randomNumber = r.nextInt(10);
        log.info("Try number: "+retryContext.getRetryCount()+" random number: "+randomNumber);
        if(randomNumber==4){
            return "We have a four in the try number: "+retryContext.getRetryCount();
        }
        else{
            throw new Exception("no fours for you :(");		
        }
    }

}

As you can see, we need to implement RetryCallback and its doWithRetry method, and we need to decide what will be the return type for the retry (in this case String will do the job).

In this example we get a random number, if that number is four we return the String (in which case there will be no more retries), if not, we throw an exception that will cause another retry (if there are attempts left).

And this is how you execute the retry template:

RetryTemplate retryTemplate = createRetryTemplate(4, 1000);
String result = null;
try {
    result = retryTemplate.execute(new DummyRetryCallback());
} catch (Exception e) {
    result = e.getMessage();
}
log.info(result);

Example outputs:

Try number: 0 random number: 1
Try number: 1 random number: 4
We have a four in the try number: 1

Try number: 0 random number: 5
Try number: 1 random number: 9
Try number: 2 random number: 8
Try number: 3 random number: 8
no fours for you :(

 

There’s a first time for everything

And this week was the first time I got a game on the App Store, the game is called Fall in Cave, I learned a lot while developing this game. 

I will be posting pieces of code that I used in my game that you can use on your projects, for example the way I handle music and sound effects.

Some details of the game:

  • Was developed in Xcode using SpriteKit
  • Graphics were done in aseprite 
  • Music and sound effects are from SoundJay

I was trying to make a game that you can play wherever you are, a “high-score” game, with a retro feel, simple to play but hard to master.

This will not be my only game, even if this one doesn’t get too much attention I will continue making games, because I love doing it. 

Counting Sort

Counting sort is so clever that it blew my mind, it doesn’t even use if clauses, this sorting algorithm doesn’t use comparisons. This algorithm can sort integer elements in the range 0 - k (k being exclusive)  where k it’s a known number. This is a great sorting algorithm when we have a large set of data in a range (0-k). It uses three arrays and has three for loops:

  1. We fill a helper array of size k where every index in the helper array represents an element of the original array, and the value is the number of times that element is present in the original array. For example, if the number 0 appears 4 times in the original array, the index 0 of the helper array will contain a 4.
  2. Using the information we have in the helper array, for every index of the helper array, we count how many elements are less or equal than that index, and we save that value in the corresponding index of the helper array. For example, if the number 0 appears 2 times, and the number 1 appears 3 times, in the helper array in the index 0 we are going to have the value 2, and in the index 1 we are going to have the value 5.
  3. We fill up the result array by grabbing an element of the original array and placing it in it’s correct position on the result array, and every time we do that, we decrement the counter corresponding to that value in the helper array. 

Pseudocode

let arr be an array of integers of range 0-max
let res be an array of integers of the same length that arr
let max be the largest number of arr + 1
let tmp be an array of length max filled with zeros
for i=0 while i=0 k--
    res[tmp[arr[k]]-1] = arr[k]
    tmp[arr[k]] = tmp[arr[k]]-1

Implementations

C (Apple LLVM version 5.1 (clang-503.0.40), compiled with gcc -ansi)

#include <stdio.h>

int main()
{
	int arr[] = {5,2,4,6,1,3,0,5,0,4,2};
	int arrlength = sizeof(arr)/sizeof(arr[0]);
	int res[arrlength];
	int max = 7;
	int tmp[max];
	for(int h = 0; h<max; h++)
	{
		tmp[h] = 0;
	}
	for(int i=0; i<arrlength; i++)
    {
        tmp[arr[i]] = tmp[arr[i]]+1;
	}
   	for(int j=1; j<max; j++)
	{
        tmp[j] = tmp[j] + tmp[j-1];
	}
    for(int k=arrlength-1; k>=0; k--)
	{
		res[tmp[arr[k]]-1] = arr[k];
		tmp[arr[k]] = tmp[arr[k]]-1;
	}
	
	for(int l=0; l<arrlength; l++)
	{
		printf("%d ",res[l]);
	}
	printf("\n");
}

Java 1.7

public class CountingSort{

    public static void countingSort(int arr[], int res[], int max){
        int tmp[] = new int[max];

        for(int i=0; i<arr.length; i++){
            tmp[arr[i]] = tmp[arr[i]]+1;
        }
        for(int j=1; j<max; j++){
            tmp[j] = tmp[j] + tmp[j-1];
        }
        for(int k=arr.length-1; k>=0; k--){
            res[tmp[arr[k]]-1] = arr[k];
            tmp[arr[k]] = tmp[arr[k]]-1;
        }
    }

    public static void main(String []args){
        int array[] = {5,2,4,6,1,3,0,5,0,4,2};
        int result[] = new int[array.length];
        int max = 7;

        CountingSort.countingSort(array,result,max);

        for(int i : result){
            System.out.print(i+" ");
        }
        System.out.println();
    }

}

Python 2.7.5

def counting_sort(arr,res,max):
    tmp = [0]*max
    for i in range(0,len(arr)):
        tmp[arr[i]] = tmp[arr[i]]+1
    for j in range(1,max):
        tmp[j] = tmp[j] + tmp[j-1]
    for k in range(len(arr)-1,-1,-1):
	res[tmp[arr[k]]-1] = arr[k]
	tmp[arr[k]] = tmp[arr[k]]-1

array = [5,2,4,6,1,3,0,5,0,4,2]
result = [0]*len(array)

counting_sort(array,result,7)
print result

Quicksort

This algorithm is often the best choice for sorting, because it’s remarkably efficient on average. It is a divide and conquer algorithm.

  • Divide: We partition the array in two subarrays.
  • Conquer: We sort the two subarrays by making recursive calls to the algorithm.

Example gif from wikipedia

Quicksort example from wikipedia

Quicksort example from wikipedia

Pseudocode (from wikipedia)

quicksort(A, i, k):
    if i < k:
    p := partition(A, i, k)
    quicksort(A, i, p - 1)
    quicksort(A, p + 1, k)

// left is the index of the leftmost element of the subarray
// right is the index of the rightmost element of the subarray (inclusive)
// number of elements in subarray = right-left+1
partition(array, left, right)
    pivotIndex := choose-pivot(array, left, right)
    pivotValue := array[pivotIndex]
    swap array[pivotIndex] and array[right]
    storeIndex := left
    for i from left to right - 1
        if array[i] ≤ pivotValue
            swap array[i] and array[storeIndex]
            storeIndex := storeIndex + 1
    swap array[storeIndex] and array[right]  // Move pivot to its final place
    return storeIndex

let arr be an unsorted array of integers
quicksort(arr,0,arr.length-1)

Implementations

C (Apple LLVM version 5.1 (clang-503.0.40), compiled with gcc -ansi)

#include <stdio.h>

void quicksort(int array[],int left, int right)
{
	if(left < right)
	{
		int q = partition(array,left,right);
		quicksort(array,left,q-1);
		quicksort(array,q+1,right);
	}
}

int partition(int array[],int left, int right)
{
	int x = array[right];
	int i = left - 1;
	for(int j=left; j<right; j++)
	{
		if(array[j] <= x)
		{
			i++;
			int temp = array[i];
			array[i] = array[j];
			array[j] = temp;
		}
	}
	int temp = array[++i];
	array[i] = array[right];
	array[right] = temp;
	return i;
}

int main()
{
	int arr[] = {5,2,4,6,1,3};
	int arrlength = sizeof(arr)/sizeof(arr[0]);
	quicksort(arr,0,arrlength-1);
	for(int i=0; i<arrlength; i++){
		printf("%d ",arr[i]);
	}
	printf("\n");
}

Java 1.7

public class QuickSort{

	public static void quickSort(int []array,int left, int right){
		if(left < right){
			int q = partition(array,left,right);
			quickSort(array,left,q-1);
			quickSort(array,q+1,right);
		}
	}

	public static int partition(int array[],int left,int right){
		int x = array[right];
		int i = left - 1;
		for(int j=left; j<right; j++){
			if(array[j]<=x){
				i++;
				int temp  = array[i];
				array[i] = array[j];
				array[j] = temp;
			}
		}
		int temp = array[++i];
		array[i] = array[right];
		array[right] = temp;
		return i;
	}

	public static void main(String []args){
		int arr[] = {5,2,4,6,1,3};
		QuickSort.quickSort(arr,0,arr.length-1);
		for(int i : arr){
			System.out.print(i+" ");
		}
		System.out.println();
	}
}

Python 2.7.5

def quicksort(array,left,right):
    if left < right:
        q = partition(array,left,right)
        quicksort(array,left,q-1)
        quicksort(array,q+1,right)

def partition(array,left,right):
    x = array[right]
    i = left - 1
    for j in range(left,right):
        if array[j] <= x:
            i = i + 1
	    temp = array[i]
            array[i] = array[j]
            array[j] = temp
    temp = array[i+1]
    array[i+1] = array[right]
    array[right] = temp
    return i + 1

arr = [5,2,4,6,1,3]
quicksort(arr,0,len(arr)-1)
print arr

Selection Sort

In the last post we implemented the Insertion Sort, today’s sorting algorithm is only good for a small number of elements, but it’s slower than the Insertion Sort. 

In Selection Sort we first find the smallest number in the array and exchange it for the first element, then we find the smallest number in the sub array [1,n], an exchange it for the second element, we repeat this until the n – 1 element.

Example gif from wikipedia

Selection sort example from wikipedia

Selection sort example from wikipedia

Pseudocode

let arr be an unsorted array of integers
    for i = 0 while i<arr.length-1 i++
        key = arr[i]
        indexOfSmallest = i;
        for j = i+1 while j<arr.length j++
            if key > arr[j]
                key = arr[j]
                indexOfSmallest = j
        arr[indexOfSmallest] = arr[i]
        arr[i] = key

Implementations

C (Apple LLVM version 5.1 (clang-503.0.40), compiled with gcc -ansi)

#include <stdio.h>
int main()
{
	int arr[] = {5,2,4,6,1,3};
	int arrlength = sizeof(arr)/sizeof(arr[0]);

	for(int i=0; i<arrlength-1; i++)
	{
		int key = arr[i];
		int indexOfSmallest = i;
		for(int j=i+1; j<arrlength; j++)
		{
			if(key>arr[j])
			{
				key = arr[j];
				indexOfSmallest = j;
			}
		}
		arr[indexOfSmallest] = arr[i];
		arr[i] = key;
	}

	for(int k=0; k<arrlength; k++){
		printf("%d ",arr[k]);
	}
	printf("\n");
}

Java 1.7

public class SelectionSort{
	
	public static void main(String []args){
		int arr[] = {5,2,4,6,1,3};

		for(int i=0; i<arr.length-1; i++){
			int key = arr[i];
			int indexOfSmallest = i;
			for(int j=i+1; j<arr.length; j++){
				if(key>arr[j]){
					key = arr[j];
					indexOfSmallest = j;
				}
			}
			arr[indexOfSmallest] = arr[i];
			arr[i] = key;
		}

		for(int i : arr){
			System.out.print(i+" ");
		}
		System.out.println();
	}	

}

Python 2.7.5

arr = [5,2,4,6,1,3]

for i in range(0,len(arr)-1):
    key = arr[i]
    indexOfSmallest = i
    for j in range(i+1,len(arr)):
        if key > arr[j]:
            key = arr[j]
            indexOfSmallest = j
    arr[indexOfSmallest] = arr[i]
    arr[i] = key

print arr

See you on the next post!

Insertion Sort

In this post, I feel like talking about the insertion sort.

In the aforementioned sort, we take an element, we are going to call this element the key. We take the key and compare it to the element in the left, if the element of the left is greater than the key, they exchange places, if they exchanged places then we compare the key to the element in the left (if there is one), if the element on the left is not greater than the key (or if there are no more elements in the left) we take the next element as the key. Rinse and repeat until we run out of elements. The first element we take as the key is the second element.

This algorithm is efficient for sorting a small number of elements.

Example gif from wikipedia

Insertion sort example from wikipedia

Insertion sort example from wikipedia

Pseudocode

let arr be an unsorted array of integers
    for i = 1 while i<arr.length i++
        key = arr[i]
        j = i -1
        while j>=0 and arr[j]>key
            arr[j+1] = arr[j]
            j--
        arr[j+1] = key

Implementations

C (Apple LLVM version 5.1 (clang-503.0.40), compiled with gcc -ansi)

#include<stdio.h>

int main()
{
	int arr[] = {5,2,4,6,1,3};
	int arrlength = sizeof(arr)/sizeof(arr[0]);
	for(int i=1; i<arrlength; i++)
	{
		int key = arr[i];
		int j = i - 1;
		while(j>=0 && arr[j]>key)
		{
			arr[j+1] = arr[j];
			j--;
		}
		arr[j+1] = key;
	}

	for(int k=0; k<arrlength; k++){
		printf("%d ",arr[k]);
	}
	printf("\n");
}

Java 1.7

public class InsertionSort{

	public static void main(String []args){
		int arr[] = new int[]{5,2,4,6,1,3};

		for(int i=1; i <  arr.length; i++){
			int key = arr[i];
			int j = i - 1;
			while(j>=0 && arr[j]>key){
				arr[j+1] = arr[j];
				j--;
			}
			arr[j+1] = key;
		}

		//let's print the sorted array

		for(int i : arr){
			System.out.print(i+" ");
		}
		System.out.println();
	}
}

Python 2.7.5

arr = [5,2,4,6,1,3]

for i in range(1,len(arr)):
    key = arr[i]
    j = i - 1
    while j>=0 and arr[j]>key:
        arr[j+1] = arr[j]
        j = j - 1
    arr[j+1] = key

print arr

Im currently reading Introduction to algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.