Quoting Udo Stenzel :

paolo.veronelli@gmail.com wrote:

It isn't, but not for the reasons you might suspect. You're using 'nub', which is quadratic, and your 'coupage' is also quadratic because it uses 'lookup' on a list, which is linear, a linear number of times. You can get this down to O(n * log n) if you replace these lists by Data.Map and Data.Set, to get down to O(n) you need arrays there, too, but that would be pointless, because you're also using 'sort', which is already in O(n * log n). The core of the algorithm is clearly linear in the length of its input.

(Btw, putting 'devil' into a state monad doesn't make much sense. I think, ordinary recursion would be more clear. In fact, it's a 'foldl'.)

Ok, I've simplified some code and moved to foldl, to collect the result. I paste new version in case you care give me some moe suggestion. Thanks. Paolino

Paolo Veronelli wrote:

Quoting Paolo Veronelli :

...

I paste new version in case you care give me some moe suggestion.

import Data.Maybe import Data.List import Data.Array.Diff

import System.Environment import Control.Arrow import Control.Monad

import Random

inc l i = l // [(i,l!i + 1)] switch l i = l // [(i,not (l!i))] constArray n v = listArray (0,n-1) (repeat v)

I don't know about performance differences, but I write constArray using the default value I can give to accumArray: constArray n v = accumArray (const) v (0,n-1) [] where "(const)" might as well be "(undefined)" or "(error "unused")"

data Folding = Folding {clusters :: [(Int,Int)], remi :: Int, colsCount :: DiffArray Int Int ,rowsCheck :: DiffArray Int Bool}

result (Folding cs _ _ _) = cs

rcluster ls d s = let devil s@(Folding cs r hs fs) l@(row,col) = let ns = s { clusters = (l:cs), rowsCheck = switch fs row, colsCount = inc hs col } rowtest | c < d = ns | (c == d) && (r > 0) = ns { remi = r - 1 } | otherwise = s where c = hs ! col in if (not (fs ! row)) then rowtest else s in foldl devil s ls

I cannot tell by a quick glance, but you may want foldl' instead of foldl here.

mcluster :: (Int,Int) -> [(Int,Int)] -> [(Int,[Int])] mcluster (lr,lc) ls = let (k,r) = divMod lr lc start = Folding{clusters = [],remi = r,colsCount = constArray lc 0,rowsCheck = constArray lr False } cs = result $ rcluster ls k start in map collapse . groupBy (comp fst (==)) . sort . map swap $ cs where comp f g x y = (f x) `g` (f y) swap = snd &&& fst collapse = (head &&& unzip) >>> (fst *** snd)

"snd.unzip" is better written as "map snd" so this is collapse = (fst.head &&& map snd) which is identical to the pointful collapse x@((a,_):_) = (a,map snd x)

cluster :: (Ord b) => (a -> a -> b) -> [a] -> [a] -> [(a,[a])] cluster fxy xs ys = let mkArray (l,xs) = (listArray :: (Int,Int) -> [e] -> DiffArray Int e) (0,l-1) xs xls = mkArray (lc,xs) yls = mkArray (rc,ys) (lc,rc) = (length xs,length ys) in map ((yls !) *** map (xls !)) (mcluster (lc,rc) (snd.unzip.sort $ delta))

"snd.unzip" is better written as "map snd" Do you need the "sort $ delta" to sort the snd field as well as the fst? If not then using "sortBy (comp fst compare)" might be clearer (and may be faster or slower).

where delta = [(fxy x y,(n,m))|(n,x) <- zip [0..] xs, (m,y) <- zip [0..] ys]

I don't know if it matters, but "zip [0..] xs" is the same as "assocs xls" and the same for ys/yls. And now something slightly bizarre occurs to me. The list "map swap delta" looks perfect to initialize a two dimensional Array to cache the fxy x y values you pre-compute for the sorting. Rather than form (n*m) pairs you could form a single unboxed n by m Array: deltaArray :: UArray (Int,Int) Int -- Unboxed for efficiency deltaArray = listArray ((0,0),(lc,rc)) [fxy x y | x <- xs, y <- ys] delta :: [(Int,Int)] delta = sortBy (comp (deltaArray!) compare) deltaArray.indices If you only need to sort by the fst field, i.e. the (fxy x y), then this is sufficient and you can call "(mcluster (lc,rc) delta)". If you needed delta sorted by both fields, then a more complicated function to sortBy is needed: delta = sortBy (\nm1 nm2 -> compare (deltaArray!nm1) (deltaArray!nm2) `mappend` compare nm1 nm2) deltaArray.indices The `mappend` depends on the "instance Monoid Ordering" and "import Data.Monoid" and is a great way to chain comparisons.

-- call it with 2 args, the number ov values and the number of clusters -- <prog> 101 10 will cluster 101 values in 10 clusters

points m n = do gen <- getStdGen return $ splitAt n (take (m + n) (randomRs (0,100::Int) gen))

test1 = do args <- getArgs return $ map read args :: IO [Int]

main = do [m,n] <- test1 --let [m,n] = [10,3200] (ps,bs) <- points m n print $ cluster (\x y -> abs (x - y)) ps bs

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