On Thu, 2006-05-18 at 06:41, Andrew Brampton wrote: > Hi, > > In the past few weeks I've found the need for a hash table and a container > that gives me O(log) search efficiency. Now I'm aware I can use associative > arrays for my hash table, but I wanted to ensure efficiency. For my O(log) > container I ended up using a sorted array, and a binary search (which I had > to write). > > Now I thought common data structures, and algorithms, like these, and many > others such as Binary Trees, Red/Black Trees and sorting algorithms and so > on would be a useful addition to PHP, or more specifically PEAR, however I > was unable to find any previous classes that provided these structures. > > So I figured I would make a set of containers and algorithms that could be > used in a generic way , and hopefully put this code into PEAR. But before I > start making nice PEAR code, I wanted to ask why nothing like this already > exists? Is it because everyone has been to lazy until now, or is there a > real reason that I'm missing that has made such structures pointless. They more than likely don't exist because PHP's associative array is O(lg n) and so everything else is pretty much just as good, except not quite as good because it will be implemented in PHP whereas the internal associative array is in C. Additionally PHP already provides all you could probably need for sorting. If this is purely for academic fun then I'd say go ahead, but if you are thinking real life applications, then I'd suggest spending your time on algorithms that don't have a just-as-good alternative already implemented internally. BTW, I don't think you can make an O(1) hash table in PHP since even if you succeeded in making a perfect hash then PHP will perform O(lg n) lookup into whatever structure you've made. Cheers, Rob. -- .------------------------------------------------------------. | InterJinn Application Framework - http://www.interjinn.com | :------------------------------------------------------------: | An application and templating framework for PHP. Boasting | | a powerful, scalable system for accessing system services | | such as forms, properties, sessions, and caches. InterJinn | | also provides an extremely flexible architecture for | | creating re-usable components quickly and easily. | `------------------------------------------------------------' -- PHP General Mailing List (http://www.php.net/) To unsubscribe, visit: http://www.php.net/unsub.php
