Incrementially updating an array

[Robert Clausecker]

Hi folks!

I have the following problem. As code is most time easier to understand,
let give an example what I try to do in C:

unsigned int i,j;
unsigned int r[100];
for (i = 0; i < 1000000; i++) {
  j = makeResult(); //j is known to be smaller than 100.
  r[j] = r[j] + 1;
}

(My C is poor, so please don't laugh)

Currently I'm using a Data.Map for this, but as the result is bounded in
this area, an array seems to be more appropreate. I don't want to mess
with mutable arrays, but I can't find anything which does the same like
Data.Map.insertWith for arrays in a reasonable way.

In my example, the input comes from a lazy list and is than folded into
the Map by insertWith (+) j 1 r. Is there any nice, quick way to do this
with Arrays without using mutable ones?

Yours, Robert Clausecker


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Henning Thielemann]

On Tue, 28 Dec 2010, Robert Clausecker wrote:

> Hi folks!
>
> I have the following problem. As code is most time easier to understand,
> let give an example what I try to do in C:
>
> unsigned int i,j;
> unsigned int r[100];
> for (i = 0; i < 1000000; i++) {
>  j = makeResult(); //j is known to be smaller than 100.
>  r[j] = r[j] + 1;
> }
>
> (My C is poor, so please don't laugh)
>
> Currently I'm using a Data.Map for this, but as the result is bounded in
> this area, an array seems to be more appropreate. I don't want to mess
> with mutable arrays, but I can't find anything which does the same like
> Data.Map.insertWith for arrays in a reasonable way.

Mutable arrays in ST monad sound like a reasonable choice.

> In my example, the input comes from a lazy list and is than folded into
> the Map by insertWith (+) j 1 r. Is there any nice, quick way to do this
> with Arrays without using mutable ones?

You may attach a one to the list elements and then call Array.accum with
(+). The corresponding function in Data.Map is Data.Map.fromListWith with
(+).

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Ross Paterson]

On Tue, Dec 28, 2010 at 08:46:24PM +0800, Robert Clausecker wrote:

> I have the following problem. As code is most time easier to understand,
> let give an example what I try to do in C:
>
> unsigned int i,j;
> unsigned int r[100];
> for (i = 0; i < 1000000; i++) {
>   j = makeResult(); //j is known to be smaller than 100.
>   r[j] = r[j] + 1;
> }
>
> (My C is poor, so please don't laugh)
>
> Currently I'm using a Data.Map for this, but as the result is bounded in
> this area, an array seems to be more appropreate. I don't want to mess
> with mutable arrays, but I can't find anything which does the same like
> Data.Map.insertWith for arrays in a reasonable way.
>
> In my example, the input comes from a lazy list and is than folded into
> the Map by insertWith (+) j 1 r. Is there any nice, quick way to do this
> with Arrays without using mutable ones?

accumArray is designed for situations like this.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Henning Thielemann]

On Wed, 29 Dec 2010, Robert Clausecker wrote:

> Am Mittwoch, den 29.12.2010, 13:29 +0100 schrieb Henning Thielemann:
>>
>> I don't know, I hope it's doing its best. :-) You might compare speed of
>> Array.accum with a manually written foldl with (//).
>
> At a glance onto it's sourcecode it actually does, but there are
> actually other problems now, as my program now runs out of stack space.
> (The list to accumulate contains about 1000000 elements). I guess it's
> all about that the garbage collector can't handle such things very well.

The pure number of 1000000 elements should not be a problem. You may post
the failing code. I guess it has something to do with:

http://www.haskell.org/haskellwiki/Stack_overflow

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe