Re: [PHP-DEV] How about implementing more data structures (ie Map, Set)
I don't have much time to work on this now. More next year ! Have ahappy Xmas. On 12/20/2012 09:43 PM, Levi Morrison wrote: As mentioned earlier, I've been working on a library(https://github.com/morrisonlevi/Ardent) with an honest effort to make the data-structures usable in several different programming styles. I've tried several designs, but requiring something to implement a `Comparable` interface turned out to not be a very good way to do things, for several reasons I don't feel like going into at the moment. - I hope you'll take a look at the current Map(https://github.com/morrisonlevi/Ardent/blob/master/src/Ardent/Map.php) and Set(https://github.com/morrisonlevi/Ardent/blob/master/src/Ardent/Set.php) interfaces in my library and see if there is anything you are missing. I'd really love it if you cloned the repository and tried using it in your project. I'm always looking for feedback.
Re: [PHP-DEV] How about implementing more data structures (ie Map, Set)
As mentioned earlier, I've been working on a library(https://github.com/morrisonlevi/Ardent) with an honest effort to make the data-structures usable in several different programming styles. I've tried several designs, but requiring something to implement a `Comparable` interface turned out to not be a very good way to do things, for several reasons I don't feel like going into at the moment. - I hope you'll take a look at the current Map(https://github.com/morrisonlevi/Ardent/blob/master/src/Ardent/Map.php) and Set(https://github.com/morrisonlevi/Ardent/blob/master/src/Ardent/Set.php) interfaces in my library and see if there is anything you are missing. I'd really love it if you cloned the repository and tried using it in your project. I'm always looking for feedback. -- PHP Internals - PHP Runtime Development Mailing List To unsubscribe, visit: http://www.php.net/unsub.php
[PHP-DEV] How about implementing more data structures (ie Map, Set)
Dear all:
I would like to get your feedback on implementing some more data
structure in the PHP core.
Things like Set, Map could be really helpful.
A Set would be an unordered collection with no duplicate elements (same
as in Python)
$setA = new Set();
$setA-append('a');
$setA-append('a');
$setB = new Set();
$setB-append('b');
$setA == $setB;
// A set can hold objects
$set-append($object);
A Map would be an associative array that can hold objects (same as
Python dictionaries)
$map= new Map();
$map[$setA] = 'Hello, world!';
echo $maps[$setB]; // Hello, world !
I can not really help with the implementation, however I could help
defining the API, creating a test suite and docs should this idea be
accepted.
Note: I had to implement this in PHP while working on Automaton, it's
tedious and inefficient.
Thanks for your feedback,
Victor
Re: [PHP-DEV] How about implementing more data structures (ie Map, Set)
On Dec 18, 2012, at 9:43 AM, Victor Berchet vic...@suumit.com wrote:
Dear all:
I would like to get your feedback on implementing some more data structure in
the PHP core.
Things like Set, Map could be really helpful.
A Set would be an unordered collection with no duplicate elements (same as in
Python)
$setA = new Set();
$setA-append('a');
$setA-append('a');
$setB = new Set();
$setB-append('b');
$setA == $setB;
// A set can hold objects
$set-append($object);
A Map would be an associative array that can hold objects (same as Python
dictionaries)
$map= new Map();
$map[$setA] = 'Hello, world!';
echo $maps[$setB]; // Hello, world !
Most of what you're looking for can be accomplished by implementing ArrayAccess
in your own classes, or using the ArrayObject generically like so:
php $obj = new ArrayObject(array());
php $obj-append('some string');
php $obj-append(new ArrayObject(array()));
php var_dump($obj[1]);
class ArrayObject#4 (0) {
}
php var_dump($obj[0]);
string(11) some string
For the duplicate issue you're referring to, you'd need to implement your own
methods for removing (e.g. array_unique).
I can not really help with the implementation, however I could help defining
the API, creating a test suite and docs should this idea be accepted.
Note: I had to implement this in PHP while working on Automaton, it's tedious
and inefficient.
Thanks for your feedback,
Victor
--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP-DEV] How about implementing more data structures (ie Map, Set)
On Tue, Dec 18, 2012 at 3:43 PM, Victor Berchet vic...@suumit.com wrote:
Dear all:
I would like to get your feedback on implementing some more data structure
in the PHP core.
Things like Set, Map could be really helpful.
A Set would be an unordered collection with no duplicate elements (same as
in Python)
$setA = new Set();
$setA-append('a');
$setA-append('a');
$setB = new Set();
$setB-append('b');
$setA == $setB;
// A set can hold objects
$set-append($object);
A Map would be an associative array that can hold objects (same as Python
dictionaries)
$map= new Map();
$map[$setA] = 'Hello, world!';
echo $maps[$setB]; // Hello, world !
I can not really help with the implementation, however I could help
defining the API, creating a test suite and docs should this idea be
accepted.
Note: I had to implement this in PHP while working on Automaton, it's
tedious and inefficient.
Thanks for your feedback,
Victor
Cool !
I recall some people have already talked about that in the past, have you
read about this ?
So, the process is always the same : wait for ppl feedback, write an RFC,
create patches, testdebug, call for vote, etc.. :-)
Julien.P
Re: [PHP-DEV] How about implementing more data structures (ie Map, Set)
On 18/12/12 15:43, Victor Berchet wrote: Dear all: I would like to get your feedback on implementing some more data structure in the PHP core. (...) I think this could be summarised as allow objects as keys for arrays. Which would give the Map behavior. Implementing Set from that is straightforward. -- PHP Internals - PHP Runtime Development Mailing List To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP-DEV] How about implementing more data structures (ie Map, Set)
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 My $0.02 at least, Anthony On Tue, Dec 18, 2012 at 1:09 PM, Ángel González keis...@gmail.com wrote: On 18/12/12 15:43, Victor Berchet wrote: Dear all: I would like to get your feedback on implementing some more data structure in the PHP core. (...) I think this could be summarised as allow objects as keys for arrays. Which would give the Map behavior. Implementing Set from that is straightforward. -- PHP Internals - PHP Runtime Development Mailing List To unsubscribe, visit: http://www.php.net/unsub.php
Re: [PHP-DEV] How about implementing more data structures (ie Map, Set)
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
Re: [PHP-DEV] How about implementing more data structures (ie Map, Set)
Victor, 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. Well, how could you do that? Without implementing object comparison methods at least (which is outside the scope of this discussion)? I could see a type-specific map which knows how to compare the classes, but in general you'd need to defer comparison to the objects themselves (so $obj1 == $obj2 would fire $obj1-compareTo($obj2) === 0)... Unless I've got something confused...
Re: [PHP-DEV] How about implementing more data structures (ie Map, Set)
On 12/18/2012 07:46 PM, Anthony Ferrara wrote: Victor, 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. Well, how could you do that? Without implementing object comparison methods at least (which is outside the scope of this discussion)? I could see a type-specific map which knows how to compare the classes, but in general you'd need to defer comparison to the objects themselves (so $obj1 == $obj2 would fire $obj1-compareTo($obj2) === 0)... Unless I've got something confused... Well let's say that object comparison methods (interface) is part of the details that I owe to this thread.
