Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.soft-sys.math.mathematica > #8610
| From | Szabolcs Horvát <szhorvat@gmail.com> |
|---|---|
| Newsgroups | comp.soft-sys.math.mathematica |
| Subject | Re: How best to implement a hash table in Mathematica |
| Date | 2012-02-19 11:29 +0000 |
| Organization | Steven M. Christensen and Associates, Inc and MathTensor, Inc. |
| Message-ID | <jhqmfb$f7i$1@smc.vnet.net> (permalink) |
| References | <jho21j$5sb$1@smc.vnet.net> |
On 2/18/2012 1:28 PM, 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.
>
If you have an application similar to dictionary lookup, have you
considered using the DownValues of a symbol?
dict[_] = Null
dict["key1"] = "value1"
dict["key2"] = "value2"
This is a mutable data structure which might not play very well with
Mathematica's native paradigms, but it is often very useful.
You can also consider using a list of rules:
rules = {"key1" -> "value1", "key2" -> "value2"}
You can build a dispatch table using Dispatch[rules] to make
replacements very fast, but every time you add an element, it will be
necessary to re-build the Dispatch object from the rules, which might
take a while.
--
Szabolcs Horvát
Visit Mathematica.SE: http://mathematica.stackexchange.com/
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