Matthew Brecknell wrote: > Ivan Miljenovic: > >> As such, I'd like to know if there's any way of storing a an n-by-n >> matrix such that the algorithm/function to get either the rows or the >> columns is less than O(n^2) like transposition is. I did try using an >> Array, but my (admittedly hurried and naive) usage of them took longer >> than a list of lists, was more difficult to manipulate, and wasn't >> required separate inverse functions to row and cols. Also, since I >> need to look all throughout the list of values, it's still O(n^2), but >> this time for both rows and columns. >> > > I'm not sure I see the problem, since any operation that touches all the > elements of a n-by-n matrix will be at least O(n^2). For such an > operation, a transposition should just add a constant factor. > > When you tried using Arrays, I presume you used an array indexed by a > pair (i,j), and just reversed the order of the index pair to switch from > row-wise to column-wise access? It's hard to see how that would slow you > down. Perhaps the slowdown was caused by excessive array copying? > Immutable arrays can be efficient for algorithms that write a whole > array at once, but usually not for algorithms that modify one element at > a time. > > I think you'll need to show specific functions that are performing below > expectation before the list will be able to help. > > For problems like latin squares and sudoku, also try thinking "outside > the matrix". Do you really need to structure the problem in terms of > rows and columns? What about a set of mutually-intersecting sets of > cells? > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > > > i think you might also want to check up on
http://en.wikibooks.org/wiki/Haskell/Hierarchical_libraries/Arrays if you intend to do a significant number of incremental updates, it is my (not particularly well-informed) understanding that you should use either mutable arrays (Data.Array.ST together with runST), or Data.Array.Diff with explicit sequencing. both approaches are discussed in the above wikipedia entry. cheers, v.
signature.asc
Description: OpenPGP digital signature
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
