search

davecom / SwiftGraph

A Graph Data Structure in Pure Swift
Apache License 2.0
758 stars 80 forks source link

Improve performance of topological sort #79

Closed dabbott closed 4 years ago

dabbott commented 4 years ago

This change improves the performance of topological sort by removing the linear lookups of vertices. I think it was something like O(n^4) with calls to indexOfVertex. I also try to do fewer vertex allocations by using indices everywhere, although this is relatively minor in comparison.

I didn't test exhaustively, but in my use case with ~500 vertices and ~500 edges, sorting went from 12s to 20ms!

davecom commented 4 years ago

Thanks, @dabbott . This is an awesome and straightforward fix!

kokluch commented 3 years ago

Hi @dabbott, is there a coming tag including this enhancement? We've tried it and it's significantly faster. We'd like to integrate it in production code.

davecom commented 3 years ago

Hi @kokluch, I’ll push out a 3.0.1 version late today including @dabbott’s performance improvement. Thanks for using SwiftGraph.

davecom commented 3 years ago

Hi @kokluch, This ended up getting pushed as 3.1. It's live now. Out of curiosity, what app are you using SwiftGraph in? Thanks, David

kokluch commented 3 years ago

Hi @davecom, Thanks for the tag :) however it's not a valid spm format so I cannot retrieve it properly. Would you be kind to make it 3.1.0? I would really appreciate. As for the apps I can't say much but you'll find SwiftGraph license mentioned on the followed apps: https://apps.apple.com/fr/app/netatmo-security/id951725393 https://apps.apple.com/fr/app/netatmo-weather/id532538499 https://apps.apple.com/fr/app/home-control/id1188809809 This list is not exhaustive.

davecom commented 3 years ago

Hi @kokluch,

Oops, sorry about that. I just pushed a 3.1.0 tag, hopefully that fixes the issue. And thanks for the info, that's very encouraging to know.

Best, David