#19494: Make finite word method nb_subword_occurences_in much faster
-------------------------+-------------------------------------------------
Reporter: | Owner:
slabbe | Status: needs_info
Type: | Milestone: sage-6.10
enhancement | Resolution:
Priority: major | Merged in:
Component: | Reviewers: Vincent Delecroix
combinatorics | Work issues:
Keywords: | Commit:
Authors: | b5fcb6310fc2370c16048845be9f7b859388139f
Sébastien Labbé | Stopgaps:
Report Upstream: N/A |
Branch: |
u/slabbe/19494 |
Dependencies: |
-------------------------+-------------------------------------------------
Changes (by vdelecroix):
* status: needs_review => needs_info
* reviewer: => Vincent Delecroix
Comment:
If I understand correctly `u.binomial(v)` is the same thing as
`v.nb_subword_occurrences_in(u)`. Why two distinct terminologies? Words
currently have `is_prefix` and `has_prefix` which I found much clearer.
With your function, you are creating some `n x n` matrices where `n` is
the length of the small word `v`. Could you check that `u` and `v` are
roughyl of the same length (say 12 and 10 or 100 and 90) your new code is
still better. In your examples there are only occurrences where `v` is
much smaller than `u`.
One drawback in the above case might also be memory usage and complexity
of dense matrix multiplication. You might need `n^3` space (for `n` dense
matrices of size `n x n`) and if `n` is big, multiplying `n x n` dense
matrices is expensive. Using sparse matrices in some corner case might be
useful, e.g.
{{{
sage: W = Words(NN)
sage: v = W(range(100))
sage: u = W(randint(0,99) for _ in range(200))
sage: u.binomial(v)
}}}
In the above case, I do not expect that the result of `prod(...)` being
that much dense. But perhaps I am wrong. Could you test it and if relevant
add an argument `sparse` (that would be `False` by default)?
Vincent
--
Ticket URL: <http://trac.sagemath.org/ticket/19494#comment:3>
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 http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
