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
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev
Locked
