Archive - Jun 10, 2007

Notes for June 10

in

All my post in my personal blog will be mirrored to facebook, poorly... cause my personal blog have sexy light themes.[facebook is so blue.. so moody]
This blog usually records the comedic materials
so 50% of them are not true
less profanity, more stuff...
please ignore these notes if you found 5 post a week is too much

I know the exact time.
Exact time for me to sit on the plane to China.
14 hours is going to be crazy. Thx for Kuczewski, he is going to lend me a Linux powered laptop.
Hope there is no snake on the plane.

So excited...
I'm going to learn so many thing.
2 Months of intensive learning!
2 Months is enough to create a AP chemistry pick up line.
Fix my teeth.
OK this gets me pissed off.
I don't get dental checks! I don't get any medical yearly checks! I could be sick and my dad will just give me medicines in one of his drawers and hope that will work!
He said, if I got really sick and it is going to kill me, then I should die cause money can not save me. I'm so glad I studied bio.

I might do this:
Be on time for math regents, but, I don't go in the testing place, I just hang out until the 25 minute after the test begins. I would walk into the test without pencil or pen.
"I'm totally Fourier transform the grade into 4.30785586*pi*e^2. word!"

My first facebook application

WhatPulse for Facebook, is the first application I made for Facebook. It gains WhatPulse data and update Facebook profile. The application is for me to keep counting how many keystroke and mouse clicks I have done before I get a girlfriend.
WhatPulse for Facebook
I need 5 users so I can submit it to Facebook's Application directory.
Please help if you have time :)
thx in advance.

Much better than quicksort!

Sorry, the title is misleading , I did not find some algorithm faster than quicksort, in fact, quicksort's lower bound is proven the lowest for any comparison sort algorithm.
Two days ago, a article about using quicksort algorithm in PHP by Tim Koschuetzki caught my eyes.

Koschuetzki was working on an array somewhat like this:

Array
(
    [0] => Array
        (
            [idv11] => 624059d1f8N0
            [adspots] => 2
    )
    [1] => Array
        (
            [idv11] => 67059d1f8N0
            [adspots] => 4
    )
    [2] => Array
        (
            [idv11] => 6759d1f8N0
            [adspots] => 8
    )
)

I took out all the unnecessary keys and values for ease of understanding.
Koschuetzki's goal is to sort the array by the adspots. Since it's a multidimensional array, he can't use sort() provided by PHP, so he creates his own code in PHP and improved his code from Θ(n^2) time into Θ(n log n) time. Good work, but there should be a better way.

Usually, problems like this are taking care by the database, I don't know why Koschuetzki's corporation ask the sorting to be done in PHP. So I come up with something extremely fast.

Below is the simplified version of Koschuetzki's quicksort. I created it by modifying the PHP quicksort implementation posted on wikibook.

function quicksort_by_adspots($array){
        if(!count($array)) return $array;
 
        $k = $array[0]['adspots'];
        $own = $array[0];
        $x = $y = array();
        $count = count($array);
        for($i=1; $i<$count; $i++)
        {
                if($array[$i]['adspots'] <= $k)
                {
                        $x[] = $array[$i];
                }
                else
                {
                        $y[] = $array[$i];
                }
        }
 
        return array_merge(quicksort_by_adspots($x), array($own), quicksort_by_adspots($y));
}

An array of 10000 values = 11 seconds!
Quicksort is fast, even PHP's internal is using quicksort. I believe Radix sort1 are the only generally acceptable faster sorting function. PHP, as ainterpreted language usually can't top other compiled languages.
So, I made a function do the same thing, but using usort().

function usort_by_adspots($array){
	function adcomp($a, $b){
	    if ($a['adspots'] == $b['adspots']) {
	        return 0;
	    }
	    return ($a['adspots'] < $b['adspots']) ? -1 : 1;
	}
	usort($array, "adcomp");
 
	return $array;
}

An array of 10000 values = 0.4 seconds!
Huge performance boost.

I guess this shows the importance of read the manual, I check out the entire manual and read each one of them today and finally found what I need. usort is the last array function in the manual.

  1. 1. LSD Radix sort is a stable sort with Θ(n·k/s) time and Θ(n) memory.
Honey Pot that kill bots