Vraag Wat zijn betere manieren om element in gesorteerde array in PHP in te voegen


Ik heb onlangs mijn CV naar een bedrijf gestuurd dat PHP-ontwikkelaars inhuurt. Ze sturen me een taak terug om op te lossen, om te kijken of ik al genoeg ervaring heb.

De taak gaat als volgt:

U hebt een array met 10k unieke elementen, gesorteerd afstammeling. Write-functie die deze array genereert en vervolgens drie verschillende functies schrijft die een nieuw element in een array invoegen, op de manier dat na de insert-array nog steeds de afstammeling wordt gesorteerd. Schrijf een code om de snelheid van die functies te meten. U kunt PHP-sorteerfuncties niet gebruiken.

Dus ik heb een functie geschreven om array te genereren en vier functies om nieuw element in te voegen in array.

/********** Generating array (because use of range() was to simple :)): *************/

function generateSortedArray($start = 300000, $elementsNum = 10000, $dev = 30){
    $arr = array();
    for($i = 1; $i <= $elementsNum; $i++){
        $rand = mt_rand(1, $dev);
        $start -= $rand;
        $arr[] = $start; 
    }
    return $arr;
}

/********************** Four insert functions: **************************/

// for loop, and array copying
function insert1(&$arr, $elem){
    if(empty($arr)){
        $arr[] = $elem;
        return true;
    }
    $c = count($arr);
    $lastIndex = $c - 1;
    $tmp = array();
    $inserted = false;
    for($i = 0; $i < $c; $i++){
        if(!$inserted && $arr[$i] <= $elem){
            $tmp[] = $elem;
            $inserted = true;
        }
        $tmp[] = $arr[$i];
        if($lastIndex == $i && !$inserted) $tmp[] = $elem;
    }
    $arr = $tmp;
    return true;
}

// new element inserted at the end of array 
// and moved up until correct place
function insert2(&$arr, $elem){
    $c = count($arr);
    array_push($arr, $elem);
    for($i = $c; $i > 0; $i--){
        if($arr[$i - 1] >= $arr[$i]) break;
        $tmp = $arr[$i - 1];
        $arr[$i - 1] = $arr[$i];
        $arr[$i] = $tmp;
    }
    return true;
}

// binary search for correct place + array_splice() to insert element
function insert3(&$arr, $elem){
    $startIndex = 0;
    $stopIndex = count($arr) - 1;
    $middle = 0;
    while($startIndex < $stopIndex){
        $middle = ceil(($stopIndex + $startIndex) / 2);
        if($elem > $arr[$middle]){
            $stopIndex = $middle - 1;
        }else if($elem <= $arr[$middle]){
            $startIndex = $middle;
        }
    }
    $offset = $elem >= $arr[$startIndex] ? $startIndex : $startIndex + 1; 
    array_splice($arr, $offset, 0, array($elem));
}

// for loop to find correct place + array_splice() to insert
function insert4(&$arr, $elem){
    $c = count($arr);
    $inserted = false;
    for($i = 0; $i < $c; $i++){
        if($elem >= $arr[$i]){
            array_splice($arr, $i, 0, array($elem));
            $inserted = true;
            break;
        }
    }
    if(!$inserted) $arr[] = $elem;
    return true;
}

/*********************** Speed tests: *************************/

// check if array is sorted descending
function checkIfArrayCorrect($arr, $expectedCount = null){
    $c = count($arr);
    if(isset($expectedCount) && $c != $expectedCount) return false;
    $correct = true;
    for($i = 0; $i < $c - 1; $i++){
        if(!isset($arr[$i + 1]) || $arr[$i] < $arr[$i + 1]){
            $correct = false;
            break;
        }
    }
    return $correct;
}
// claculates microtimetime diff
function timeDiff($startTime){
    $diff = microtime(true) - $startTime;
    return $diff;
}
// prints formatted execution time info
function showTime($func, $time){
    printf("Execution time of %s(): %01.7f s\n", $func, $time);
}
// generated elements num
$elementsNum = 10000;
// generate starting point
$start = 300000;
// generated elements random range    1 - $dev
$dev = 50;


echo "Generating array with descending order, $elementsNum elements, begining from $start\n";
$startTime = microtime(true);
$arr = generateSortedArray($start, $elementsNum, $dev);
showTime('generateSortedArray', timeDiff($startTime));

$step = 2;
echo "Generating second array using range range(), $elementsNum elements, begining from $start, step $step\n";
$startTime = microtime(true);
$arr2 = range($start, $start - $elementsNum * $step, $step);
showTime('range', timeDiff($startTime));

echo "Checking if array is correct\n";
$startTime = microtime(true);
$sorted = checkIfArrayCorrect($arr, $elementsNum);
showTime('checkIfArrayCorrect', timeDiff($startTime));

if(!$sorted) die("Array is not in descending order!\n");
echo "Array OK\n";

$toInsert = array();

// number of elements to insert from every range
$randElementNum = 20;

// some ranges of elements to insert near begining, middle and end of generated array
// start value => end value
$ranges = array(
    300000 => 280000,
    160000 => 140000,
    30000 => 0,
);
foreach($ranges as $from => $to){
    $values = array();
    echo "Generating $randElementNum random elements from range [$from - $to] to insert\n";
    while(count($values) < $randElementNum){
        $values[mt_rand($from, $to)] = 1;
    }
    $toInsert = array_merge($toInsert, array_keys($values));
}
// some elements to insert on begining and end of array
array_push($toInsert, 310000);
array_push($toInsert, -1000);

echo "Generated elements: \n";
for($i = 0; $i < count($toInsert); $i++){
    if($i > 0 && $i % 5 == 0) echo "\n";
    printf("%8d, ", $toInsert[$i]);
    if($i == count($toInsert) - 1) echo "\n";
}
// functions to test
$toTest = array('insert1' => null, 'insert2' => null, 'insert3' => null, 'insert4' => null);
foreach($toTest as $func => &$time){
    echo "\n\n================== Testing speed of $func() ======================\n\n";
    $tmpArr = $arr;
    $startTime = microtime(true);
    for($i = 0; $i < count($toInsert); $i++){
        $func($tmpArr, $toInsert[$i]);
    }
    $time = timeDiff($startTime, 'checkIfArraySorted');
    showTime($func, $time);
    echo "Checking if after using $func() array is still correct: \n";
    if(!checkIfArrayCorrect($tmpArr, count($arr) + count($toInsert))){
        echo "Array INCORRECT!\n\n";
    }else{
        echo "Array OK!\n\n";
    }
    echo "Few elements from begining of array:\n";
    print_r(array_slice($tmpArr, 0, 5));

    echo "Few elements from end of array:\n";
    print_r(array_slice($tmpArr, -5));

    //echo "\n================== Finished testing $func() ======================\n\n";
}
echo "\n\n================== Functions time summary    ======================\n\n";
print_r($toTest);

Resultaten zijn hier te vinden: http://ideone.com/1xQ3T 

Helaas kreeg ik slechts 13 van de 30 punten voor deze taak (weet niet hoe deze werd berekend of wat precies in aanmerking werd genomen). Ik kan alleen maar aannemen dat dit komt omdat er betere manieren zijn om nieuw element in gesorteerde array in PHP in te voegen. Ik ben nu een tijdje op zoek naar dit onderwerp maar kon niets goeds vinden. Maby, weet je van een betere aanpak of een paar artikelen over dat onderwerp?

Btw op mijn localhost (PHP 5.3.6-13ubuntu3.6 met Suhosin-Patch, AMD Athlon (tm) II X4 620) insert2() is het snelst, maar op ideone (PHP 5.2.11) insert3() is het snelst. Om het even welke ideeën waarom? Ik veronderstel dat array_splice () op de een of andere manier is afgestemd :).

//BEWERK

Gisteren heb ik er opnieuw over nagedacht en heb ik de betere manier gevonden om inserts te maken. Als je alleen een gesorteerde structuur nodig hebt en een manier om het te herhalen en je eerste zorg de snelheid van invoegbewerking betreft, dan zou de beste keuze de SplMaxHeap-klasse gebruiken. In SplMaxHeap klasse zijn inserts verdomd snel :) Ik heb mijn script aangepast om te laten zien hoe snel inserts zijn. Code is hier: http://ideone.com/vfX98 (ideone heeft php 5.2 dus er zal geen SplMaxHeap-klasse zijn)

Op mijn localhost krijg ik dit soort resultaten:

================== Functions time summary  ======================

           insert1() => 0.5983521938
           insert2() => 0.2605950832
           insert3() => 0.3288729191
           insert4() => 0.3288729191
SplMaxHeap::insert() => 0.0000801086

12
2018-03-01 21:36


oorsprong


antwoorden:


Misschien ben ik het wel, maar misschien zochten ze ook naar leesbaarheid en onderhoudbaarheid?

Ik bedoel, je benoemt je variabelen $arr, en $c en $middle, zonder zelfs de moeite te nemen om de juiste documentatie te plaatsen.

Voorbeeld:

/**
 * generateSortedArray()    Function to generate a descending sorted array
 *
 * @param int $start        Beginning with this number
 * @param int $elementsNum  Number of elements in array
 * @param int $dev          Maximum difference between elements
 * @return array            Sorted descending array.
 */
function generateSortedArray($start = 300000, $elementsNum = 10000, $dev = 30) {
    $arr = array();                             #Variable definition
    for ($i = 1; $i <= $elementsNum; $i++) {    
        $rand = mt_rand(1, $dev);               #Generate a random number
        $start -= $rand;                        #Substract from initial value
        $arr[] = $start;                        #Push to array
    }
    return $arr;
}

3
2018-03-01 21:40