In article <mailman.1060.1269243742.23598.python-l...@python.org>, Stefan Behnel <stefan...@behnel.de> wrote: >Lawrence D'Oliveiro, 22.03.2010 00:36: >> Terry Reedy wrote: >>> No one has discovered a setting >>> of the internal tuning parameters for which there are no bad patterns >>> and I suspect there are not any such. This does not negate Xavier's >>> suggestion that a code change might also solve your problem. >> >> Could it be that for implementing a structure like a trie as the OP is, >> where a lot of CPU cycles can be spent manipulating the structure, a high- >> level language like Python, Perl or Ruby just gets in the way? > >I would rather say that the specific problem of the trie data structure is >that it has extremely little benefit over other available data structures.
Not true. >There may still be a couple of niches where it makes sense to consider it >as an alternative, but given that dicts are so heavily optimised in Python, >it'll be hard for tries to compete even when written in a low-level language. It depends. If your data is not in nearly sorted order, trees are some of the best mechanisms available. >Remember that the original use case was to load a dictionary from a text >file. For this use case, a trie can be very wasteful in terms of memory and >rather CPU cache unfriendly on traversal, whereas hash values are a) rather >fast to calculate for a string, and b) often just calculated once and then >kept alive in the string object for later reuse. You still have to walk the bucket in a hash map/table. Performance may be orders of magnitude worse than for trees. >> My feeling would be, try to get the language to do as much of the work for >> you as possible. If you canât do that, then you might be better off with a >> lower-level language. > >I agree with the first sentence, but I'd like to underline the word 'might' >in the second. As this newsgroup shows, very often it's enough to look for >a better algorithmic approach first. > >Stefan > -- You want to know who you are? http://oshosearch.net/Convert/search.php Most Osho books on line: http://oshosearch.net
-- http://mail.python.org/mailman/listinfo/python-list