Ordering python sets

bearophileHUGS at lycos.com bearophileHUGS at lycos.com
Mon Oct 27 21:18:43 CET 2008


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



More information about the Python-list mailing list