bijectionist does avoidable work

[mantepse]

Steps To Reproduce

Suppose we are calling

sage: Bijectionist(A, B)

with large sets A and B, eg., with 20000 elements each, as in the doctest.

Expected Behavior

This should return almost immediately, since no work needs to be done.

Actual Behavior

Instead, it takes a long time. This is because __init__ finally calls self.set_constant_blocks([]), which in turn calls self._compute_possible_block_values(), which will then compute the intersection of the two element sets

([self._restrictions_possible_values[a] for a in block] + [self._statistics_possible_values[a] for a in block])

for each block of self._P. Here self._P is a DisjointSet of singletons - one block for each element of self._A. In fact, this will always be the value of self._P, whenever we are looking for a bijection (i.e., self._tau is the identity map).

However, initially, these two sets are all of self._A.

So:

• check whether we can avoid calling self._compute_possible_block_values()
• check whether we can optimize self._compute_possible_block_values() for the case of very few non-singleton blocks.

Additional Information

No response

Environment

irrelevant.

Checklist

• I have searched the existing issues for a bug report that matches the one I want to file, without success.
• I have read the documentation and troubleshoot guide

[mantepse]

While looking into this I also realised that _preprocess_intertwining_relations has no real example - both examples provided actually do not modify _P.

Also,

        .. TODO::

            it is not clear whether this method makes sense

is a little discouraging.

[mantepse]

Note to myself: I need to track callers of _possible_block_values, because this is what _compute_possible_block_values sets. These are

• _forced_constant_blocks
• possible_values
• _find_counterexample
• and all of _Bijectionist_MILP