Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.soft-sys.math.mathematica > #8623
| From | David Bailey <dave@removedbailey.co.uk> |
|---|---|
| Newsgroups | comp.soft-sys.math.mathematica |
| Subject | Re: How best to implement a hash table in Mathematica |
| Date | 2012-02-19 11:36 +0000 |
| Organization | Steven M. Christensen and Associates, Inc and MathTensor, Inc. |
| Message-ID | <jhqmrr$fbq$1@smc.vnet.net> (permalink) |
| References | <jho21j$5sb$1@smc.vnet.net> |
On 18/02/2012 11:28, Joseph Gwinn wrote:
> I have an application that resembles dictionary lookup, with significant
> rates of collision.
>
> The current approach is to initialize the hash table, a 10^4 element
> list of empty sublists, and then build the table by inserting document
> object id numbers into the correct sublists as indexed by some important
> property of the object. The choice of property varies with application.
> The property may be quantized geographic location, or some attribute of
> the object itself.
>
> When done building the hash table, query consists of reading the sublist
> using an index derived in the same way as for the original building of
> the list. Each sublist may have many entries, and the entries need not
> be numbers.
>
> Anyway, I have a workable approach using
>
> HashList[[index]]=
> Union[Flatten[Join[HashList[[index]],{new object ID}]]]]
>
> as the core update function, but I'm wondering how well this will scale
> to say 10^6 sublists (which may be needed to keep the collisions under
> control with large datasets), and of course if there is a better way in
> Mathematica.
>
> I did look at SparseArrays, but they don't support elements that are
> sublists.
>
> Although this hash table is one dimensional, I have uses for 2D and
> maybe 3D tables, which are very common when one is hashing physical
> location.
>
> Thanks in advance,
>
> Joe Gwinn
>
Before constructing a hash table (other than for pedagogical reasons), I
would try the built in mechanisms of Mathematica. For example, here is a
trivial loop which creates a 'hash table' called hashtable, with values
f[key]:
kk=1;
While[kk < 100000,
hashtable[kk]=f[kk];
kk++;
];
Of course, in this example the keys to the table are just the integers,
but the built-in mechanism will work with keys of any structure.
When a function is defined in this way as lots of individual values,
Mathematica uses techniques (probably hash) to access the values. Try it
and see how efficient it is!
David Bailey
http://www.dbaileyconsultancy.co.uk
Back to comp.soft-sys.math.mathematica | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
How best to implement a hash table in Mathematica Joseph Gwinn <joegwinn@comcast.net> - 2012-02-18 11:28 +0000
Re: How best to implement a hash table in Mathematica Szabolcs Horvát <szhorvat@gmail.com> - 2012-02-19 11:29 +0000
Re: How best to implement a hash table in Mathematica Joseph Gwinn <joegwinn@comcast.net> - 2012-02-20 07:50 +0000
Re: How best to implement a hash table in Mathematica David Bailey <dave@removedbailey.co.uk> - 2012-02-19 11:36 +0000
Re: How best to implement a hash table in Mathematica Joseph Gwinn <joegwinn@comcast.net> - 2012-02-20 07:48 +0000
Re: How best to implement a hash table in Mathematica A Retey <awnl@gmx-topmail.de> - 2012-02-21 11:20 +0000
Re: How best to implement a hash table in Mathematica Joseph Gwinn <joegwinn@comcast.net> - 2012-02-22 10:36 +0000
Re: How best to implement a hash table in Mathematica Szabolcs Horvát <szhorvat@gmail.com> - 2012-02-21 11:21 +0000
Re: How best to implement a hash table in Mathematica Joseph Gwinn <joegwinn@comcast.net> - 2012-02-22 10:35 +0000
Re: How best to implement a hash table in Mathematica Richard Fateman <fateman@cs.berkeley.edu> - 2012-02-19 11:36 +0000
Re: How best to implement a hash table in Mathematica Joseph Gwinn <joegwinn@comcast.net> - 2012-02-20 07:49 +0000
Re: How best to implement a hash table in Mathematica Richard Fateman <fateman@cs.berkeley.edu> - 2012-02-21 11:11 +0000
Re: How best to implement a hash table in Mathematica Joseph Gwinn <joegwinn@comcast.net> - 2012-02-22 10:36 +0000
Re: How best to implement a hash table in Mathematica Leonid Shifrin <lshifr@gmail.com> - 2012-02-22 10:34 +0000
Re: How best to implement a hash table in Mathematica "Nasser M. Abbasi" <nma@12000.org> - 2012-02-23 10:51 +0000
Re: How best to implement a hash table in Mathematica Leonid Shifrin <lshifr@gmail.com> - 2012-02-24 06:00 +0000
csiph-web