Большая симуляция добавления и удаления элементов из очереди в PHP

Question

Мой друг получил следующее тестовое задание.Реализуйте класс Item как часть большей симуляции добавления и удаления элементов из очереди.

Метод add добавляет число в конец очереди, метод get удаляет первое число из очереди и возвращает его.

class Item
{
    public function __construct(){
    }

    public function add($number){
    }

    public function get(){
    }
}

Мы перепробовали все, что пришло нам в голову, но время выполнения не опускается ниже 15 секунд для 50 000 итераций.Кто-нибудь знает лучшее решение этой проблемы?

Контрольный пример:

$n = 50000;

for ($i=0; $i < $n ; $i++) { 
    $item->add("Test".$i);
}

for ($i=0; $i < $n ; $i++) { 
    echo $item->get()."\n";
}

Вот что мы попробовали:

С array_shift:

$this->numbers[] = $number;
return array_shift($this->numbers);

раз в секундах: 22,661945819855 |23.122117042542 |21,985857009888 |22.498090982437

array_shift и array_push:

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

времени в секундах: 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;

раз в секундах: 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;

раз в секундах: 49.540771007538 |47.315555810928 |46.451086997986 |46.475464820862

SplDoublyLinkedList:

    $this->numbers = new SplDoublyLinkedList();
    $this->numbers->push($passportNumber);
    return $this->numbers->shift();

раз в секундах: 18.166617155075 |17.268024921417 |15.621854066849 |18.711433887482

Связанные списки:

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;
    }
}

раз в секундах: 19.694635868073 |17.934485912323 |18,973595142365 |+18,013978004456

Answer 1

Основная часть, на которую уходит время, - это метод get, и это array_shift.вы можете использовать array_slice вместо 1000 элементов, например:

<?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 "\r\n";
$start = microtime(true);

for ($i=0; $i < $n ; $i++) { 
    echo $item->get() . "\r\n";
}

echo microtime(true)-$start;

ob_end_flush();