#20028: sorting of number field elements
-------------------------------------+-------------------------------------
Reporter: cremona | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-7.1
Component: number fields | Resolution:
Keywords: sort number field | Merged in:
elements | Reviewers:
Authors: | Work issues:
Report Upstream: N/A | Commit:
Branch: | 7aca11920ce4e5f5b02f6c89adc0ae59213940fd
u/nbruin/sorting_of_number_field_elements| Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by nbruin):
Replying to [comment:4 cremona]:
> Thanks for geting started on this. I have built the branch and will see
what "make testlong" reveals. It may be a good idea -- surely -- to not
put this forward for merging until there is at least a default sorting
function in place, which is quick such as by comparing strings?
Isn't the whole idea that there is ''no'' default sorting function? If you
mean making convenient key functions readily available, then: yes. I
expect we'll need them to fix doctests.
Comparing strings is not cheap at all because constructing the string
representation is slow. It's better to stick with binary objects.
Coefficient lists are much faster:
{{{
sage: L=[a^j for j in [1..100]]
sage: %timeit [str(l) for l in L]
100 loops, best of 3: 5.89 ms per loop
sage: %timeit [l.list() for l in L]
1000 loops, best of 3: 386 µs per loop
sage: %timeit [list(l) for l in L]
100 loops, best of 3: 9.92 ms per loop
sage: k=lambda l:l.list()
sage: %timeit [k(l) for l in L]
1000 loops, best of 3: 398 µs per loop
}}}
unfortunately, using "list(l)" is slow: it might construct an iterator out
of l first, which would have much more overhead to get the whole list of
coefficients than getting the list immediately. So either we optimize
"list" so that `sorted(L,key=list)` works or we make `k` above available
(possibly in a lower overhead version). Note that coefficient lists
already come in the right order for power basis rep: integers look like
`[*,0,...,0]`.
--
Ticket URL: <http://trac.sagemath.org/ticket/20028#comment:5>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
