On 12/5/11, 88888 Dihedral <dihedral88...@googlemail.com> wrote: > On Monday, December 5, 2011 1:50:08 PM UTC+8, Dan Stromberg wrote: >> Two methods: >> 1) If you need your hash only once in an infrequent while, then save >> the elements in a list, appending as needed, and sort prior to >> hashing, as needed >> >> 2) If you need your hash more often, you could keep your elements in a >> treap or red-black tree; these will maintain sortedness throughout the >> life of the datastructure. >> >> 3) If A bunch of log(n) or n or nlog(n) operations doesn't sound >> appealing, then you might try this one: Create some sort of mapping >> from your elements to the integers. Then just use a sum. This won't >> scatter things nearly as well as a cryptographic hash, but it's very >> fast, because you don't need to reevaluate some of your members as you >> go. >> >> HTH >> > A sorted list can behave like a hash table. This is of O(log(n)) in > accesses > of n items in theory. > > I agree with you a hash key computation method too slow than a list of n > items in accesses for a range of n items should be reloadable. > > But this is not supported in Python yet. > > For tedious trivial jobs of non-heavy computing , I'll opt for easy use.
A sorted list is O(log(n)) for lookups, but O(n) for insertions. If you have a process doing both, the table operations are O(n). A hash table that isn't overfilled is O(1) for lookups, O(1) for insertions. But this is not ordered. Here's a straightforward treap implementation for python, with pure python and cython versions: http://pypi.python.org/pypi/treap/0.995 There's also at least one red-black tree implementation available. -- http://mail.python.org/mailman/listinfo/python-list
