Posts tagged programming

This is something to be very careful of if you need to transfer data between two ruby-based systems using JSON. If you serialize a Time object it will serialize as a string, this means on deserialization it stays as a string

Let me demonstrate:

test_data = {“time” => Time.now}

json = test_data.to_json

# the timestamp looks like this in json “Tue Sep 28 14:37:37 -0400 2010”

results = JSON.parse(json)

results[“time”].is_a?(Time) #false!!! its still a string!

This can cause real problems if used in a real system when timestamps are critical to application logic.

Solutions

1. require ‘json/add/core’

if you use the json-ruby gem, it comes with a set of object extensions, these extensions serialize Time objects in a different way allowing them to be re-cast back to proper time objects during deserialization.

The negative to this is that you are producing very ruby-specific JSON, and you need to make sure you explicitly require these extensions whenever you want to serialize/deserialize which can be tricky.

Here is what a time object would look like using this:

”{"n":364019000,"json_class":"Time","s":1285689344}”

Not pretty.

2. Make time objects integers

This is the easiest and best solution for all involved. Just make them into unix timestamps by calling time.to_i. JSON deserializers in every language know how to parse integers, and unix timestamps are very easy to convert into a time object

Time.at(unix_timestamp)

 This is the first post in my quest to be a better programmer. Quicksort is one of the ‘standard’ sorting algorithms. Its fairly easy to implement, and normally runs fairly quickly. I’ve implemented quicksort in both C and Scheme, although I think my Scheme implementation is more of a pseudo-quicksort due to a reluctance to break from the functional style encouraged by Scheme syntax.

Quicksort Overview

The ‘Partition’ algorithm is at the core of a quicksort implementation, and this partitions an array into groups of ‘less than x’ and ‘more than x’, with x itself being placed inbetween. The final position of x is the value returned by the partition function. In my simple implementation, the choice of x remains constant (either the first or last element). Randomizing this is the main way to increase the worst case speed of this algorithm.

After partitioning the initial input, quicksort recursivly calls itself on the ‘less-than’ and ‘more-than’ groups returned from partition. The result is a chain of recursive calls which continues until quicksort is trying to sort a single number.

Check out Wikipedia to get a more in-depth understanding of quicksort.

Special Property

Quicksort is good because it sorts ‘in-place’. In other words it doesn’t use a secondary array to sort the elements into. This can save a lot of memory, especially if you are sorting a list of complicated data structures which are a few KB each.

My C Implementation

void Quicksort(int A[], int p, int r){
	
	if(p<r){
		int q = Partition(A, p, r);
		Quicksort(A, p, q-1);
		Quicksort(A, q+1, r);
	}
}

int Partition(int A[], int p, int r){
	int j, temp;
	
	int x = A[r];
	int i = p -1;
	
	for(j = p;j<r;j++){
		if(A[j]<= x)
		{
			i++;
			temp = A[i];
			A[i] = A[j];
			A[j] = temp;
		}
	}
	temp = A[r];
	A[r] = A[i +1];
	A[i+1] = temp;
	
	return i+1;

My Scheme Implementation

I think its worth noting that the scheme implementation doesn’t exactly sort ‘in-place’. Instead it recursivly builds up secondary lists then joins them together at the end as the return value instead of moving the elements around in a single list. However the amount of memory used should still be in the order of the number of elements in the input array unlike other sorting algorithms (counting-sort, and bucket-sort come to mind) which use secondary arrays which do not form part of the solution.

(define pHelper (lambda (all chk l m)
                  (cond ((null? all) (cons l (cons chk (cons m '()))))
                        (else
                        (let ((x (car all)))
                          (if (<= x chk) 
                              (pHelper (cdr all) chk (cons x l) m)
                              (pHelper (cdr all) chk l (cons x m))))))))

(define partition (lambda (l)
                      (pHelper (cdr l) (car l) '() '())))



(define quicksort (lambda (l)
                    (cond ((null? l) l)
                          (else
                          (let ((lx (partition l)))
                            (append (quicksort (car lx)) (cons (cadr lx) (quicksort (caddr lx)))))))))