Faster complement and conjugate methods for Composition using naive method

[mathzeta]

For compositions of n greater than about 55, it seems that the naive method of constructing the complement composition using the difference of sets is faster. This obviously also can affect the conjugate() method.

In the attached branch, I added a "complement_naive" method. Few timings:

sage: C = Compositions(20)
sage: A = [C.random_element() for i in range(300)]
sage: %timeit B = [c.complement() for c in A]
100 loops, best of 3: 5.29 ms per loop
sage: %timeit B = [c.complement_naive() for c in A]
100 loops, best of 3: 8.48 ms per loop

sage: C = Compositions(50)
sage: A = [C.random_element() for i in range(300)]
sage: %timeit B = [c.complement() for c in A]
100 loops, best of 3: 10.1 ms per loop
sage: %timeit B = [c.complement_naive() for c in A]
100 loops, best of 3: 10.3 ms per loop

sage: C = Compositions(55)
sage: A = [C.random_element() for i in range(300)]
sage: %timeit B = [c.complement() for c in A]
100 loops, best of 3: 10.9 ms per loop
sage: %timeit B = [c.complement_naive() for c in A]
100 loops, best of 3: 10.5 ms per loop

sage: C = Compositions(100)
sage: A = [C.random_element() for i in range(200)]
sage: %timeit B = [c.complement() for c in A]
100 loops, best of 3: 12.6 ms per loop
sage: %timeit B = [c.complement_naive() for c in A]
100 loops, best of 3: 8.44 ms per loop

sage: C = Compositions(200)
sage: A = [C.random_element() for i in range(300)]
sage: %timeit B = [c.complement() for c in A]
10 loops, best of 3: 39.8 ms per loop
sage: %timeit B = [c.complement_naive() for c in A]
100 loops, best of 3: 17.2 ms per loop

sage: C = Compositions(1000)
sage: A = [C.random_element() for i in range(300)]
sage: %timeit B = [c.complement() for c in A]
1 loop, best of 3: 396 ms per loop
sage: %timeit B = [c.complement_naive() for c in A]
10 loops, best of 3: 59.9 ms per loop

This happens probably because a random composition of n have "many" small parts

Component: combinatorics

Keywords: days94

Author: Tomer Bauer

Branch/Commit: u/mathzeta2/25691_composition_complement_naive @ 5a53744

Issue created by migration from https://trac.sagemath.org/ticket/25691

[mathzeta]

Commit: 5a53744

[mathzeta]

Branch: u/mathzeta2/25691_composition_complement_naive