Lie Ryan: >Oh no, the two dict implementation would work _exactly_ the same from the >outside, they are transparently interchangeable. Only the performance >characteristic differs because of the different implementation.<
I don't agree with the general idea. If the operations done by your data structure have different computational complexity, then they are fit for different usages. When you program you must know what computational complexity has each of the operations of your data structyre, otherwise there's no way to know the complexity of your whole program, so instead of programming you are just become a mage that tries magical spells and hopes for the better. So I don't accept so much different data structures to have the same name. That's why I'll never appreciate the Python list type to be named list instead of array, despite it supports more or less all the functions you expect from an abstract list type. Said that, for a high-level language like Python I can see another possible solution. To have a type that contains several kinds of data structures, for example a "dict" that contains a hash implementation, a red-black tree, etc. Such data structure can use a small part of the computational power given to it to collect statistics usages of each object (or each variable, that may contain in succession several ojects of the same type). Such data structure can then at run time adapt dynamically, chosing to use the implementation fitter for the specific usage of each object or variable (the programmer can give hints of course, or sometimes even coerce the usage a specific implementation). (such statistics can also be saved on disk to be used for the successive run of the program, to help them work well from the start too, and not just after a while). If this capability works well in practice, then it can solve the problem you were talking about, I think. I presume data structures in future high-level languages will be quite more able to adapt themselves to their usages. Today it's the second time I talk about future programming languages :-) Bye, bearophile -- http://mail.python.org/mailman/listinfo/python-list
