On Tue, 2007-03-20 at 15:09 +1000, Matthew Brecknell wrote:
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.
What I was hoping for was a data structure such that I could directly access the columns of the matrix, rather than having to apply a function to get to them. I didn't think it likely, but then again, a man can dream... ;)
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.
I've attached the code I had written using Arrays. Note that it wasn't the final version of my algorithms, etc. as I continued work a bit further using lists of lists, but the working behind them is just the same (just some extra optimizations, etc. are missing). Here's the way I was pulling out the rows and columns from the array: type Matrix a = IArray MatCoord a type MatCoord = (Int,Int) type Row a = Array Int a getRows :: Matrix a -> [Row a] getRows m = [newRow sr [(c,v) | ((r,c),v) <- vals, r == r'] | r' <- values sr] where sr = fst . snd . bounds $ m vals = assocs m unRows :: [Row a] -> Matrix a unRows = liftM2 newMatrix length addRowValues where addRowValue r = map (\ (c,v) -> ((r,c),v)) . assocs addRowValues = concat . zipWith addRowValue [1..] getCols :: Matrix a -> [Row a] getCols m = [newRow sc [(r,v) | ((r,c),v) <- vals, c == c'] | c' <- values sc] where sc = snd . snd . bounds $ m vals = assocs m unCols :: [Row a] -> Matrix a unCols = liftM2 newMatrix length addColValues where addColValue c = map (\ (r,v) -> ((r,c),v)) . assocs addColValues = concat . zipWith addColValue [1..] And here's an example where I used these functions. What it's doing is storing a list of all possible values for each cell in the matrix, then removing double ups. type Choices = [[Int]] prune :: Matrix Choices -> Matrix Choices prune = pruneBy cols . pruneBy rows where pruneBy (f,f') = f' . map reduce . f reduce :: Row Choices -> Row Choices reduce r = array size (map reducer vals) where size = bounds r vals = assocs r reducer (c,vs) = (c, vs `minus` singles) singles = getSingles r minus :: Choices -> Choices -> Choices xs `minus` ys = if single xs then xs else xs \\ ys
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?
I based my code upon the paper by Richard Bird and later implemented by Graham Hutton. I'm going to be re-writing it a bit, in terms of first generating the "shapes" that the Partial Latin Squares can take, then trying to fill in the numbers. I have considered using a graph-theory approach, but I have no idea where to even start to code it. Fundamentally, I'm trying to generate all Partial Latin Squares that fit a given criteria, so I need the rows/columns to ensure that I have no more than one instance of each value in each row or column. -- Ivan Lazar Miljenovic