Algorithms in PHP: Deques

  $ time php -r '$a=array_fill(0,100000,"test");while(array_shift($a)){}' 
  real    0m10.238s
  user    0m10.238s
  sys     0m0.000s

  $ time perl -e 'my @a=("test") x 100000;while(shift(@a)){}'
  real    0m0.027s
  user    0m0.027s
  sys     0m0.000s

  $ time node -e 'a=Array(100000).fill("test");while(a.shift()){}'
  real    0m1.350s
  user    0m1.343s
  sys     0m0.011s

Re: Algorithms in PHP: Deques

#5

Post by pluc » Tue, Sep 13, 2022, 11:39 AM UTC

craigharley wrote: post #2

nieve -> naive Just a small typo, article is good. Clear examples and good explanations.

That code is so bad. Who does this?!

    return ($this->head === 0 && $this->tail === $this->size - 1) || $this->head === $this->tail + 1;

Or this?

     $return = $this->next?->resetPrevious();

Or this!!!

    $this->tail =
            $this->tail?->setNext(new Node($this->tail, null, $value))->next
            ?? $this->head = new Node(null, null, $value);

Or leaves typos in their code?

    elseif ($this->tail === $this->size - 1) {
            $this->tail = 0;just a tiny
        }

I get that PHP has a bad rep but this ain't helping.

Re: Algorithms in PHP: Deques

#6

Post by withinboredom » Tue, Sep 13, 2022, 12:14 PM UTC

pluc wrote: post #5

craigharley wrote: post #2

nieve -> naive Just a small typo, article is good. Clear examples and good explanations.

That code is so bad. Who does this?! return ($this->head === 0 && $this->tail === $this->size - 1) || $this->head === $this->tail + 1; Or this? $return = $this->next?->resetPrevious(); Or this!!! $this->tail = $this->tail?->setNext(new Node($this->tail, null, $value))->next ?? $this->head = new Node(null, null, $value); Or leaves typos in their code? elseif ($this->tail === $this->size - 1) { $this->tail = 0;just a t…

> who does this

Well, I’m doing this for fun, mostly in an illustrative manner. I’m not getting paid for this, nor is anyone reviewing my work. So thanks for volunteering, though your critical analysis could be more constructive.

As to the typos, I suspect it comes from the WordPress editor just being its weird self and perhaps me starting to type in the wrong place, or Grammarly updating the wrong thing. Who knows, but it’s not in the markdown version of this draft.

Re: Algorithms in PHP: Deques

#7

Post by Izkata » Tue, Sep 13, 2022, 12:44 PM UTC

tyingq wrote: post #4

Php's array_shift() does seem unusually slow. $ time php -r '$a=array_fill(0,100000,"test");while(array_shift($a)){}' real 0m10.238s user 0m10.238s sys 0m0.000s $ time perl -e 'my @a=("test") x 100000;while(shift(@a)){}' real 0m0.027s user 0m0.027s sys 0m0.000s $ time node -e 'a=Array(100000).fill("test");while(a.shift()){}' real 0m1.350s user 0m1.343s sys 0m0.011s

PHP arrays are associative arrays, it has to update the keys for every remaining value after the first element is deleted.

Re: Algorithms in PHP: Deques

#8

Post by johannes1234321 » Tue, Sep 13, 2022, 12:51 PM UTC

tyingq wrote: post #4

Php's array_shift() does seem unusually slow. $ time php -r '$a=array_fill(0,100000,"test");while(array_shift($a)){}' real 0m10.238s user 0m10.238s sys 0m0.000s $ time perl -e 'my @a=("test") x 100000;while(shift(@a)){}' real 0m0.027s user 0m0.027s sys 0m0.000s $ time node -e 'a=Array(100000).fill("test");while(a.shift()){}' real 0m1.350s user 0m1.343s sys 0m0.011s

Interesting side effect of PHP's magicfull array, which is an array/vector, a linked list and a dictionary/hashmap in a single data structure and in that case copies all elements on each shift into the new location to keep the indexes starting at zero. If you break up the "array", say with an `unset($a[0]);` after the array_fill, which tells that you don't want "array" behavior, it becomes fast but all elements keep their original index instead of being moved forward.

Re: Algorithms in PHP: Deques

#9

Post by nkozyra » Tue, Sep 13, 2022, 12:51 PM UTC

withinboredom wrote: post #6

pluc wrote: post #5

Earlier quoted context omitted.

That code is so bad. Who does this?! return ($this->head === 0 && $this->tail === $this->size - 1) || $this->head === $this->tail + 1; Or this? $return = $this->next?->resetPrevious(); Or this!!! $this->tail = $this->tail?->setNext(new Node($this->tail, null, $value))->next ?? $this->head = new Node(null, null, $value); Or leaves typos in their code? elseif ($this->tail === $this->size - 1) { $this->tail = 0;just a t…

> who does this Well, I’m doing this for fun, mostly in an illustrative manner. I’m not getting paid for this, nor is anyone reviewing my work. So thanks for volunteering, though your critical analysis could be more constructive. As to the typos, I suspect it comes from the WordPress editor just being its weird self and perhaps me starting to type in the wrong place, or Grammarly updating the wrong thing. Who knows,…

I also wonder what the purpose of wrapping native PHP array mutation in an object is and what overhead that introduces.

I'm with you on being kind in code reviews but one of the canonical examples of sticky bad PHP code is the addslashes top answer on SO for preventing SQL injection. It stayed there for years/decades and hundreds if not thousands of junior devs copied and pasted it.

So there's some risk when we share code that Google can index and possibly elevate.

I think consulting an algorithms book first would give a more formal example that you could work from.

Re: Algorithms in PHP: Deques

#10

Post by bkanber » Tue, Sep 13, 2022, 12:53 PM UTC

pluc wrote: post #5

craigharley wrote: post #2

nieve -> naive Just a small typo, article is good. Clear examples and good explanations.

That code is so bad. Who does this?! return ($this->head === 0 && $this->tail === $this->size - 1) || $this->head === $this->tail + 1; Or this? $return = $this->next?->resetPrevious(); Or this!!! $this->tail = $this->tail?->setNext(new Node($this->tail, null, $value))->next ?? $this->head = new Node(null, null, $value); Or leaves typos in their code? elseif ($this->tail === $this->size - 1) { $this->tail = 0;just a t…

> I get that PHP has a bad rep

Have you ever tried reading perl code?