search

gaperez64 / acacia-bonsai

A minimal implementation of reactive synthesis via universal co-Buchi automata using antichains
GNU General Public License v3.0
4 stars 3 forks source link

Faster union for vector_backed #39

Closed gaperez64 closed 8 months ago

gaperez64 commented 1 year ago

It's not ground-breaking, but if instead of merely inserting elements from one antichain into the other (cf. https://github.com/gaperez64/acacia-bonsai/blob/617b702848d1ebb79659873d943846f3b4bf936e/src/downsets/vector_backed.hh#L76) we keep a pointer to the end of the first antichain, we can avoid checking domination against freshly inserted elements. This works because we know we started with two antichains.

With this, one gets the best running time we've come up with for union (even considering constants). That is nmd . With k-d trees it seems it's 2nmd since one needs to check for domination on both trees.

gaperez64 commented 1 year ago

Nope the fastest way is to have a single nesting of the loops in which we check both sides of inequalities