Movatterモバイル変換
[0]ホーム
A sorted map type.
Alex Martellialeaxit at yahoo.com
Sat Apr 14 03:48:19 EDT 2001
"Mark Pilgrim" <f8dy at diveintopython.org> wrote in messagenews:B6FD065A.56BE%f8dy at diveintopython.org...> in articleslrn9dbfe5.qmh.apardon at trout.vub.ac.be,apardon at trout.vub.ac.be> atapardon at trout.vub.ac.be wrote on 4/12/01 10:33 AM:>> > Is there a module that provides a sorted map.> >> > What I need is a map type that allow you to visit> > all members in key order. Also the possibility> > to look for the next in line after a search> > would be nice. Is there a module that already ...> separate list). Sorting (key,value) pairs (items) is simplest, but not> fastest.">http://www.activestate.com/ASPN/Python/Cookbook/Recipe/52306>> Article and associated code by Alex Martelli, which, if you're new around> here, means it's definitive.Nope, not necessarily definitive -- that would be so if the timbot or effbothad authored it; I'm the _fallible_ one of the three bots, the one with theHumanFoibles module activated.Anyway, that recipe does not provide optimal code if your typical usagepattern alternates too frequently between inserting/deleting an elementand 'visiting all members in key order'; it focuses on the more typicalusage pattern where bursts of modifications happen for a while, thenbursts of visits, and back again. It re-sorts each time a 'visit' happensafter 1 or more (potential) modifications, so if you have M occurrencesof modify-then-revisit of the N items, runtime is O(M*NlogN). And itgives no help with "look for the next in line after a search" -- the searchruns at dictionary-speed (call it O(1):-), but then you'd have to turnto standard module bisect for the 'next' part (again, a re-sort...).Wrapping nice layers around a hash table for a job that should bedone with a tree has its limits -- at some point, not having the datastructure that WANTS to be there to underly your code leads yousmack into a wall. I think it might be worthwhile looking for a realAVL tree implementation for Python. Sam Rushing has one, and Ithink it's worth exploring; see his summary page of links athttp://www.nightmare.com/software.html, and specifically hisAVL module (ftp://www.nightmare.com/squirl/python-ext/avl/,but I'm having some problem getting to the ftp site right now).Alex
More information about the Python-listmailing list
[8]ページ先頭