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.