Re: Re: Sorting times (SOLVED in half the time, hey tedd get your new and improved variant here)

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



German Geek schreef:
> Remember we have copy-on-write in PHP.
> 
> Beat this :P :

for speed it's way faster, slight issue though, it won't
give the expected output for arrays that contain the same
value more than once. not difficult to fix that,
below a new version of the test script with both your
original variant (timeSort4()) and a version that doesn't mislay
duplicates (timeSort5()). both take half the time to run roughly ... nice :-)

<?php


// TEST
ini_set("date.timezone", "Europe/Amsterdam");

$iter = 10000;
$time = array(
    array("1:30pm", "7:30am", "12:30pm"),
    array("1:30pm", "7:30am", "12:30pm", "4:45pm", "8:15am", "11:00pm"),
    array("1:30pm", "7:30am", "12:30pm", "4:45pm", "8:15am", "11:00pm", "4:30am", "6:45am", "12:00pm"),
);

foreach ($time as $t)
    testIt($t, $iter);


// FUNCS

function sortTime1($in_times)
{
    $time = array();
    foreach ($in_times as $t)
        $time[] = strtotime($t);

    sort($time);

    $sort_time = array();
    foreach ($time as $t)
        $sort_time[] = date("g:ia", $t);

    return $sort_time;
}

function timeSort2($in)
{
    static $time = null;

    if (!$time)
        $time = time();

    $now = array_fill(0, count($in), $time);
    $out = array_map("strtotime", $in, $now);
    array_multisort($out, SORT_NUMERIC, SORT_ASC, $in);

    return $in;
}

function timeSort3($a, $b)
{
    static $now = null;

    if (!$now)
        $now = time();

    $a = strtotime($a, $now);
    $b = strtotime($b, $now);
    if ($a == $b)
        return 0;

    return $a < $b ? -1 : 1;
}

function timeSort4($ar)
{
    $stamps = array();
    foreach ($ar as $timeString)
        $stamps[strtotime($timeString)] = $timeString;

    ksort($stamps);
    return array_values($stamps);
}

function timeSort5($ar)
{
    $stamps = array();
    foreach ($ar as $ts)
        if (isset($stamps[$ts]))
            $stamps[strtotime($ts)][1]++;
        else
            $stamps[strtotime($ts)] = array($ts, 1);

    ksort($stamps);

    $ar = array();
    foreach ($stamps as $data)
        for ($i = 0; $i < $data[1]; $i++)
            $ar[] = $data[0];

    return $ar;
}

function testIt($time, $iter)
{
    echo "\nNo. of array items = ", count($time), ", no of iterations = $iter\n-------\n";

    $s = microtime(true);
    for ($i = 0; $i < $iter; $i++)
        timeSort2($time);
    $e = microtime(true);
    echo "timeSort1() ran for ".round($e-$s, 6)." seconds \n";

    $s = microtime(true);
    for ($i = 0; $i < $iter; $i++)
        timeSort2($time);
    $e = microtime(true);
    echo "timeSort2() ran for ".round($e-$s, 6)." seconds \n";

    $s = microtime(true);
    for ($i = 0; $i < $iter; $i++)
        usort($time, "timeSort3");
    $e = microtime(true);
    echo "timeSort3() ran for ".round($e-$s, 6)." seconds \n";

    $s = microtime(true);
    for ($i = 0; $i < $iter; $i++)
        timeSort4($time);
    $e = microtime(true);
    echo "timeSort4() ran for ".round($e-$s, 6)." seconds \n";

    $s = microtime(true);
    for ($i = 0; $i < $iter; $i++)
        timeSort5($time);
    $e = microtime(true);
    echo "timeSort5() ran for ".round($e-$s, 6)." seconds \n";
}

?>


> <?php
> 
> $timeArray = array(/* your string time data */);
> 
> function timeStamps($ar) {
>   $stamps = array();
>   foreach ($ar as $timeString) {
>     $stamps[strtotime($timeString)] = $timeString;
>   }
>   return $stamps;
> }
> 
> function sortTime(&$ar) {
>   $timeStampAr = timeStamps($ar);
>   ksort($timeStampAr); // since the keys are integers, timestamps ksort
> would do the right thing
>   $ar = array_values($timeStampAr);
>   return $ar; //dont really need this but just in case someone prefers to
> use
>                   //it differently or needs a copy
> }
> 
> sortTime($timeArray);
> 
> /* this way the strtotime function is only applied once to each time string
> which is probably the most expensive. And ksort uses the sort algorithm that
> the PHP core programmers regard as the most efficient. I believe quick sort.
> CODE NOT TESTED :P might have minor mistakes but i doubt it :P.*/
> 
> ?>
> Tim-Hinnerk Heuer
> 
> http://www.ihostnz.com
> Fred Allen  - "California is a fine place to live - if you happen to be an
> orange."
> 
> 2009/2/16 Jochem Maas <jochem@xxxxxxxxxxxxx>
> 
>> Shawn McKenzie schreef:
>>> Shawn McKenzie wrote:
>> ...
>>
>>>>> Not tested:
>> no shit.
>>
>>>>> function time_sort($a, $b)
>>>>> {
>>>>>     if (strtotime($a) == strtotime($b)) {
>>>>>         return 0;
>>>>>     }
>>>>>     return (strtotime($a) < strtotime($b) ? -1 : 1;
>>>>> }
>>>>>
>>>>> usort($time, "time_sort");
>>>>>
>>>> Well, I just thought, since the strtotime() uses the current timestamp
>>>> to calculate the new timestamp, if you only give it a time then the
>>>> returned timestamp is today's date with the new time you passed.  If you
>>>> had a large array and the callback started at 23:59:59 then you could
>>>> end up with some times from the date it started and some from the next
>>>> day, which of course would not be sorted correctly with respect to times
>>>> only.  So, this might be better (not tested):
>>>>
>> ditto (as in nice syntax error).
>>
>>>> function time_sort($a, $b)
>>>> {
>>>>     static $now = time();
>>>>
>>>>     if (strtotime($a, $now) == strtotime($b, $now)) {
>>>>         return 0;
>>>>     }
>>>>     return (strtotime($a, $now) < strtotime($b, $now) ? -1 : 1;
>>>> }
>>>>
>>>>
>>> Your best bet above.
>> and G.W.Bush is a socialist.
>>
>> I did a little test, the ultra-fast version offered by McKenzie
>> is really great as long as your array of time strings aren't ever
>> going to be longer than say 3-4 items (with the caveat that you
>> don't use a second argument to strtotime() ... if you do then
>> even with 3 items it's substantially slower).
>>
>> for any reasonable number of items my tests show tedd's version
>> pisses on McKenzies from a great height (note that I actually
>> optimized Mckenzies variant by halfing the number of calls to
>> strtotime()).
>>
>> I added a third variant, as a sort of control, which runs pretty
>> much on par with tedd's version but uses rather less LOC
>> (tedd you might like it as a little example of using array_multisort(),
>> i.e. a way of avoiding writing the double foreach loop in this case)
>>
>> tedd's variant:         sortTime1()
>> McKenzie's variant:     sortTime2()
>> my variant:             sortTime3()
>>
>> sample output from one of my test runs:
>> ===============================================================
>> ===============================================================
>> No. of array items = 3, no of iterations = 10000
>> -------
>> timeSort1() ran for 1.306011 seconds
>> timeSort2() ran for 1.337358 seconds
>> timeSort3() ran for 1.742724 seconds
>>
>> No. of array items = 6, no of iterations = 10000
>> -------
>> timeSort1() ran for 2.647697 seconds
>> timeSort2() ran for 2.475791 seconds
>> timeSort3() ran for 7.268916 seconds
>>
>> No. of array items = 9, no of iterations = 10000
>> -------
>> timeSort1() ran for 3.891894 seconds
>> timeSort2() ran for 3.960463 seconds
>> timeSort3() ran for 18.440713 seconds
>>
>>
>>
>>
>> the test script:
>> ===============================================================
>> ===============================================================
>> <?php
>> // TEST
>> ini_set("date.timezone", "Europe/Amsterdam");
>>
>> $iter = 10000;
>> $time = array(
>>    array("1:30pm", "7:30am", "12:30pm"),
>>    array("1:30pm", "7:30am", "12:30pm", "4:45pm", "8:15am", "11:00pm"),
>>    array("1:30pm", "7:30am", "12:30pm", "4:45pm", "8:15am", "11:00pm",
>> "4:30am", "6:45am", "12:00pm"),
>> );
>>
>> foreach ($time as $t)
>>    testIt($t, $iter);
>>
>>
>> // FUNCS
>>
>> function sortTime1($in_times)
>> {
>>    $time = array();
>>    foreach ($in_times as $t)
>>        $time[] = strtotime($t);
>>
>>    sort($time);
>>
>>    $sort_time = array();
>>    foreach ($time as $t)
>>        $sort_time[] = date("g:ia", $t);
>>
>>    return $sort_time;
>> }
>>
>> function timeSort2($in)
>> {
>>    static $time = null;
>>
>>    if (!$time)
>>        $time = time();
>>
>>    $now = array_fill(0, count($in), $time);
>>    $out = array_map("strtotime", $in, $now);
>>    array_multisort($out, SORT_NUMERIC, SORT_ASC, $in);
>>
>>    return $in;
>> }
>>
>> function timeSort3($a, $b)
>> {
>>    static $now = null;
>>
>>    if (!$now)
>>        $now = time();
>>
>>    $a = strtotime($a, $now);
>>    $b = strtotime($b, $now);
>>    if ($a == $b)
>>        return 0;
>>
>>    return $a < $b ? -1 : 1;
>> }
>>
>> function testIt($time, $iter)
>> {
>>    echo "\nNo. of array items = ", count($time), ", no of iterations =
>> $iter\n-------\n";
>>
>>    $s = microtime(true);
>>    for ($i = 0; $i < $iter; $i++)
>>        timeSort2($time);
>>    $e = microtime(true);
>>    echo "timeSort1() ran for ".round($e-$s, 6)." seconds \n";
>>
>>    $s = microtime(true);
>>    for ($i = 0; $i < $iter; $i++)
>>        timeSort2($time);
>>    $e = microtime(true);
>>    echo "timeSort2() ran for ".round($e-$s, 6)." seconds \n";
>>
>>    $s = microtime(true);
>>    for ($i = 0; $i < $iter; $i++)
>>        usort($time, "timeSort3");
>>    $e = microtime(true);
>>    echo "timeSort3() ran for ".round($e-$s, 6)." seconds \n";
>> }
>>
>> --
>> PHP General Mailing List (http://www.php.net/)
>> To unsubscribe, visit: http://www.php.net/unsub.php
>>
>>
> 


-- 
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php


[Index of Archives]     [PHP Home]     [Apache Users]     [PHP on Windows]     [Kernel Newbies]     [PHP Install]     [PHP Classes]     [Pear]     [Postgresql]     [Postgresql PHP]     [PHP on Windows]     [PHP Database Programming]     [PHP SOAP]

  Powered by Linux