search

dpaukov / combinatoricslib3

Combinatorial objects stream generators for Java.
Apache License 2.0
177 stars 24 forks source link

Optimize subset generation. #18

Closed nstdio closed 2 years ago

nstdio commented 2 years ago

This PR provides significant performance boost for subset generation. Firstly, when assembling a next subset, namely instead of looping over original input and checking a subset state in the bit vector now we are loop directly on bit vector. The second one is that we don't unconditionally clear content of internal list, but overwrite old elements and clear leftovers afterwards.

        Input Size          Time          Cleared
before          30      4m 33sec      16106127330
after           30      2m 22sec        536870882
coveralls commented 2 years ago

Coverage Status

Coverage increased (+0.005%) to 99.746% when pulling 57026618f7682b3def255cb50546ec363b1fe243 on nstdio:optimize-subset into 67c8a2fd3175776a9135d5677628cc7764e42db8 on dpaukov:master.

dpaukov commented 2 years ago

Thank you for improving the performance of the subset iterator!

nstdio commented 2 years ago

Can we have a new patch version to try it out?

dpaukov commented 2 years ago

Yes, the change is available in version 3.3.3.