Seth Gordon <[EMAIL PROTECTED]> wrote:
> almost-entirely-functional code ... that in its first draft, took
> about three seconds to process 2,000 rows, eight minutes to process
> 20,000 rows, and overflowed a 1-MB stack when processing 200,000 rows.
> Oops.
Which just goes to show that your algorithm is non-linear in the size of
the input. I doubt that your posted snippet is the cause of the
problem, since it is certainly linear in the AList it is given.
> I profiled the code and
> observed that the most-called-upon function in the program (200
> million entries for those 20,000 rows)
By optimisation, you can only make this function a constant factor
faster. You need to work out how to call it less often in the first
place.
> type AList = [(Key, [MetaThingies])]
>
> myFunction :: AList -> Thingie -> AList
> myFunction [] x = [(key x, [meta x])]
> myFunction ((k, v):tail) x | matchKeys k (key x) =
> case tryJoining v x of
> Nothing -> (k, v) : (myFunction tail x)
> Just v' -> (k', v') : tail
> where v' = bestKey k (key x)
> | otherwise = (k, v) : (myFunction tail x)
myFunction is clearly rather like a map (except that occasionally it
stops before traversing the whole list). There is nothing wrong with
its recursion pattern or otherwise.
Regards,
Malcolm
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
