Array + memory usage

[Hal Daume]

Someone else already replied with much information.  I figured I'd try
to add a small amount.

Basically, to clarify, the problem is that at every character you read,
you do something like 'arr // list'.  (//) is *not* an O(1) operation as
you might expect.  In fact, it *copies* the entire array.  Why?  Because
if you later reference the old one, it needs to have a "backup" version.
The solution, if you want to use arrays, is basically to use a mutable
state array, like IO(U)Array or ST(U)Array.

However, you might be better off using a different data structure.  An
easy solution would be to use a finite map from Data.FiniteMap.  You'll
incur a little overhead, but then again, the distribution of letters in
natural language text is anything but flat; some you will likely never
see and you're wasting space in your array for these.

Of course, you could use a more informed coding tree based on letter
distributions, but this is probably overkill.

--
 Hal Daume III                                   | hdaume@isi.edu
 "Arrest this man, he talks in maths."           | www.isi.edu/~hdaume


> -----Original Message-----
> From: haskell-admin@haskell.org=20
> [mailto:haskell-admin@haskell.org] On Behalf Of mies
> Sent: Thursday, June 19, 2003 2:11 AM
> To: haskell@haskell.org
> Subject: Array + memory usage
>=20
>=20
> Hello, i'm a haskell newbie, and i'm trying to use arrays for=20
> counting=20
> letters. But when I input a textfile of lets say 100KB the=20
> program uses=20
> 75 M of memory, and I really don;t have a clue where the=20
> problem could=20
> be. I have searched many topics here but I didn't find a solution. I=20
> have made an axample of how i am using the array.
>=20
> module Main where
>=20
> import Array
> import IO
>=20
> main =3D do let fr =3D testUpdater f 100000
>           writeFile "test.txt" (show (fr!155))
>=20
> f :: Array Int Int
> f =3D (array (0,255) [(i, 0) | i <- [0..255]])
>=20
> testUpdater :: Array Int Int -> Int -> Array Int Int=20
> testUpdater fr 0 =3D fr testUpdater fr x =3D testUpdater=20
> ((fr//[(155, fr!(155) + 1)])) (x - 1)
>=20
> updateF :: Array Int Int -> Array Int Int
> updateF x =3D (x//[(155, x!(155) + 1)])
>=20
> Regards, Richard Nieuwenhuis
> rnieuwen@cs.uu.nl
>=20
> _______________________________________________
> Haskell mailing list
> Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
>=20