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 use
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 been proved
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 citation for
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 one point out what's wrong
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
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
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
Haskell
To: Don Stewart [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 dictionary allows for update. e.g. the statement
d['a'] = 3
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
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 = fromList
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 which
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
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 slower
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 dictionary
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 the
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
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,
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
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)
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 release
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
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
The above number
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 structure
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: 12 sec
Python: 2.24 sec
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
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´t true
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 wrong with my
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, when you
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 the
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?
If you can
32 matches
Mail list logo
