search

toyboot4e / ac-library-hs

[WIP] Haskell port of ac-library.
Creative Commons Zero v1.0 Universal
4 stars 0 forks source link

MaxFlow API (`Builder` vs `GrowVec`) #7

Closed toyboot4e closed 1 month ago

toyboot4e commented 1 month ago

Original ACL makes use of std::vector. Shall we follow ACL or separate Builder and MaxFlow?

toyboot4e commented 1 month ago

Growable vector requires another indirection (MutVar). I would give it a try and compare the performance.

toyboot4e commented 1 month ago

So I've implemented a GrowVec version of max flow (b61e96a). Here's a comparsion in ACLP - D, though the test case was too small:

MaxFlow:

[INFO] slowest: 0.200039 sec  (for 01-13.txt)
[INFO] max memory: 64.000000 MB  (for 01-09.txt)

MaxFlowGrow:

[INFO] slowest: 0.216807 sec  (for 01-13.txt)
[INFO] max memory: 64.000000 MB  (for 01-06.txt)

MaxFlowGrow is surely slower, but not too much. Now I'm preferring ACL-compatible API over speed.