hash tables

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

hash tables

Dennis Raddle
I want to build a hash table and then freeze it and use it for fast lookup later. Is there a way to build it in IO or ST but freeze it and use it in transparent code later?
D


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: hash tables

David Turner-2
Hi Dennis,

Data.HashMap [1] is my preferred way to do this, which avoids any mucking around in IO at all.

If that doesn't work for you, funnily enough the function you're looking for may well be called `freeze` [2]


[2] https://hackage.haskell.org/package/vector-0.12.0.0/docs/Data-Vector.html#v:freeze

On 27 Jan 2017 05:18, "Dennis Raddle" <[hidden email]> wrote:
I want to build a hash table and then freeze it and use it for fast lookup later. Is there a way to build it in IO or ST but freeze it and use it in transparent code later?
D


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: hash tables

Frank Staals
David Turner <[hidden email]> writes:

> Hi Dennis,
>
> Data.HashMap [1] is my preferred way to do this, which avoids any mucking
> around in IO at all.
>
> If that doesn't work for you, funnily enough the function you're looking
> for may well be called `freeze` [2]
>
> [1]
> https://hackage.haskell.org/package/unordered-containers-0.2.7.2/docs/Data-HashMap-Strict.html
>
> [2]
> https://hackage.haskell.org/package/vector-0.12.0.0/docs/Data-Vector.html#v:freeze
>
> On 27 Jan 2017 05:18, "Dennis Raddle" <[hidden email]> wrote:
>
> I want to build a hash table and then freeze it and use it for fast lookup
> later. Is there a way to build it in IO or ST but freeze it and use it in
> transparent code later?
> D

I've actually wanted this type of operations a few times as well, but
never really found a solution so far. The problem with just using
Data.HashMap is that it does not guarantee the desired query times
(although I'm guessing it would "work well in practice").

It would be awesome if there was some sort of cuckoo-hashing
implementation that you could build in ST (in expected O(n) time or so),
and then freeze as to get O(1) worst case (guaranteed) lookups in pure
code.

--

- Frank
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: hash tables

Gregory Collins-3

On Fri, Jan 27, 2017 at 1:12 AM, Frank Staals <[hidden email]> wrote:
It would be awesome if there was some sort of cuckoo-hashing
implementation that you could build in ST (in expected O(n) time or so),
and then freeze as to get O(1) worst case (guaranteed) lookups in pure
code.

There is a version of cuckoo hashing in the hashtables library that is in ST, but it doesn't do freeze, sorry. I decided not to add freeze -- it would have more than doubled the API footprint for very little benefit.

G
--
Gregory Collins <[hidden email]>

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.