[Moose-dev] Re: Tarjan optimization

Hello, I have been using Moose for some graph analysis and I noticed that Tarjan was a little slow. Analyzing further, I noticed that even though the complexity of Tarjan is linear, building the graph is O(n*m) where n is the number of nodes, and m is the number of edges of the graph. This happen because Moose creates its own graph nodes using as a model my nodes, and then for building each edge of the graph it looks for the corresponding node using detect: [ :n | n model = aModel ] over the OrderedCollection of nodes. I fixed it by replacing the nodes OrderedCollection for a Dictionary and replacing the MalTarjan>>findNode:ifAbsent: implemented with a detect:ifAbsent: by a Dictionary lookup. In my benchmark of 2 seconds before the fix, now takes 38ms, and my other experiment that I got bored of waiting after 10 hours now it takes less than 1 hour and a half. I already committed it, the tests look fine but let me know if something goes bad. Cheers, Alejandro _______________________________________________ Moose-dev mailing list Moose-dev(a)iam.unibe.ch https://www.iam.unibe.ch/mailman/listinfo/moose-dev