On 03/05/2010 12:45 PM, Steven D'Aprano wrote: > E.g. a trie needs six pointers just to represent the single > key "python": > > '' -> 'p' -> 'y' -> 't' -> 'h' -> 'o' -> 'n' > > while a hash table uses just one: > > -> 'python'
You can argue that had trie beed used as the datatype, there will actually be no need to store the key's string representation; the index of the object in the trie implies the textual representation. Such that, you will still need 6 pointers, but you won't need to store a string object. It will just be: '' -> ptrP -> ptrY -> ptrT -> ptrH -> ptrO -> ptrN and if for some reason the name is needed (perhaps for debugging?); then there could be an algorithm to reverse-map the ptrXs to char. I can imagine that to be implementable if variable names in python be limited to alphanumerics only and probably a select few of symbols. Unicode names makes things difficult though... _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
