Jump to content
Larry Ullman's Book Forums

Recommended Posts

My question (long winded...sorry!): I'm a little confused at exactly how usort works and what it expects from a user created comparison function. According to PHP.net "The comparison function must return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second."

 

The examples on the same page use the following function to do a very simple numeric comparison:

 

function cmp($a, $b){

if ($a == $b) {

return 0;

}

return ($a < $b) ? -1 : 1;

}

 

This would return either a +ve, -ve or 0 value depending on the comparison result. This is (as PHP.net says in the description above) what usort expects.

 

Your scripts in Chapter 1 (sort.php) use the following much simpler function for numeric comparison:

 

 

function grade_sort ($x, $y) {

return ($x['grade'] < $y['grade']);

}

 

The way I see it this only returns a 1 (+ve) or 0 value (Boolean) as it is a simple "less than" comparison.

 

This would make me think that values which would have returned a -ve return and subsequently be moved in the array using PHP.net's method will return 0 and remain static using your method, and therefore the array would require many more iterations for a complete sort. However, when I scripted both examples (I modified your sort.php script) and had it print the iteration number, comparison details and final returned values as it sorted the array I saw no difference between the number of iterations performed or the values compared. The returned values werek as I expected, where your method returned 0's for everything that didn't match your "less than" comparison and PHP.net's returned all three values, but ultimately it made no difference to how the array was sorted.

 

Can you explain what is happening here? Is usort only concerned with a simple Boolean response despite PHP.net's description that it would prefer 3 types of return? It certainly seems the case...or of course I have the entire theory totally wrong!

 

Thanks, Rich

Link to comment
Share on other sites

Interesting detective work! The main difference is that my example is never testing whether the two values are equal. In the PHP example, the function tests if the two values are equal, if $a is less than $b, and if $b is less than $a, returning a corresponding value for each. In my example, I only test the last two conditions, because if the values are equal, it doesn't matter where they are sorted relative to each other. So in the PHP example, 0 is returned--and nothing happens--if the two values are the same. In my example, 1/true is returned--and nothing happens--if $a is not less than $b.

 

Does that make sense?

Link to comment
Share on other sites

Thanks for the response.

 

So this would imply that usort is actually not concerned with receiving a returned -ve value as would be implied by their description of the cmp_function, and that a 0 value returned is treated by the usort in the same way as a -ve value return. Maybe this is why the changelog mentions the following...

 

4.1.0 A new sort algorithm was introduced. The cmp_function doesn't keep the original order for elements comparing as equal.

 

... because even if the value is equal it is still moved down the array (even if only down through other like values) in the same direction as any compared values that would have received a -ve return. This would explain why there was no difference at all in the results of the two sort functions and would suggest that post v4.1.0 there is never a time in a iteration where nothing happens. A value is always moved somewhere in the array regardless of the result.

 

Does that sound right to you?

 

EDIT:

 

I just run the sort script again using just two equal values and those values do indeed swap places after a single iteration thus confirming that equal values are always moved in the array and do not remain static.

 

 

Array As Is

 

Array

(

[2] => Array

(

[name] => Vance

[grade] => 85.1

)

 

[364] => Array

(

[name] => Steve

[grade] => 85.1

)

 

)

Iteration 1: Steve 85.1 vs. Vance 85.1

Returned Value: 0

Array Sorted By Grade

 

Array

(

[364] => Array

(

[name] => Steve

[grade] => 85.1

)

 

[2] => Array

(

[name] => Vance

[grade] => 85.1

)

 

)

Link to comment
Share on other sites

Just to confirm, you got those results when you changed the function to return 0 for equal, right?

 

In any case, my function is essentially saying only swap the two values if the one is less than the other. I'm not having it swap for equal to or greater than. But, of course, you can change the user defined function to work as you need for your situation.

Link to comment
Share on other sites

That result was generated using your method (code below). The 0 was returned as a result of the equal amounts not satisfying your "less than" comparison, yet the array was still reordered. It seems usort will always perform at least some action during an iteration and no values remain static.

 

 

<?php

 

$students = array (

2 => array ('name' => 'Vance', 'grade' => 85.1),

364 => array ('name' => 'Steve', 'grade' => 85.1)

);

 

function grade_sort ($x, $y) {

static $count = 1;

echo "<p>Iteration $count: {$x['name']} {$x['grade']} vs. {$y['name']} {$y['grade']}</p>\n";

$test = ($x['grade'] < $y['grade']);

printf ('Returned Value: %b', $test);

$count++;

return $test;

 

}

 

echo '<h3>Array As Is</h3><pre>' . print_r($students, 1) . '</pre>';

 

uasort ($students, 'grade_sort');

 

echo '<h3>Array Sorted By Grade</h3><pre>' . print_r($students, 1) . '</pre>';

 

?>

Link to comment
Share on other sites

That is how it appears. This had been bugging me a lot. I couldn't see how your version could produce the same number of iterations per sort as a version that differentiated between 3 different values but this explains why it is so. Sorry to have doubted your code! PHP.net's description and examples appear to be out of date for this new sort method. This being the case your code requires less work per iteration and is more efficient use of code..something which I strive for. It's a curse sometimes!

 

Thanks for helping me see what is going on here. And thanks for writing some great books, by the way!

Link to comment
Share on other sites

It's very common to see this pattern in Java. There you implement the simple interface Comparable which requires a compareTo method. That is basically doing the exact thing as you see here. The problem with PHP sometimes is that you miss these kinds of things. They are not hard to do, but you don't see them that often in PHP.

 

The Comparator interface in Java is also very interesting. From that basic interface, you could make your own sorting algorithms for any object collection. Static functions like Array.sort() and Collections.sort() will allow you to use different Comparator objects to sort different ways. This comes pretty much out of the box with PHP, but you make some sacrifices for this simplicity.

 

If you look at the function naming "cmp", my guess would be that it stands for Comparator. That would maybe give you a better understanding.

Link to comment
Share on other sites

 Share

×
×
  • Create New...