Dear all,
I am trying to implement the python-style dictionary in Haskell.
Python dictionary is a data structure that maps one key to one value.
For instance, a python dictionary
d = {'a':1, 'b':2 }
maps key 'a' to 1, 'b' to 2.
Python dictionary allows for update. e.g. the statement
d['a'] = 3
ch
Did you use Unicode in Python?
--
_jsn
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Hello kenny,
Tuesday, November 18, 2008, 1:37:36 PM, you wrote:
> The above number shows that my implementations of python style
> dictionary are space/time in-efficient as compared to python.
thanks, interesting code
1. why you think that your code should be faster? pythob
implementation is
No I do not consider unicode in these implementations.
On Tue, Nov 18, 2008 at 6:43 PM, Jason Dusek <[EMAIL PROTECTED]> wrote:
> Did you use Unicode in Python?
>
> --
> _jsn
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.or
main :: IO ()
main = do { content <- readFile "in.txt"
; let -- change this following type annotation
-- to change different type of the dictionary
-- dict :: DM.Map S.ByteString Int
-- dict :: IM.IntMap Int
dict :: Trie Int
dict = fromLi
Hi Bulat,
> 1. why you think that your code should be faster? pythob
> implementation is probably written in C ince it's one of its core data
> structures
>
I am not hoping that my code should be faster, but at least not as slow as
what it gets.
Basically I am looking for an implementation whic
kenny lu wrote:
Internally, python dictionary is implemented using hash table.
My first attempt is to use Data.HashTable. However it was immediately
abandoned, as I realize the memory usage is unreasonably huge.
Why should a Haskell hash table need more memory then a Python hash
table? I've h
2008/11/18 kenny lu <[EMAIL PROTECTED]>:
> Dear all,
>
> I am trying to implement the python-style dictionary in Haskell.
>
> Python dictionary is a data structure that maps one key to one value.
> For instance, a python dictionary
> d = {'a':1, 'b':2 }
> maps key 'a' to 1, 'b' to 2.
> Python dicti
Hello Alberto,
I cc this to haskell-cafe again.
Alberto G. Corona wrote:
Not so much memory, because data is referentially transparent, the new Map
can point to whole subtrees of the old map that stay the same. is similar
than when a new list is created by prefixing a new element from a old li
The most balanced case may be the insertion of a element in the middle of a
list, but this is far worst than to insert an element in a particular branch
of a tree ( it needs an average of list-lenght/2 element creations while in
a tree needs only (average-branch-length)/2)
I refer to Maps, beca
Which version of GHC and which version of the Data.ByteString library?
There was an inlining bug related to Data.Map /Data.IntMap performance
fixed between the 6.8.x release and the current bytestring release.
In testing, Data.Map with strict bytestring keys matched the python (C
implemented) dict
Dear Don,
I am using GHC 6.8.1
Regards,
Kenny
On Tue, Nov 18, 2008 at 11:33 PM, Don Stewart <[EMAIL PROTECTED]> wrote:
> Which version of GHC and which version of the Data.ByteString library?
> There was an inlining bug related to Data.Map /Data.IntMap performance
> fixed between the 6.8.x relea
Great. Assuming you're following the advice to use bytestrings, please
install the newest bytestring library version, here,
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/bytestring
Data.Map or Data.IntMap with bytestrings should be quite efficient.
(or use a trie if more precisio
2008/11/18 kenny lu <[EMAIL PROTECTED]>:
> Here is a comparison of memory usage
>
> Map : 345 MB
> IntMap : 146 MB
> Trie : 282 MB
> Python : 94 MB
>
> Here is a comparison of execution time (on an intel dual core 2.0G)
>
> Map: 26 sec
> IntMap: 9 sec
> Trie: 12 sec
> Python: 2.24 sec
>
>
>
On Tue, Nov 18, 2008 at 10:37 AM, David Menendez <[EMAIL PROTECTED]> wrote:
> This isn't really a fair comparison. Map, IntMap, and Trie are
> persistent data structures, and Python dictionaries are ephemeral.
> (That is, when you "add" a key to a Map, you actually create a new one
> that shares st
dave:
> 2008/11/18 kenny lu <[EMAIL PROTECTED]>:
> > Here is a comparison of memory usage
> >
> > Map : 345 MB
> > IntMap : 146 MB
> > Trie : 282 MB
> > Python : 94 MB
> >
> > Here is a comparison of execution time (on an intel dual core 2.0G)
> >
> > Map: 26 sec
> > IntMap: 9 sec
> > Trie:
sorry, Dons,
-- Forwarded message --
From: Alberto G. Corona <[EMAIL PROTECTED]>
Date: 2008/11/18
Subject: Re: [Haskell-cafe] implementing python-style dictionary in Haskell
To: Don Stewart <[EMAIL PROTECTED]>
By the way byteStrings are wonderful, but, it isn
On Tue, Nov 18, 2008 at 3:52 PM, Don Stewart <[EMAIL PROTECTED]> wrote:
> dave:
>> 2008/11/18 kenny lu <[EMAIL PROTECTED]>:
>> > The above number shows that my implementations of python style dictionary
>> > are space/time in-efficient as compared to python.
>> >
>> > Can some one point out what's
On Tue, Nov 18, 2008 at 3:46 PM, Luke Palmer <[EMAIL PROTECTED]> wrote:
> On Tue, Nov 18, 2008 at 10:37 AM, David Menendez <[EMAIL PROTECTED]> wrote:
>> This isn't really a fair comparison. Map, IntMap, and Trie are
>> persistent data structures, and Python dictionaries are ephemeral.
>> (That is,
On Tue, Nov 18, 2008 at 12:46 PM, Luke Palmer <[EMAIL PROTECTED]> wrote:
> But when these persistent data structures are used in a
> single-threaded way, why should we not hope for the performance to be
> comparable?
If you can guarantee single-threaded use, then you can just use ST and
implement
On Tue, Nov 18, 2008 at 8:51 PM, Ryan Ingram <[EMAIL PROTECTED]> wrote:
> On Tue, Nov 18, 2008 at 12:46 PM, Luke Palmer <[EMAIL PROTECTED]> wrote:
>> But when these persistent data structures are used in a
>> single-threaded way, why should we not hope for the performance to be
>> comparable?
>
> I
dave:
> On Tue, Nov 18, 2008 at 3:52 PM, Don Stewart <[EMAIL PROTECTED]> wrote:
> > dave:
> >> 2008/11/18 kenny lu <[EMAIL PROTECTED]>:
> >> > The above number shows that my implementations of python style dictionary
> >> > are space/time in-efficient as compared to python.
> >> >
> >> > Can some o
Tillmann Rendel <[EMAIL PROTECTED]> writes:
> Why should a Haskell hash table need more memory then a Python hash
> table? I've heard that Data.HashTable is bad, so maybe writing a good
> one could be an option.
One problem is that Haskell collections are lazy by default. I'm
aware of a few use
Ryan Ingram wrote:
On Tue, Nov 18, 2008 at 12:46 PM, Luke Palmer <[EMAIL PROTECTED]> wrote:
But when these persistent data structures are used in a
single-threaded way, why should we not hope for the performance to be
comparable?
If you can guarantee single-threaded use, then you can just us
On Sat, Nov 22, 2008 at 5:33 AM, Janis Voigtlaender
<[EMAIL PROTECTED]> wrote:
>> You can generally make a persistent data structure with the same
>> asymptotic bounds as the ephemeral structure, ...
>
> I would be very careful with the "generally" here. At least, I am not
> aware that this has bee
Ryan Ingram <[EMAIL PROTECTED]> wrote:
> ...persistent data structures tend to have much worse constant
> factors and those factors translate to a general 2x-3x
> slowdown.
Can you explain why that is, or provide a citation for it?
It's not something I've found easy to Google.
--
_jsn
___
Ryan Ingram wrote:
On Sat, Nov 22, 2008 at 5:33 AM, Janis Voigtlaender
<[EMAIL PROTECTED]> wrote:
You can generally make a persistent data structure with the same
asymptotic bounds as the ephemeral structure, ...
I would be very careful with the "generally" here. At least, I am not
aware that
On Sat, Nov 22, 2008 at 1:20 PM, Jason Dusek <[EMAIL PROTECTED]> wrote:
> Ryan Ingram <[EMAIL PROTECTED]> wrote:
>> ...persistent data structures tend to have much worse constant
>> factors and those factors translate to a general 2x-3x
>> slowdown.
>
> Can you explain why that is, or provide a ci
Hello kenny,
Tuesday, November 18, 2008, 2:34:25 PM, you wrote:
> I am not hoping that my code should be faster, but at least not as slow as
> what it gets.
> Basically I am looking for an implementation which is close to the one in
> python.
well, if haskell will allow to produce code not slo
Hello Tillmann,
Tuesday, November 18, 2008, 2:46:47 PM, you wrote:
> Why should a Haskell hash table need more memory then a Python hash
> table? I've heard that Data.HashTable is bad, so maybe writing a good
> one could be an option.
about Data.HashTable: it uses one huge array to store all th
On Tue, 2008-11-18 at 22:42 +0100, Alberto G. Corona wrote:
> sorry, Dons,
>
> -- Forwarded message --
> From: Alberto G. Corona <[EMAIL PROTECTED]>
> Date: 2008/11/18
> Subject: Re: [Haskell-cafe] implementing python-style dictionary in
> Haskel
On Nov 18, 2008, at 7:03 AM, Bulat Ziganshin wrote:
Hello Tillmann,
Tuesday, November 18, 2008, 2:46:47 PM, you wrote:
Why should a Haskell hash table need more memory then a Python hash
table? I've heard that Data.HashTable is bad, so maybe writing a good
one could be an option.
about Dat
This actually brings up something I was wondering about lately. I
recently stumbled across a language called clojure, which is a
lisp-like that runs on the JVM. The interesting thing is that
mutations go through a transactional mutable reference system, and the
other datastructures are all immuta
One problem is that Haskell collections are lazy by default. I'm
aware of a few use cases where laziness lets you formulate a very
elegant recursive population of a collection, but I think that in
general, strictness is what you want,
While I strongly agree with the gist of your post, I never
34 matches
Mail list logo
