ac-library-rs icon indicating copy to clipboard operation
ac-library-rs copied to clipboard

Try reusing arrays in "mincostflow"

Open kenkoooo opened this issue 5 years ago • 1 comments

In mincostflow, we can reuse some arrays.

It is said that using the distance component only in the compare function reduces the running time of dijkstra. I've never compared them by myself, but it might worth trying.

Originally posted by @MiSawa in https://github.com/rust-lang-ja/ac-library-rs/pull/25#discussion_r485758288

kenkoooo avatar Sep 10 '20 14:09 kenkoooo

Actually reusing vector and priority queue instances would reduce the number of malloc and realloc, which might be important to do. Though my intention there was about the definition of comparison used in the priority queue. The original implementation uses this custom structure instead of pair<Cost, int> plus greater<pair<Cost, int>>, since in this way, we can avoid comparing the vertex ids in the comparison function.

I think we can create a helper wrapper struct like this, or create a struct in place like what the original impl do.

MiSawa avatar Sep 11 '20 08:09 MiSawa