Two questions. How often does the array change, and how big does it get? It may well be that you just copy it and take the hit, as that'll be cheaper (even in C, incidentally) than any other solution, if it's a short array or if the updates happen rarely. If not, try using Data.Array.Diff and replaceDiffArray. This is usually fairly efficient for most applications. By the way, depending on the type of the data you're putting into these arrays, Data.ByteString might be a good choice as well. On Thu, Jul 10, 2008 at 12:12 PM, Felipe Lessa wrote:

2008/7/10 Dmitri O.Kondratiev :

...

allows construct an array of a fixed size. How to add more elements to the array later?

I can't really answer your question, however I bet that it would require allocating another, bigger array and copying the old elements over, at least from time to time. So you may want to take a look at Data.Sequence[1], supporting O(1) append on both sides and (sort of) O(log i) for accessing the i-th element.

[1] http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Sequen...

HTH,

-- Felipe. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- I try to take things like a crow; war and chaos don't always ruin a picnic, they just mean you have to be careful what you swallow. -- Jessica Edwards

2008/7/11 Dmitri O.Kondratiev :

I don't quite understand how Data.Array.Diff work. I tried this:

...

let arr = listArray (1,3) [1..3] :: DiffArray Int Int

then:

...

replaceDiffArray arr [(1, 777)] array (1,3) [(1,1),(2,777),(3,3)] Why when replacing first element the second one changes?

replaceDiffArray is low-level, nobody should use it, use the normal IArray interface instead. (To answer your question, replaceDiffArray works with low level index, not the Ix class, all array are indexed by 0, 1, .. for it, so 1 is the index of the second element of the array)

and also trying to add 4-th element results in: Prelude Data.Array.Diff> replaceDiffArray arr [(4, 444)] array (1,3) [(1,1),(2,2),(3,3)]

It looks like replaceDiffArray can not be used to add new element to the end of array?

No, the size of a DiffArray can't be changed : DiffArray are just an IArray instance with better performances for update than the classic IArray instance (which copy the entire content on every update...). There are some libraries that allows you to change the size of your array, be aware though that this operation is very costly (in every language). http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ArrayRef -- Jedaï

How does Data.Sequence http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Sequen... compares with ArrayRef for appending and accessing arrays efficiently ? On Fri, Jul 11, 2008 at 4:58 PM, Chaddaï Fouché wrote:

2008/7/11 Dmitri O.Kondratiev :

...

I don't quite understand how Data.Array.Diff work. I tried this:

...

let arr = listArray (1,3) [1..3] :: DiffArray Int Int

then:

...

replaceDiffArray arr [(1, 777)] array (1,3) [(1,1),(2,777),(3,3)] Why when replacing first element the second one changes?

replaceDiffArray is low-level, nobody should use it, use the normal IArray interface instead. (To answer your question, replaceDiffArray works with low level index, not the Ix class, all array are indexed by 0, 1, .. for it, so 1 is the index of the second element of the array)

...

and also trying to add 4-th element results in: Prelude Data.Array.Diff> replaceDiffArray arr [(4, 444)] array (1,3) [(1,1),(2,2),(3,3)]

It looks like replaceDiffArray can not be used to add new element to the end of array?

No, the size of a DiffArray can't be changed : DiffArray are just an IArray instance with better performances for update than the classic IArray instance (which copy the entire content on every update...).

There are some libraries that allows you to change the size of your array, be aware though that this operation is very costly (in every language). http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ArrayRef

-- Jedaï

I need extendable array to store and count unique vectors. I have a file containing vectors presented as strings like: 10, 6, 80, 25, 6, 7 1, 2, 15, 17, 33, 22 21, 34, 56, 78, 91, 2 ... (BTW, what is the best library function to use to convert string of digits into a list or array?) There are two arrays: 1) Array of unique vectors. The first vector red from file starts this array. Next vectors are added to this array if they are sufficiently dissimilar from the already existing in the array. Similarity is computed as euclidean distance between two vectors. 2) Array of counts. Length of this array is equal to the length of array with unique vectors. Thus every vector has a corresponding count. If new vector is similar to some vector already existing in the first array then corresponding count is incremented. For example, array of unique vectors: [[10, 6, 80, 25, 6, 7], [1, 2, 15, 17, 33, 22], [21, 34, 56, 78, 91, 2]] may have a corresponding counts array: [5,1,3] where: 5 tells that my file has 5 vectors similar to vector [10, 6, 80, 25, 6, 7], Only 1 vector [1, 2, 15, 17, 33, 22], and 3 vectors similar to [21, 34, 56, 78, 91, 2] As long as I don't know a priory how many unique vectors my file has, as well as how many similar to these unique others exists - I need to start both arrays with size 0. Next when I find a similar vector I need to increment count at corresponding index in 'counts' array. I will also need to access vectors at different index in unique array later. That's why I need a collection both indexed and able to extend also. I think that Data.Sequence will do for the task, don't you think? On Fri, Jul 11, 2008 at 7:23 PM, Chaddaï Fouché wrote:

2008/7/11 Dmitri O.Kondratiev :

...

How does Data.Sequence

http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Sequen...

...

compares with ArrayRef for appending and accessing arrays efficiently ?

It doesn't since Data.Sequence doesn't use arrays, it uses a custom data structure that allows to do plenty of operations with pretty good asymptotic complexity. Be aware though that the constants aren't that good and that depending on your usage, lists, array or another specialized data structure could be much more efficient.

By comparisons, extending an array is very likely to be much more expensive from time to time than adding some elements to your Data.Sequence. On the other hand the random access would be much faster in an array and even the amortized cost of extending the array may not be much worse than the amortized cost on the Data.Sequence in some cases.

What exactly are you trying to do ?

-- Jedaï

-- Dmitri O. Kondratiev dokondr@gmail.com http://www.geocities.com/dkondr

Dmitri O.Kondratiev wrote:

I need extendable array to store and count unique vectors. I have a file containing vectors presented as strings like: 10, 6, 80, 25, 6, 7 1, 2, 15, 17, 33, 22 21, 34, 56, 78, 91, 2 ... (BTW, what is the best library function to use to convert string of digits into a list or array?)

If you don't need to do error checking on the input syntax, the easiest (and arguably fastest) method is just read: Prelude> let x = "10, 6, 80, 25, 6, 7" Prelude> read ("[" ++ x ++ "]") :: [Int] [10,6,80,25,6,7] For error checking, you can use reads.