Re: [Haskell-cafe] Newbie: Appending arrays?
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? 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? Thanks, Dima On Thu, Jul 10, 2008 at 10:59 PM, Jefferson Heard [EMAIL PROTECTED] wrote: 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 [EMAIL PROTECTED] wrote: 2008/7/10 Dmitri O.Kondratiev [EMAIL PROTECTED]: 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-Sequence.html 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie: Appending arrays?
2008/7/11 Dmitri O.Kondratiev [EMAIL PROTECTED]: 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ï ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] Newbie: Appending arrays?
Hello Chaddai, Friday, July 11, 2008, 4:58:00 PM, you wrote: 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 or http://haskell.org/haskellwiki/Library/ArrayRef for reference -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie: Appending arrays?
How does Data.Sequence http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Sequence.html compares with ArrayRef for appending and accessing arrays efficiently ? On Fri, Jul 11, 2008 at 4:58 PM, Chaddaï Fouché [EMAIL PROTECTED] wrote: 2008/7/11 Dmitri O.Kondratiev [EMAIL PROTECTED]: 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ï ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie: Appending arrays?
2008/7/11 Dmitri O.Kondratiev [EMAIL PROTECTED]: How does Data.Sequence http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Sequence.html 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ï ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie: Appending arrays?
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é [EMAIL PROTECTED] wrote: 2008/7/11 Dmitri O.Kondratiev [EMAIL PROTECTED]: How does Data.Sequence http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Sequence.html 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 [EMAIL PROTECTED] http://www.geocities.com/dkondr ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie: Appending arrays?
This doesn't require any fancy data structures. On Fri, Jul 11, 2008 at 08:07:50PM +0400, Dmitri O.Kondratiev wrote: 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] Instead store this as a list of pairs [([10,6,80,25,6,7], 5), ...] and it'll be easy to write a recursive function that accepts a new vector and either increments the appropriate count or adds the new vector at the end with count 1. I will also need to access vectors at different index in unique array later. Then once you've finished constructing the list, turn it into an array with listArray and use random access into that. Regards, Reid Barton ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie: Appending arrays?
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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie: Appending arrays?
Thanks for your help, guys! I like simple solutions most of all :) On Fri, Jul 11, 2008 at 9:44 PM, Reid Barton [EMAIL PROTECTED] wrote: This doesn't require any fancy data structures. Instead store this as a list of pairs [([10,6,80,25,6,7], 5), ...] and it'll be easy to write a recursive function that accepts a new vector and either increments the appropriate count or adds the new vector at the end with count 1. On Fri, Jul 11, 2008 at 11:32 PM, Dan Weston [EMAIL PROTECTED] wrote: 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. -- Dmitri O. Kondratiev [EMAIL PROTECTED] http://www.geocities.com/dkondr ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Newbie: Appending arrays?
What is the best way to extend array? I would use a list instead of array as it is easy to append, but need to have random access to its elements later. So in fact I need to start with an integer array of size 1. Next I may need to add new elements to this array or modify values of the existing ones. Function: array :: (Ix a) = (a,a) - [(a,b)] - Array a b allows construct an array of a fixed size. How to add more elements to the array later? Thanks! -- Dmitri O. Kondratiev [EMAIL PROTECTED] http://www.geocities.com/dkondr ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie: Appending arrays?
2008/7/10 Dmitri O.Kondratiev [EMAIL PROTECTED]: 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-Sequence.html HTH, -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie: Appending arrays?
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 [EMAIL PROTECTED] wrote: 2008/7/10 Dmitri O.Kondratiev [EMAIL PROTECTED]: 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-Sequence.html 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
