[Haskell-cafe] Re: Incremental array updates
Bulat Ziganshin
bulat.ziganshin at gmail.com
Thu Feb 26 14:02:49 EST 2009
Hello Eugene,
Thursday, February 26, 2009, 5:32:14 PM, you wrote:
look at http://haskell.org/haskellwiki/Library/ArrayRef
it contains reimplementation of arrays library according to Oleg&Simon idea:
- Unboxed arrays now can be used in polymorphic functions, they are defined
for every element type that belongs to the classes Unboxed and HasDefaultValue
(again, look at http://www.haskell.org/pipermail/haskell-cafe/2004-July/006400.html).
You can add new instances to these classes
> STUArray is really a bit tricky to get used with: especially, if you
> do something wrong, the type errors will be rather dreadful.
> However, if you do everything right, it's OK and you sometimes even
> don't need to write the types at all.
> There are a couple of examples here
> http://www.google.com/codesearch?q=runSTUArray
> I also use them a bit in
> http://hackage.haskell.org/cgi-bin/hackage-scripts/package/jarfind
> And here's one more small source where I used it:
> http://hpaste.org/fastcgi/hpaste.fcgi/view?id=1791#a1791 That's
> problem 87 from projecteuler.net.
> 2009/2/26 Daniel Kraft <d at domob.eu>:
>> Daniel Fischer wrote:
>>>
>>> Am Donnerstag, 26. Februar 2009 14:53 schrieb Daniel Kraft:
>>>>
>>>> Hi,
>>>>
>>>> I seem to be a little stuck with incremental array updates... I've got
>>>> an array of "few" (some thousand) integers, but have to do a calculation
>>>> where I incrementally build up the array. For sake of simplicity, for
>>>> now I don't use a State-Monad but simply pass the array as state down
>>>> the recursive calls.
>>>>
>>>> Unfortunatelly, I seem to experience problems with lazyness; when I run
>>>> my program, memory usage goes up to horrific values! The simple program
>>>> below reproduces this; when run on my machine, it uses up about 300 MB
>>>> of real and 300 MB of virtual memory, and the system starts swapping
>>>> like mad! I compiled with ghc --make -O3, ghc version 6.8.3 if that
>>>> matters.
>>>
>>> As Eugene already said, use STUArray (STArray if you need some laziness).
>>> It's much much faster.
>>
>> I'm just reading about it, but didn't find anything except the Haddock
>> documentation... This may need some time to work out :)
>>
>>>> BTW, I tried to make the array update strict using the `seq` as below,
>>>> but with no effect... What am I doing wrong here?
>>>>
>>>> Many thanks,
>>>> Daniel
>>>>
>>>>
>>>>
>>>>
>>>> import Data.Array;
>>>>
>>>>
>>>> arraySize = 1000
>>>> limit = 100000
>>>>
>>>> type MyArray = Array Int Int
>>>>
>>>> emptyArray :: MyArray
>>>> emptyArray = array (0, arraySize - 1) [ (i, 0) | i <- [0 .. arraySize -
>>>> 1]
>>>> ]
>>>>
>>>>
>>>> procOne :: Int -> MyArray -> MyArray
>>>> procOne a cnt
>>>>
>>>> | a > limit = cnt
>>>> | otherwise =
>>>>
>>>> let ind = a `mod` arraySize
>>>> oldcnt = cnt ! ind
>>>> newarr = cnt // [(ind, oldcnt + 1)]
>>>> in
>>>> procOne (a + 1) (newarr `seq` newarr)
>>>
>>> Note that
>>> x `seq` x
>>> is exactly equivalent to just writing x, it will be evaluated if and only
>>> if x is required to be evaluated by something else.
>>>
>>> Try
>>> let ind = a `mod` arraySize
>>> oldcnt = cnt ! ind
>>> newarr = cnt // [(ind,oldcnt+1)]
>>> newcnt = newarr ! ind
>>> in newcnt `seq` procOne (a+1) newarr
>>>
>>> to force newarr to be evaluated, so the old array is eligible for garbage
>>> collection.
>>
>> This was my first attempt at using `seq` for forcing strict evaluation, and
>> I seemingly did it wrong ;)
>>
>> Thanks for all the quick answers!
>>
>> Yours,
>> Daniel
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
--
Best regards,
Bulat mailto:Bulat.Ziganshin at gmail.com
More information about the Haskell-Cafe
mailing list