Re: Q: Efficiency of Array Implementation
Dear Mr. Mechveliani, I thought efficient arrays are impossible in functional language. I'm not sharing this thought... Here is a quote from the Haskell Library Report: \begin{quote} ``Haskell provides indexable arrays, which may be thought of as functions whose domains are isomorphic to contiguous subsets of the integers. Functions restricted in this way can be implemented efficiently; in particular, a programmer may reasonably expect rapid access to the components.'' \end{quote} So we have to organise the data so that to avoid the access by index - as possible. Sure. If possible - ok. Regards, Jan ___ '---|-- | __, _ _ EMail: [EMAIL PROTECTED] | / | / |/ | WWWeb: http://www.uni-passau.de/~laitenbe/ |/\_/|_/ | |_/ /| Laitenberger --(-|-- \|
Re: Q: Efficiency of Array Implementation
Concerning 'rapid access' you found in docs - it is hard to believe this access is as fast as in C array - i mean changing X[i] in array X. Because when this change is done fast, it is a side effect, breaks functionality. I always thought that this is the main cost the functional world pays for the nice functional principles - to think of how to avoid indice in the critical parts of the algorithm. Well, i may mistake ...
Re: Q: Efficiency of Array Implementation
Date: Fri, 19 Feb 1999 09:41:58 +0100 (MET) From: Lennart Augustsson [EMAIL PROTECTED] CC: [EMAIL PROTECTED], [EMAIL PROTECTED], [EMAIL PROTECTED] Concerning 'rapid access' you found in docs - it is hard to believe this access is as fast as in C array - i mean changing X[i] in array X. Because when this change is done fast, it is a side effect, breaks functionality. Extracting values from an array can be as fast as in C. The tricky part is contructing the array. The Haskell Array module provides one way of constructing monolithic arrays, i.e., arrays that are built once and never again modified. But there are other ways, e.g., using ST monad which allows incremental construction of the array. -- Lennart This reminds me of a question I could not solve on my own yet (due to lack of an operational profiler for the most part): Is it possible that ghc knows how to transform Array data structures into destructive arrays in some settings? I had an algorithm with a terrible time complexity and wrote an implementation using purely functional Arrays. Since the runtime was still to bad, I tried ST together with MutableArrays instead, but the runtime got worse. I don't have the time to figure out the details right now, but if you plan to stay interested in them for a longer period, tell me and I will give you more information when I work on the problem again. (It's still possible that it's a bug in my code, however.) -Matthias -- Max-Planck-Institut für Informatik | DFKI [EMAIL PROTECTED] | [EMAIL PROTECTED] http://www.mpi-sb.mpg.de/~fis |
Q: Efficiency of Array Implementation
Hi, I recently noticed in a test program, that updating a table of fixed size (index and entries of type Int) was slower using an Array instead of our AVL implementation. Does anybody know which compiler option I must give on the command line that the Array is translated to a C array? I was using ghc-4.01 without special options. Many thanks in advance, Jan ___ '---|-- | __, _ _ EMail: [EMAIL PROTECTED] | / | / |/ | WWWeb: http://www.uni-passau.de/~laitenbe/ |/\_/|_/ | |_/ /| Laitenberger --(-|-- \|