Welcome Guest, Not a member yet? Register   Sign In
Can anyone explain how this usort actually works
#1

Hi all,

I have a function in one of my models that is working  exactly as I wanted it to, I just don't quite understand how it works.

I have read the php.net on usort but am still confounded by it. http://php.net/manual/en/function.usort.php
How does the comparison function help with sorting the entire data set given that it is just working out the difference between two indexes, the mysterious $a and $b?

Code:
usort($search_results,function($a, $b) {
    return $a['search_rank'] - $b['search_rank'];
});

My $search_results is an array created from searching lots of different tables and formatting and amalgamating the results (companies table, people table, projects table etc). The only thing I add is what I call a search_rank which is really just a count of the characters before the search string is first found, using stripos(), so a search for 'Mark' gives a score of 0 for a person named 'Mark Lee', or a score of 3 for the company 'Top Mark Ltd' as an example.

I then sort these rows by this search_rank in the search_results array with the above usort. (This is my attempt at adding a search relevance to the list).

But how is it working? It does work, amazingly well, but how?

The usort uses the callback function $a[]-$b[], but how is that helping usort to sort the entire data set? It is making no sense to me at all and really bugging me out. If anyone can shed any additional light on how usort is using that callback to sort my array I would be very interested to hear.

Thanks in advance for any input or feedback,

Best wishes,

Paul.
Reply
#2

(This post was last modified: 09-28-2015, 12:22 AM by slax0r.)

Hi,

this is pretty simple, is it not?
Quote: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.

So if your mathematical operation results in a result less/equal/greater than zero, your array will be sorted accordingly. If I take
your example, you have the "search_rank" of 0 and 3, and if both results are in your array in that order it means it will return -2 on the first iteration, swapping those two elements. Which can lead to unpredictable results. If you want to sort based on that rank, you should compare the values, not subtract them, as in:
PHP Code:
if ($a["search_rank"] === $b["search_rank"]) { return 0; }
return 
$a["search_rank"] < $b["search_rank"] ? -1

This way your array will be sorted based on rank, from the one with lowest value to the one with highest, if you want it the other way around, just swap the "-1" and "1" in the second line of above code snippet.

Regards
Reply
#3

The term "weight" is often used to describe similar values in sorting algorithms, so I'll use it here as well ...

-1 means that $a has a lower weight than $b
0 means that $a and $b are equal
1 means that $a has a higher weight than $b

Higher weight values are moved in front of the lower weight values in the list, and because you'd eventually have all list items compared to each other, you end up with a sorted list. Smile
Reply
#4

Thank you for those explanations, they help a lot.

So does usort reiterate again and again until the entire list remains unchanged?

If it does it sounds like it might cause some overhead although so far I can't detect any noticeable delay so it must be really fast at it.

Thanks again for the above answers, I really appreciate the explanations.

Best wishes,

Paul.
Reply
#5

usort is basically a 'merge sort' algorithm with guaranteed O(n log n) complexity, where n is the number of elements of an array. How it works is that it splits up the array into the smallest unit, so, 1 element of the array. Then it compares each element with the adjacent list, and merges the values. It is faster than bubble sort on large unsorted lists, but if the list is already sorted, bubble sort will be faster than merge sort.

Here is a good graphical representation on how it works, taken from wiki: https://upload.wikimedia.org/wikipedia/c...-300px.gif
Reply
#6

Aha! Finally I get it. That was an excellent link, thank you.

The other more technical documents I read about it now make more sense too.

What an amazingly clever little function. I shall be using this a lot in the future I suspect.

Thank you all again.

Best wishes,

Paul.
Reply
#7

Well, usort is only useful when you do not care for key association, and you need a special, complex(ish) logic to sort, like in your example, where you are sorting based on a specific key. If you have just a normal [3,5,6,4,2,1,9,8] array, then "asort" will probably be enough. Take a looksy for all the available options: http://php.net/manual/en/array.sorting.php
Reply
#8

I found usort on that very list :-)

I had never used it before and it worked magically. My intention is to make the weighting function more complex over time, but strpos of the search string will do for now.

Currently I am searching projects, cases, companies, tasks, trackers, people, guides and call tables, amalgamating the results into a search results array that has name, link, icon, description and weight indexes for each sub array constructed from the various bits of info in the different tables.

At the moment I am just taking the first 10 results of each table, which is missing relevant info for now, but given the speed of usort I am experimenting with taking the first 100 results and then all results of each table, sorting it, and then cutting it down to size for the page. However I suspect it will get too slow but at the moment the function is so fast that performance seems unaffected.

However, as I said, it is what I am doing right now. I just feel so much better now I actually have some understanding of how usort is actually working.

Apparently the root of this sorting method was invented in the 60's. So many clever people, it constantly amazes me.

Best wishes,

Paul.
Reply
#9

Obviously sorting this straight out of the database would yield the most optimal results.

Granted sometimes SQL queries can get too complicated and sometimes you have to use php to do custom sorts, but more often than not SQL sorting is the way to go.
Practical guide to IgnitedCMS - Book coming soon, www.ignitedcms.com
Reply
#10

(This post was last modified: 11-09-2015, 08:29 AM by PaulD. Edit Reason: minor typo )

Just wanted to add that I found myself today again scratching my head on a different project thinking 'how on earth am I going to sort that (very complicated) array' when I remembered usort and did it in two very short lines of code.

I simply love usort!!!!!!

Just thought I would share that.

:-)
Reply




Theme © iAndrew 2016 - Forum software by © MyBB