QuickSort: comparing Java to PHP

Standard

QuickSort uses a divide and conquer technique to organize the arrays contents. The algorithm runs in:

worst case: O(n2)
best case: O(n log n) (simple partition)
or O(n) (three-way partition and equal keys)
average: O(n log n)

Motivation:

In the debate of Java vs PHP it was asked why use java when many tasks require less code in PHP. The answer while complex boils down to performance. This is a tiny example to show a performance comparison for each language.

The Algorithms

As a additional angle two separate implementations of the quicksort in Java have been added. One will use arrayLists while the other integer array. Additionally, JDK 7 / 8 will ran separately to analyze platform performance.

    
public static void quickSort(ArrayList<Integer> array, int start, int end) {
    
    // Align the left and right starting positions
    int leftPos = start;
    int rightPos = end;
    
    // if there is only one element in the partition, do not do any sorting
    if ((end - start) < 1) {
        return;
    }
    
    int pivot = array.get(start);
    
    // keep scanning because the left and right indecies have not met
    while (rightPos > leftPos) {
        
        while (array.get(leftPos) <= pivot && leftPos <= end && rightPos > leftPos) {
            leftPos++; // start left look for element greater than the pivot
        }
        
        while (array.get(rightPos) > pivot && rightPos >= start && rightPos >= leftPos) {
            rightPos--; // from right look for element not greater than the pivot
        }
        
        if (rightPos > leftPos) {
            swap(array, leftPos, rightPos); // if the left index is still smaller than the right index, swap the corresponding elements
        }
    }
    
    // after the indices have crossed, swap the last element in the left partition with the pivot
    swap(array, start, rightPos);
    
    // quicksort the left partition
    quickSort(array, start, rightPos - 1);
    
    // quicksort the right partition
    quickSort(array, rightPos + 1, end);
}

The PHP implementation uses a straight integer array.

public function quickSort(&$array, $start, $end) {
    
    // Align the left and right starting positions
    $leftPos = $start;
    $rightPos = $end;
    
    // if there is only one element in the partition, do not do any sorting
    if (($end - $start) < 1) {
        return;
    }
    
    $pivot = $array[$start];
    
    // keep scanning because the left and right indecies have not met
    while ($rightPos > $leftPos) {
        
        while ($array[$leftPos] <= $pivot && $leftPos <= $end && $rightPos > $leftPos) {
            $leftPos++; // start left look for element greater than the pivot
        }
        
        while ($array[$rightPos] > $pivot && $rightPos >= $start && $rightPos >= $leftPos) {
            $rightPos--; // from right look for element not greater than the pivot
        }
        
        if ($rightPos > $leftPos) {
            $this->swap($array, $leftPos, $rightPos); // if the left index is still smaller than the right index, swap the corresponding elements
        }
    }
    
    // after the indices have crossed, swap the last element in the left partition with the pivot
    $this->swap($array, $start, $rightPos);
    
    // quicksort the left partition
    $this->quickSort($array, $start, $rightPos - 1);
    
    // quicksort the right partition
    $this->quickSort($array, $rightPos + 1, $end);
}

Each algorithm is fed in X number of random integers. For Java to assure accuracy 50 iterations on the algorithm are performed to determine the run time. PHP is configured for 10 iterations due to the memory limit of 2 gigabytes. While one could argue that the data is inconsistent due to the randomized values, by increasing the iterations it gives a more accurate result.

Results:

[visualizer id=”472″]

I have omitted the PHP 10,000,000 array size test as is such a high number it skews the graph.

Conclusion:

JDK 7 appears to have a slight edge when it comes to arrayLists, however the difference while worth nothing does not conclude performance improvements. Therefore, Java 7 / 8 performance does not differ. As expected PHP performance is considerably worse that Java. PHP is not designed to nest over 100 functions. This can be configured as a variable as described below.

To run your own tests checkout either the PHP or Java repository on Github.

Possible errors:

PHP Fatal error: Maximum function nesting level of ‘100’ reached, aborting!

This error means that you need to increase the allowed number of nested calls. This can be configured by editing the php.ini file.

xdebug.max_nesting_level=200

Tech Specs
Java JDK 8 / 7
PHP 5.5 (2GB memory allocated)
AMD FX 8-core
16gb RAM 1600mhz

Binary search: comparing Java to PHP performance

Standard

Binary search finds the specified key in a given sorted array, then returns it’s position. The algorithm runs in:

worst case: O(log n)
best case: O(1)
average: O(log n)

Motivation:

In the debate of Java vs PHP it was asked why use java when many tasks require less code in PHP. The answer while complex boils down to performance. This is a tiny example to show a performance comparison for each language.

The Algorithms

As a additional angle I have added two separate implementations of the binary search in Java. One will use arrayLists while the other integer array. Additionally, JDK 7 / 8 will ran separately to analyze platform performance.

    
public static int binarySearch(ArrayList<Integer> array, int key) {

        int position, lower = 0, upper = array.size() - 1;

        // To start, find the subscript of the middle position.
        position = (lower + upper) / 2;

        while ((array.get(position) != key) && (lower <= upper)) {
            if (array.get(position) > key) {
                upper = position - 1;
            } else {
                lower = position + 1;
            }
            position = (lower + upper) / 2;
        }

        return ((lower <= upper) ? position : -1);
    }

The PHP implementation uses a straight integer array.

public function binary_search($a, $key) {

	$lo = 0;
	$hi = sizeof($a) - 1;
	$position = (int)(($lo + $hi) / 2);
	while (($a[$position] != $key) && ($lo <= $hi)) {
		if ($a[$position] > $key) {
			$hi = $position - 1;
		} else {
			$lo = $position + 1;
		}

		$position = (int)(($lo + $hi) / 2);
	}

	unset($a, $key);
	return (($lo <= $hi) ? $position : -1);
}

Each algorithm fed in X number of presorted ints. For java to assure accuracy 50 iterations on the algorithm is performed to determine the run time. PHP is configured for 10 iterations due to the memory limit of 2 gigabytes.

Results:

[visualizer id=”394″]

Conclusion:

Java 7 / 8 performance does not differ. An arrayList in has slightly more overhead compared to a pure integer array. As expected PHP performance is considerable worse that Java. PHP is not designed to hold 10 million ints in memory. To make this test work, the memory allocated to php had to be adjusted to 2gb. In conclusion, leave the large data sets to integer arrays in Java, not PHP to have the best performance.

To run your own tests checkout either the PHP or Java repository on Github.

Tech Specs
Java JDK 8 / 7
PHP 5.5 (2GB memory allocated)
AMD FX 8-core
16gb RAM 1600mhz