|
Size: 3772
Comment:
|
← Revision 5 as of 2017-02-03 20:17:12 ⇥
Size: 0
Comment: archived by mrennekamp
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| == Design discussion for permutations and discrete functions == This is about permutations, and more generally about functions between finite sets. Desirable features: (1) Python mantra: an object which looks like a list should behave like a list. I.e. if the users sees:: {{{ sage: p = ... sage: p [4,1,3,2] }}} Then he will expect:: {{{ sage: p[0] 4 }}} (2) The user should be able to manipulate permutations (functions) of any finite set, and manipulate them as is, without reindexing:: {{{ sage: F = Functions([3,4,8]) sage: F.list() [3,3,3] [3,3,4] [3,3,8] ... [8,8,8] sage: p = F([8,3,4]) [8,3,4] }}} In particular, whatever the syntax is, one want to be able to do:: {{{ sage: p of 3 8 sage: p of 3 = 4 sage: p [4,3,4] }}} It is important to have short notations for readability of the algorithms. Write access (with surrounding mutability mantra) is necessary as well. (3) Permutations(n) should be Permutations([1,...,n]) (4) Internally, permutations could be implemented as permutations of [0...n-1] for speed (future cythonization) It's in fact a typical design situation: internal implementations using 0...n indexing (cf. matrix, FreeModule, dynkin diagrams, Family, ...) + views on them indexed by whatever is convenient for the user. (5) Backward compatibility == Potential solutions: == - Current one:: {{{ sage: p = DiscreteFunction([3,1,2]) sage: p[0] 3 sage: p[0] = 1; p[1] = 3 # actually not implemented sage: p [1,3,2] }}} Caveat: breaks (2) - Use indexed access starting at 1 (or whatever the smallest letter is):: {{{ sage: p = DiscreteFunction([3,1,2]) sage: p[1] 3 sage: p[1] = 1; p[2] = 3 # actually not implemented sage: p [1,3,2] }}} Breaks (1), (5). This also means that any method that works on a list will not work on a permutation. So one would have to define a separate methods for a permutation. - Use functional notation:: {{{ sage: p = DiscreteFunction([3,1,2]) sage: p(1) 3 sage: p(1) = 1; p(2) = 3 # actually not implemented sage: p [1,3,2] }}} Caveat: requires patching Sage (no {{{__setcall__}}} analoguous to {{{__setitem__}}). In the mean time, we could use p.set(1, 1) (lengthy notation). Another (huge) disadvantage is that {{{__call___}}} is much slower than {{{__getitem__}}}:: {{{ sage: p = Permutations(130).random_element() sage: %timeit p[83] 1000000 loops, best of 3: 808 ns per loop sage: %timeit p.__getitem__(83) 1000000 loops, best of 3: 561 ns per loop sage: %timeit p(83) 100000 loops, best of 3: 3.27 µs per loop }}} Actually something that I have always wonder about: why don't we have Permutation_class inheriting from list/tuple? This would speed things up. {{{ sage: from sage.combinat.permutation import Permutation_class sage: class MyPermutation(list, Permutation_class): ... def __repr__(self): ... return '[%s]' % super(MyPermutation,self).__repr__()[1:-1] sage: q = MyPermutation(Permutations(17).random_element()); q [2, 8, 12, 7, 9, 3, 11, 15, 14, 4, 5, 1, 6, 17, 16, 13, 10] sage: %timeit q[11] 10000000 loops, best of 3: 89 ns per loop sage: %timeit q.__getitem__(11) 1000000 loops, best of 3: 304 ns per loop sage: %timeit q(11) 1000000 loops, best of 3: 1.2 µs per loop }}} - ... |
