You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
polyTimes::Semiringa=>Vectora->Vectora->Vectora
polyTimes x y
=ifVector.null x then x elseifVector.null y then y elseVector.cons (times a b) (Vector.map (a *) q +Vector.map (* b) p + (Vector.cons zero (polyTimes p q)))
where
a =Vector.unsafeHead x
b =Vector.unsafeHead y
p = (\t d ->ifVector.null t then d else t) (Vector.tail x) (Vector.empty)
q = (\t d ->ifVector.null t then d else t) (Vector.tail y) (Vector.empty)
Technically this is the optimum in terms of asymptotic analysis.
Proof:
C(0) = 0
C(n) = n (Vector.cons) + n (Vector.map) + n (Vector.map) + n (Vector.cons) + C(n - 1) (recursive call)
That recurrence represent the worst case running time of polyTimes. Solving this with the master method C(n) = Θ(n^2). This being said the asymptotics hide some serious constants. You copy the vector into a new vector two times each recursive call because of Vector.cons. Never use Vector.cons it has to copy the entire vector into a new one that is just one element bigger. Instead rethink the algorithm to not use Vector.cons. You could completely redesign the alg or use ST and mutable vectors.
The text was updated successfully, but these errors were encountered:
Specifically the instance for vectors is awful
Technically this is the optimum in terms of asymptotic analysis.
Proof:
That recurrence represent the worst case running time of
polyTimes
. Solving this with the master methodC(n) = Θ(n^2)
. This being said the asymptotics hide some serious constants. You copy the vector into a new vector two times each recursive call because ofVector.cons
. Never useVector.cons
it has to copy the entire vector into a new one that is just one element bigger. Instead rethink the algorithm to not useVector.cons
. You could completely redesign the alg or useST
and mutable vectors.The text was updated successfully, but these errors were encountered: