Tukukkk

My friend got the next test assignment. Implement a class Item as part of a larger simulation of adding and removing items from queue.

The add method adds the number at the end of queue, get method removes first number from the queue and returns it.

class Item

{

    public function __construct(){

    }



    public function add($number){

    }



    public function get(){

    }

}

We tried everything that came to our mind, but the execution time does not fall below 15sec for 50.000 iterations. Does anyone know a better solution to this problem?

Test case:

$n = 50000;



for ($i=0; $i < $n ; $i++) { 

    $item->add("Test".$i);

}



for ($i=0; $i < $n ; $i++) { 

    echo $item->get()."n";

}

Here's what we've tried:

With array_shift:

$this->numbers = $number;

return array_shift($this->numbers);

times elapsed in secs:
22.661945819855 |
23.122117042542 |
21.985857009888 |
22.498090982437

array_shift and array_push:

array_push($this->numbers, $number);

return array_shift($this->numbers);

times elapsed in secs: 25.500070095062 |
22.558148860931 |
21.946757078171 |
22.031461000443

unset:

    array_push($this->numbers, $number);

    $key = key($this->numbers);

    $n = $this->numbers[$key];

    unset($this->numbers[$key]);

    return $n;

times elapsed in secs: 18.401049852371 |
14.445369958878 |
15.184392929077 |
16.063473939896

array_splice:

    array_push($this->numbers, $number);

    $key = key($this->numbers);

    $n = $this->numbers[$key];

    array_splice($this->numbers, $key, 1);

    return $n;

times elapsed in secs: 49.540771007538 |
47.315555810928 |
46.451086997986 |
46.475464820862

SplDoublyLinkedList:

    $this->numbers = new SplDoublyLinkedList();

    $this->numbers->push($passportNumber);

    return $this->numbers->shift();

times elapsed in secs: 18.166617155075 |
17.268024921417 |
15.621854066849 |
18.711433887482

Linked lists:

class ListNode

{

    public $data;

    public $next;

    function __construct($data)

    {

        $this->data = $data;

        $this->next = NULL;

    }

}



class Item

{

    $this->firstNode = null;

    $this->lastNode = null;

    public function add($number)

    {

        $link = new ListNode($number);



        if ($this->firstNode === null) {

            $this->firstNode = &$link;

            $this->lastNode = &$link;

        } else {

            $this->lastNode->next = &$link;

            $this->lastNode = &$link;

        }

    }



    public function get()

    {

        if ($this->firstNode === null) {

            return null;

        }



        $n = $this->firstNode->data;

        $this->firstNode = $this->firstNode->next;



        return $n;

    }

}

times elapsed in secs: 19.694635868073 |
17.934485912323 |
18.973595142365 |
18.013978004456

the main part the time is taken on is the get method and it's array_shift. you can use array_slice instead on 1000 elements for example:

<?php

class Item

{

    protected $numbers = ;



    public function add($number){

        $this->numbers[$number] = true;

    }



    public function get(){

        $x = key($this->numbers);

        unset($this->numbers[$x]);

        return $x;

    }

}



ob_start();



$n = 50000;

$item = new Item();



$start = microtime(true);



for ($i=0; $i < $n ; $i++) { 

    $item->add("Test".$i);

}



echo microtime(true)-$start;

echo "rn";

$start = microtime(true);



for ($i=0; $i < $n ; $i++) { 

    echo $item->get() . "rn";

}



echo microtime(true)-$start;



ob_end_flush();