Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:64347
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: error (pb1.pair.com: domain suumit.com from 98.139.213.129 cause and error)
Message-ID: <50D0B953.8010001@suumit.com>
Date: Tue, 18 Dec 2012 19:43:31 +0100
Reply-To: victor@suumit.com
Organization: Suumit
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/17.0 Thunderbird/17.0
MIME-Version: 1.0
To: Anthony Ferrara <ircmaxell@gmail.com>
CC: =?ISO-8859-1?Q?=C1ngel_Gonz=E1lez?= <keisial@gmail.com>, 
 "internals@lists.php.net" <internals@lists.php.net>
References: <50D08108.1020503@suumit.com> <50D0B162.90006@gmail.com> <CAAyV7nEvU+YgwYYMXbZ3m6gZ6WZORZ37R6C_akJMefN+5j=dvw@mail.gmail.com>
In-Reply-To: <CAAyV7nEvU+YgwYYMXbZ3m6gZ6WZORZ37R6C_akJMefN+5j=dvw@mail.gmail.com>
Content-Type: multipart/alternative;
 boundary="------------040302000003010306050503"
Subject: Re: [PHP-DEV] How about implementing more data structures (ie Map,
 Set)
From: victor@suumit.com (Victor Berchet)

--------------040302000003010306050503
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

I am happy to see some interest in this discussion, I'll try to give 
more details in the coming days.

To clarify, my first example should be:

$setA = new Set();
$setA->append('a');
$setA->append('a');

$setB = new Set();
$setB->append('a'); // 'a' instead of 'b'

$setA == $setB;

Cheers,
Victor

On 12/18/2012 07:32 PM, Anthony Ferrara wrote:
> Guys,
>
> PHP arrays are a great one-size-fits-all data structure. But like all 
> one-size-fits-all <anything>, jack-of-all-trades usually means master 
> of none.
>
> There are definitely benefits to using specific data structures if 
> implemented correctly under the hood.
>
> A good example of this is a Queue. Implemented properly using a 
> Singly-Linked-List or Doubly-Linked-List, inserts are O(1), peeks are 
> O(1) and removals are O(1). Compare that to an array based 
> queue implementation where inserts are O(1) and peeks are O(1) but 
> removals are O(n)... (or inserts and removals are reversed).
>
> For low volume logic, the array can substitute for more custom data 
> structures quite easily. But for needs with more data (or more 
> transactions), there's no replacement for a proper data structure...
>
>
>
> To the original question:
>
> I would love to see not just more data structures, but better designed 
> ones in core.
>
> For example, with SPLStack http://php.net/manual/en/class.splstack.php
> 1. Why the heck does it have unshift() as well as push()? A stack is a 
> One-way-in, one-way-out data structure, why are both exposed?
> 2. Why the heck does it implement ArrayAccess? Again, completely 
> defeats the point of a stack
> 3. Why does it *extend* DLL? A Stack can be implemented with a DLL, 
> but it is *not* a DLL. Huge difference...
>
> Now, there was some discussion by some of us about re-doing the entire 
> spl data structures a while ago. This git repo (PHP) is the evolution 
> of that idea. https://github.com/morrisonlevi/Ardent
>
> Now it's not written with the explicit intent of replacing SPL. It's 
> written in an attempt to try to get the data structures designed 
> right. Then, it may be ported to PECL, and then finally may be 
> proposed to core.
>
>
> As far as MAP, we already have one: 
> http://php.net/manual/en/class.splobjectstorage.php
If you give a closer look to my example, you will notice a difference: 
$map[$setA] and $map[$setB] point to the same storage which I think is 
not possible with SPLObjectStorage.
>
> My $0.02 at least,
>
> Anthony
>


--------------040302000003010306050503--