Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #16640 > unrolled thread

Re: order independent hash?

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: order independent hash? Dan Stromberg <drsalists@gmail.com> - 2011-12-04 21:50 -0800
    Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-05 04:09 -0800
    Re: order independent hash? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-05 04:09 -0800
      Re: order independent hash? Dan Stromberg <drsalists@gmail.com> - 2011-12-05 15:05 -0800

#16640 — Re: order independent hash?

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

On 11/30/11, Neal Becker <ndbecker2@gmail.com> wrote:
> I like to hash a list of words (actually, the command line args of my
> program)
> in such a way that different words will create different hash, but not
> sensitive
> to the order of the words.  Any ideas?
>
> --
> http://mail.python.org/mailman/listinfo/python-list
>

[toc] | [next] | [standalone]

#16652

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. 
  

[toc] | [prev] | [next] | [standalone]

#16653

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. 
  

[toc] | [prev] | [next] | [standalone]

#16695

On 12/5/11, 88888 Dihedral <dihedral88888@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.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web