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
All the work being done with the bang patterns does not seem to be necessary for the suc function as far as I can tell. I think the strict evaluation could cause the asymptotic complexity of the suc function to change from O(k + min(n,W)) (where k is the number of nodes in the output and n and W are the familiar IntMap variables) to O(n) (because of the clearPred and clearSucc functions). Should this be rewritten to:
matchGr::Node->Grab->DecompGrab
matchGr node (Gr g)
=caseIM.lookup node g ofNothing-> (Nothing, Gr g)
Just (p, label, s)
->let g1 =IM.delete node g
p' =IM.delete node p
s' =IM.delete node s
g2 = clearPred g1 node s'
g3 = clearSucc g2 node p'
in (Just (p' `seq` toAdj p', node, label, toAdj s), g3 `seq`Gr g3)
Or something similar.
The text was updated successfully, but these errors were encountered:
I was trying to figure out the time complexity of
suc
which lead me to thematchGr
function.fgl/Data/Graph/Inductive/PatriciaTree.hs
Lines 146 to 158 in 86dc04d
All the work being done with the bang patterns does not seem to be necessary for the
suc
function as far as I can tell. I think the strict evaluation could cause the asymptotic complexity of thesuc
function to change fromO(k + min(n,W))
(wherek
is the number of nodes in the output andn
andW
are the familiarIntMap
variables) toO(n)
(because of theclearPred
andclearSucc
functions). Should this be rewritten to:Or something similar.
The text was updated successfully, but these errors were encountered: