Changes between Version 22 and Version 37 of Ticket #10534


Ignore:
Timestamp:
06/06/14 20:31:07 (4 years ago)
Author:
vdelecroix
Comment:

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #10534

    • Property Status changed from needs_review to needs_work
    • Property Commit changed from to efd638056cb99427de29b298169299fa171184fc
    • Property Branch changed from to u/chapoton/10534
    • Property Milestone changed from sage-5.11 to sage-6.3
    • Property Work issues changed from to does not apply
    • Property Summary changed from Optimizations for the generation of subwords, subsets and set partitions to Cleanup in choose_nk, split_nk, subword, subset

  • Ticket #10534 – Description

    v22 v37  
    1 This ticket stands for a faster method of exhaustive generation of combinatorial object that may be found in sage.combinat.* and more precisely
     1- deprecate `ChooseNK` (in `sage.combinat.choose_nk`) and `SplitNK` (in `sage.combinat.split_nk`).
     2- clean `sage.combinat.subword` and `sage.combinat.subset`
     3  - inheritance from `Parent`
     4  - much better iteration/random generation
     5  - ...
    26
    3  * subwords (sage.combinat.subword)
    4  * subsets (sage.combinat.subset)
    5  * set partitions (sage.combinat.set_partitions and sage.combinat.set_partition_ordered)
    6 
    7 Most of the time, the improvment just consists in calling the python library itertools. For other, it consists in creating a lower level Python iterator which does not use the heavy mechanism of Parent/Element (which is not intended for the frontend user).
    8 
    9 Moreover, the patch provides
    10   * bugs and typos corrections (doctest coverage is now 100%)
    11   * random generation capabilities
    12   * modified cardinality method which always return a Sage Integer (and no more Python int or Sage Rational)
    13 
    14 Some timings (on Intel(R) Core(TM)2 Duo CPU T8100  @ 2.10GHz)
    15 
    16 Old version
    17 
    18 {{{
    19 sage: S = SetPartitions(8,[3,3,2])
    20 sage: timeit('for p in S: pass')
    21 5 loops, best of 3: 401 ms per loop
    22 
    23 sage: S = SetPartitions(9,[3,3,2,1])
    24 sage: timeit('for p in S: pass')
    25 5 loops, best of 3: 4 s per loop
    26 
    27 sage: S = Subsets([1]*1+[2]*2+[3]*3+[4]*4+[5]*5, submultiset=True)
    28 sage: timeit('S.cardinality()')
    29 5 loops, best of 3: 712 ms per loop
    30 }}}
    31 New version
    32 
    33 {{{
    34 sage: S = SetPartitions(8,[3,3,2])
    35 sage: timeit('for p in S: pass')
    36 5 loops, best of 3: 130 ms per loop
    37 sage: timeit('for p in S._fast_iterator(): pass')
    38 25 loops, best of 3: 10.4 ms per loop
    39 
    40 sage: S = SetPartitions(9,[3,3,2,1])
    41 sage: timeit('for p in S: pass')
    42 5 loops, best of 3: 1.43 s per loop
    43 sage: timeit('for p in S._fast_iterator(): pass')
    44 5 loops, best of 3: 91.3 ms per loop
    45 
    46 sage: S = Subsets([1]*1+[2]*2+[3]*3+[4]*4+[5]*5,submultiset=True)
    47 sage: timeit('S.cardinality()')
    48 625 loops, best of 3: 33.9 µs per loop
    49 }}}
    50 
    51 Apply only:
    52 
    53   * trac_10534-generation_of_subsets_and_set_partitions.3.patch
     7And become more pep8 compliant ;=)