4 ms·

Algorithms in PHP: Deques

85 points by withinboredom 4y ago

craigharley 4y ago
nieve -> naive Just a small typo, article is good. Clear examples and good explanations.
- cProdigy 4y ago
  precisely
- pluc 4y ago
  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.
  - withinboredom 4y ago
    > 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.
    - nkozyra 4y ago
      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.
      - withinboredom 4y ago
        > purpose of wrapping native PHP array mutation in an object is and what overhead that introduces. The purpose is to illustrate what we are doing and setting the stage for later implementations. The overhead is practically unmeasurable unless we are filling the object table with these things (we are not). Property lookup and function calls are pretty darn fast in PHP, especially with JIT enabled.
        nkozyra 4y ago
        > The overhead is practically unmeasurable unless we are filling the object table with these things I think that's typically how one would measure complexity and regardless of JIT I think it introduces some artificial cost.
        withinboredom 4y ago
        Sure, it adds a cost, but it’s infinitesimal compared to the cost of what we are measuring.
  - bkanber 4y ago
    > I get that PHP has a bad rep Have you ever tried reading perl code?
    - rinze 4y ago
      I learned that Perl is a write-only language back in the day, and that really helped.
  - P5fRxh5kUvp2th 4y ago
    or maybe you're being overly critical. PHP aint pretty, but that code doesn't seem unreasonable to me. I certainly wouldn't blink at it outside of the typo.
  - goshx 4y ago
    You are not helping either. Show how it is supposed to be :)
    - vanviegen 4y ago
      That's kind of the whole issue, isn't? Who knows what that kind of code is supposed to mean?
  - firasd 4y ago
    Actually this type of over-usage of ternary operators is not a PHP thing.. it's very prevalent in the JavaScript world
    - jorams 4y ago
      None of those snippets contain a ternary operator. ?? is the Null Coalescing Operator[1] ?-> is the nullsafe operator[2] [1]: https://www.php.net/manual/en/language.operators.comparison.php#language.operators.comparison.coalesce https://www.php.net/manual/en/language.operators.comparison.... [2]: https://www.php.net/manual/en/language.oop5.basic.php#language.oop5.basic.nullsafe https://www.php.net/manual/en/language.oop5.basic.php#langua...
      - firasd 4y ago
        Oh my mistake. Still stuff like 'return a || b' is the kind of thing I see in JS way more than in PHP codebases
        deergomoo 4y ago
        Probably because the Boolean operators in JS return the left or right side of the expression, rather than a Boolean. It was an okay-ish way to get a default/fallback value before JS got a proper coalescing operator.
tyingq 4y ago
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
- Izkata 4y ago
  PHP arrays are associative arrays, it has to update the keys for every remaining value after the first element is deleted.
  - actually_a_dog 4y ago
    That seems like some kind of local fitness minimum in the space of design choices. Even though there certainly are worse choices one could make, I couldn't imagine anything much worse than that would even stand up to any sort of use.
  - TazeTSchnitzel 4y ago
    PHP does at least have an optimised internal representation for arrays with sequential integer keys, where it can avoid having a hash table and just do linear indexing: https://www.npopov.com/2014/12/22/PHPs-new-hashtable-implementation.html#packed-hashtables https://www.npopov.com/2014/12/22/PHPs-new-hashtable-impleme... But a tradeoff in that design is it still has to keep track of keys and update them if you remove stuff from the start of the array. Adding and removing elements at the end is very fast, though.
- johannes1234321 4y ago
  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.
Jwjwhwuwuwhw 4y ago

85 points by withinboredom 4y ago

craigharley 4y ago

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

cProdigy 4y ago
precisely
pluc 4y ago
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.
- withinboredom 4y ago
  > 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.
  - nkozyra 4y ago
    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.
    - withinboredom 4y ago
      > purpose of wrapping native PHP array mutation in an object is and what overhead that introduces. The purpose is to illustrate what we are doing and setting the stage for later implementations. The overhead is practically unmeasurable unless we are filling the object table with these things (we are not). Property lookup and function calls are pretty darn fast in PHP, especially with JIT enabled.
      - nkozyra 4y ago
        > The overhead is practically unmeasurable unless we are filling the object table with these things I think that's typically how one would measure complexity and regardless of JIT I think it introduces some artificial cost.
        withinboredom 4y ago
        Sure, it adds a cost, but it’s infinitesimal compared to the cost of what we are measuring.
- bkanber 4y ago
  > I get that PHP has a bad rep Have you ever tried reading perl code?
  - rinze 4y ago
    I learned that Perl is a write-only language back in the day, and that really helped.
- P5fRxh5kUvp2th 4y ago
  or maybe you're being overly critical. PHP aint pretty, but that code doesn't seem unreasonable to me. I certainly wouldn't blink at it outside of the typo.
- goshx 4y ago
  You are not helping either. Show how it is supposed to be :)
  - vanviegen 4y ago
    That's kind of the whole issue, isn't? Who knows what that kind of code is supposed to mean?
- firasd 4y ago
  Actually this type of over-usage of ternary operators is not a PHP thing.. it's very prevalent in the JavaScript world
  - jorams 4y ago
    None of those snippets contain a ternary operator. ?? is the Null Coalescing Operator[1] ?-> is the nullsafe operator[2] [1]: https://www.php.net/manual/en/language.operators.comparison.php#language.operators.comparison.coalesce https://www.php.net/manual/en/language.operators.comparison.... [2]: https://www.php.net/manual/en/language.oop5.basic.php#language.oop5.basic.nullsafe https://www.php.net/manual/en/language.oop5.basic.php#langua...
    - firasd 4y ago
      Oh my mistake. Still stuff like 'return a || b' is the kind of thing I see in JS way more than in PHP codebases
      - deergomoo 4y ago
        Probably because the Boolean operators in JS return the left or right side of the expression, rather than a Boolean. It was an okay-ish way to get a default/fallback value before JS got a proper coalescing operator.

tyingq 4y ago

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

Izkata 4y ago
PHP arrays are associative arrays, it has to update the keys for every remaining value after the first element is deleted.
- actually_a_dog 4y ago
  That seems like some kind of local fitness minimum in the space of design choices. Even though there certainly are worse choices one could make, I couldn't imagine anything much worse than that would even stand up to any sort of use.
- TazeTSchnitzel 4y ago
  PHP does at least have an optimised internal representation for arrays with sequential integer keys, where it can avoid having a hash table and just do linear indexing: https://www.npopov.com/2014/12/22/PHPs-new-hashtable-implementation.html#packed-hashtables https://www.npopov.com/2014/12/22/PHPs-new-hashtable-impleme... But a tradeoff in that design is it still has to keep track of keys and update them if you remove stuff from the start of the array. Adding and removing elements at the end is very fast, though.
johannes1234321 4y ago
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.

Jwjwhwuwuwhw 4y ago