From a strictly implementation and computer science point of view how would you classify the Php array datastructure? Is it an associative array? a hash? a dictionary? ... ?
+1
A:
It's a bit difficult to define it in my opinion. Although, I think I would classify it as an associative array since most of the defined operations for an associative array are available on PHP arrays.
martinp
2009-01-27 07:42:46
+8
A:
From the PHP manual:
An array in PHP is actually an ordered map. A map is a type that associates values to keys. This type is optimized for several different uses; it can be treated as an array, list (vector), hash table (an implementation of a map), dictionary, collection, stack, queue, and probably more.
Tom Haigh
2009-01-27 09:52:03
The question was about the implementation. How can one know which operations on a PHP array are O(1) and what the efficiency of other operations is?
Avi
2009-01-27 09:55:38
Hmm, I bet it can't quite behave like my favorite, the dequeue!
tkotitan
2009-03-09 17:25:50
+3
A:
Well, it depends on how you wish to classify it. I'd opt for classification by the performance of operations.
For example, a true array in Computer Science terms has an O(1) lookup time, while a linked list has an O(n) lookup time. Insertion and deletion are O(1) in a linked list while they are O(n) in an array.
I am not sure what the actual performance of a PHP array is, but if you measure a few of the elementary operations on them and compare them with what's expected from the 'true Computer Science datastructures' you should be able to classify it.
eamelink
2009-01-27 10:47:32
Not a bad idea, however hardware optimizations tend to get in the way of algorithmic performance, so its not always trivial, or even possible to determine the Big-O of an implementation, looking at its performance, as cache hits and CPU pipelining stuff screw the results.
Robert Gould
2009-01-27 10:57:36
A:
It depends on what you want to define really. A dictionary or map refers to the behaviour of the datatype, while a hashmap refers to a specific implementation hereof. The term array is a bit tinted - Strictly speaking, it refers to a concrete implementation, whereas a list is a generic term that refers to any array-like datatype. It's however quite common to use array as a synonym for list.
troelskn
2009-01-27 17:04:07