summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorXavier Caruso <xavier.caruso@univ-rennes1.fr>2017-12-20 15:33:05 +0100
committerXavier Caruso <xavier.caruso@univ-rennes1.fr>2017-12-20 15:33:05 +0100
commitb70227bcec8cb6d841c2e157f1f1c08179254ef2 (patch)
tree8e8e039d575f42c49f39a7ae10b925ae355fadb6
parentSome doctests in lattice_precision.py (diff)
More doctests in lattice_precision.py
-rw-r--r--src/sage/rings/padics/lattice_precision.py400
1 files changed, 350 insertions, 50 deletions
diff --git a/src/sage/rings/padics/lattice_precision.py b/src/sage/rings/padics/lattice_precision.py
index 5180800..4041d97 100644
--- a/src/sage/rings/padics/lattice_precision.py
+++ b/src/sage/rings/padics/lattice_precision.py
@@ -194,6 +194,24 @@ class pRational:
########################
def list_of_padics(elements):
+ """
+ Convert a list of p-adic composed elements (as polynomials, matrices)
+ to a list of weak refererences of their p-adic coefficients.
+
+ This is an helper function for the methods meth:`precision_lattice`
+
+ TESTS::
+
+ sage: from sage.rings.padics.lattice_precision import list_of_padics
+ sage: R = ZpLP(2)
+ sage: M = random_matrix(R,2,2)
+ sage: list_of_padics(M)
+ [<weakref at 0x...; to 'pAdicLatticeElement' at 0x...>,
+ <weakref at 0x...; to 'pAdicLatticeElement' at 0x...>,
+ <weakref at 0x...; to 'pAdicLatticeElement' at 0x...>,
+ <weakref at 0x...; to 'pAdicLatticeElement' at 0x...>]
+
+ """
from sage.rings.padics.padic_lattice_element import pAdicLatticeElement
if isinstance(elements, pAdicLatticeElement):
return [ weakref.ref(elements) ]
@@ -205,9 +223,31 @@ def list_of_padics(elements):
return ans
def format_history(tme, status, timings):
+ """
+ Return a formated output for the history.
+
+ This is an helper function for the methods meth:`history`.
+
+ TESTS::
+
+ sage: from sage.rings.padics.lattice_precision import format_history
+ sage: format_history(1.23456789, ['o','o','o','o','o','o','~','o','o'], true)
+ '1.234568s oooooo~oo'
+ sage: format_history(1.23456789, ['o','o','o','o','o','o','~','o','o'], false)
+ 'oooooo~oo'
+
+ sage: format_history(12.3456789, ['o','o','o','o','o','o','~','o','o'], true)
+ ' >= 10s oooooo~oo'
+ sage: format_history(10^(-10), ['o','o','o','o','o','o','~','o','o'], true)
+ ' --- oooooo~oo'
+ sage: format_history(-1, ['o','o','o','o','o','o','~','o','o'], true)
+ ' Timings oooooo~oo'
+ """
status = ''.join(status)
if timings:
- if tme < 0.000001:
+ if tme < 0:
+ s = " Timings "
+ elif tme < 0.000001:
s = " --- "
elif tme >= 10:
s = " >= 10s "
@@ -271,7 +311,7 @@ class PrecisionLattice(UniqueRepresentation, SageObject):
sage: R = ZpLP(2)
sage: R.precision()
- Precision Lattice on 0 object
+ Precision Lattice on ... objects
If a label has been specified, it is included in the representation
@@ -305,8 +345,7 @@ class PrecisionLattice(UniqueRepresentation, SageObject):
def reduce(self, index=0, partial=False):
"""
- Perform a row reduction of the matrix representating this precision
- lattice
+ Reduce the size of the entries above the diagonal of the precision matrix
INPUT:
@@ -461,22 +500,20 @@ class PrecisionLattice(UniqueRepresentation, SageObject):
if self._history is not None:
self._history.append(('add', None, walltime(tme)))
- def _set_precision(self, x, column={}):
- """
- """
- p = self._p
- x_ref = weakref.ref(x)
- index = len(self._lattice[x_ref]) - 1
- n = len(self._elements)
- col = n * [self._approx_zero]
- self._lattice[x_ref] = col
- self._absolute_precisions[x_ref] = min([ c.valuation() for c in col ])
+ #def _set_precision(self, x, column={}):
+ # p = self._p
+ # x_ref = weakref.ref(x)
+ # index = len(self._lattice[x_ref]) - 1
+ # n = len(self._elements)
+ # col = n * [self._approx_zero]
+ # self._lattice[x_ref] = col
+ # self._absolute_precisions[x_ref] = min([ c.valuation() for c in col ])
def mark_for_deletion(self, ref):
"""
Mark an element for deletion.
- It is not meant to be called manually.
+ This function is not meant to be called manually.
It is automatically called by the garbage collection when
an element is collected.
@@ -490,6 +527,20 @@ class PrecisionLattice(UniqueRepresentation, SageObject):
The actual update is performed when the method meth:`del_elements`
is called. This is automatically done at the creation of a new
element but can be done manually as well.
+
+ EXAMPLES::
+
+ sage: R = ZpLP(2, label='markdel')
+ sage: prec = R.precision()
+ sage: x = R(1,10)
+ sage: prec
+ Precision Lattice on 1 object (label: markdel)
+ sage: del x # indirect doctest: x is here marked for deletion
+ sage: prec
+ Precision Lattice on 1 object (label: markdel)
+ sage: prec.del_elements() # x is indeed deleted
+ sage: prec
+ Precision Lattice on 0 object (label: markdel)
"""
tme = walltime()
try:
@@ -707,7 +758,7 @@ class PrecisionLattice(UniqueRepresentation, SageObject):
EXAMPLES::
- sage: R = ZpLP(2)
+ sage: R = ZpLP(2, label='preclattice')
sage: prec = R.precision()
sage: x = R(1,10); y = R(1,5)
sage: u = x + y
@@ -792,7 +843,8 @@ class PrecisionLattice(UniqueRepresentation, SageObject):
jagged precision (that is a precision which is split over
all variables).
- We refer to [] for a detail exposition of diffused digits.
+ We refer to [] for a detail exposition of the notion of
+ diffused digits.
EXAMPLES::
@@ -901,31 +953,31 @@ class PrecisionLattice(UniqueRepresentation, SageObject):
sage: prec.tracked_elements()
[1 + O(2^10), 1 + O(2^5)]
sage: prec.tracked_elements(values=False)
- [<weakref at ...; to 'pAdicLatticeElement' at ...>,
- <weakref at ...; to 'pAdicLatticeElement' at ...>,
- <weakref at ...; dead>]
+ [<weakref at 0x...; to 'pAdicLatticeElement' at 0x...>,
+ <weakref at 0x...; to 'pAdicLatticeElement' at 0x...>,
+ <weakref at 0x...; dead>]
sage: prec.tracked_elements(values=False, dead=False)
- [<weakref at ...; to 'pAdicLatticeElement' at ...>,
- <weakref at ...; to 'pAdicLatticeElement' at ...>]
+ [<weakref at 0x...; to 'pAdicLatticeElement' at 0x...>,
+ <weakref at 0x...; to 'pAdicLatticeElement' at 0x...>]
sage: u = x + y
sage: v = x - y
sage: prec.tracked_elements()
[1 + O(2^10), 1 + O(2^5), 2 + O(2^5), O(2^5)]
sage: prec.tracked_elements(values=False)
- [<weakref at ...; to 'pAdicLatticeElement' at ...>,
- <weakref at ...; to 'pAdicLatticeElement' at ...>,
- <weakref at ...; to 'pAdicLatticeElement' at ...>,
- <weakref at ...; to 'pAdicLatticeElement' at ...>,
- <weakref at ...; dead>]
+ [<weakref at 0x...; to 'pAdicLatticeElement' at 0x...>,
+ <weakref at 0x...; to 'pAdicLatticeElement' at 0x...>,
+ <weakref at 0x...; to 'pAdicLatticeElement' at 0x...>,
+ <weakref at 0x...; to 'pAdicLatticeElement' at 0x...>,
+ <weakref at 0x...; dead>]
sage: del x; del y
sage: prec.tracked_elements()
[None, None, 2 + O(2^5), O(2^5), None]
sage: prec.tracked_elements(values=False)
- [<weakref at ...; to 'pAdicLatticeElement' at ...>,
- <weakref at ...; to 'pAdicLatticeElement' at ...>,
- <weakref at ...; dead>]
+ [<weakref at 0x...; to 'pAdicLatticeElement' at 0x...>,
+ <weakref at 0x...; to 'pAdicLatticeElement' at 0x...>,
+ <weakref at 0x...; dead>]
"""
if values:
if dead:
@@ -942,20 +994,225 @@ class PrecisionLattice(UniqueRepresentation, SageObject):
# History
def history_enable(self):
+ """
+ Enable history.
+
+ We refer to the documentation of the method meth:`history` for
+ a complete documentation (including examples) about history.
+
+ TESTS::
+
+ sage: R = ZpLP(2, label='history_en')
+ sage: prec = R.precision()
+
+ sage: print(prec.history()) # history is disabled by default
+ Traceback (most recent call last):
+ ...
+ ValueError: History is not tracked
+
+ sage: prec.history_enable()
+ sage: print(prec.history())
+ Timings
+ ---
+
+ .. SEEALSO::
+
+ meth:`history`, meth:`history_disable`, meth:`history_clear`
+ """
if self._history is None:
self._history_init = ( len(self._elements), list(self._marked_for_deletion) )
self._history = [ ]
def history_disable(self):
+ """
+ Disable history.
+
+ We refer to the documentation of the method meth:`history` for
+ a complete documentation (including examples) about history.
+
+ TESTS::
+
+ sage: R = ZpLP(2, label='history_dis')
+ sage: prec = R.precision()
+
+ sage: print(prec.history()) # history is disabled by default
+ Traceback (most recent call last):
+ ...
+ ValueError: History is not tracked
+
+ sage: prec.history_enable()
+ sage: print(prec.history())
+ Timings
+ ---
+
+ sage: prec.history_disable()
+ sage: print(prec.history())
+ Traceback (most recent call last):
+ ...
+ ValueError: History is not tracked
+
+ .. SEEALSO::
+
+ meth:`history`, meth:`history_enable`, meth:`history_clear`
+ """
self._history = self._history_init = None
def history_clear(self):
+ """
+ Clear history
+
+ We refer to the documentation of the method meth:`history` for
+ a complete documentation (including examples) about history.
+
+ TESTS::
+
+ sage: R = ZpLP(2, label='history_clear')
+ sage: prec = R.precision()
+ sage: prec.history_enable()
+
+ sage: x = R(1,10); y = R(1,5)
+ sage: x,y = x+y, x-y
+ sage: print(prec.history())
+ Timings
+ ... oooo
+ ... ~~oo
+
+ When we clear history, only the last line is kept::
+
+ sage: prec.history_clear()
+ sage: print(prec.history())
+ Timings ~~oo
+ --- ~~oo
+
+ sage: del x;
+
+ sage: print(prec.history())
+ Timings ~~oo
+ ... ~~~o
+
+ .. SEEALSO::
+
+ meth:`history`, meth:`history_enable`, meth:`history_disable`
+ """
if self._history is None:
raise ValueError("History is not tracked")
self._history_init = ( len(self._elements), list(self._marked_for_deletion) )
self._history = [ ]
- def history(self, compact=True, include_reduce=False, timings=True, output_type='asciiart'):
+ def history(self, compact=True, separate_reduce=False, timings=True, output_type='asciiart'):
+ """
+ Show history
+
+ The history records creations and deletions of elements attached
+ to this precision lattice, together with many timings.
+
+ INPUT:
+
+ - ``compact`` -- a boolean (default: ``True``); if true, all
+ consecutive operations of the same type appear on a single row
+
+ - ``separate_reduce`` -- a boolean (default: ``False``); specify
+ whether partial/full Hermite reduction should be displayed
+ separatedly
+
+ - ``timings`` -- a boolean (default: ``True``); specify whether
+ timings should be displayed
+
+ - ``output_type`` -- only ``asciiart`` is implemented for now.
+
+ IMPORTANT NOTE:
+
+ History is disabled by default.
+ It should then be enabled (through a call to the method meth:`history_enable`)
+ before use.
+
+ EXAMPLES::
+
+ sage: R = ZpLP(2, label='history_en')
+ sage: prec = R.precision()
+
+ We first enable history::
+
+ sage: prec.history_enable()
+
+ At the beginning, the history is of course empty::
+
+ sage: print(prec.history())
+ Timings
+ ---
+
+ Now we start creating and deleting elements::
+
+ sage: L = [ R.random_element() for _ in range(20) ]
+ sage: for p in range(20):
+ ....: if is_prime(p): L[p] = None
+ sage: prec.del_elements()
+
+ sage: print(prec.history())
+ Timings
+ ... oooooooooooooooooooo
+ ... oo~~o~o~ooo~o~ooo~o~
+ ... oooooooooooo
+
+ The legend is the following::
+ - the symbol ``o`` represents a tracked element
+ - the symbol ``~`` represents an element which is marked for deletion
+
+ On the history, we see:
+ - 1st line: twenty new elements were created
+ (this corresponds to the affectation of the list ``L``)
+ - 2nd line: elements at prime positions were marked for deletion
+ (this corresponds to the ``for`` loop)
+ - 3rd line: the above elements are indeed deleted
+ (this corresponds to the call of the method meth:`del_elements`
+
+ Here are some variants::
+
+ sage: print(prec.history(timings=False))
+ oooooooooooooooooooo
+ oo~~o~o~ooo~o~ooo~o~
+ oooooooooooo
+
+ sage: print(prec.history(separate_reduce=True))
+ Timings
+ ... oooooooooooooooooooo
+ ... oo~~o~o~ooo~o~ooo~o~
+ ... oo~~o~o~ooo~ooooo
+ ... oo~~o~o~ooo~orrrr
+ ... oo~~o~o~oooooooo
+ ... oo~~o~o~ooorrrrr
+ ... oo~~o~ooooooooo
+ ... oo~~o~orrrrrrrr
+ ... oo~~oooooooooo
+ ... oo~~orrrrrrrrr
+ ... oo~oooooooooo
+ ... oo~rrrrrrrrrr
+ ... oooooooooooo
+ ... oorrrrrrrrrr
+ --- oooooooooooo
+
+ The symbol ``r`` represents a column of the precision matrix which is
+ currently under partial Hermite reduction
+
+ Timings for automatic reduction do not appear because they are included
+ in the timings for deletion.
+
+ The symbol ``R`` is used to symbolize a column which is under full
+ Hermite reduction. Note that full Hermite reduction are never performed
+ automatically but needs to be called by hand::
+
+ sage: prec.reduce()
+ sage: print(prec.history(separate_reduce=True))
+ Timings
+ ...
+ ... RRRRRRRRRRRR
+ --- oooooooooooo
+
+ .. SEEALSO::
+
+ meth:`history_enable`, meth:`history_disable`, meth:`history_clear`
+ """
+
if self._history is None:
raise ValueError("History is not tracked")
total_time = 0
@@ -969,12 +1226,25 @@ class PrecisionLattice(UniqueRepresentation, SageObject):
status = n*['o']
for index in mark:
status[index] = '~'
- hist = [ ]; oldevent = ''
+ hist = [ format_history(-1, status, timings) ]
+ oldevent = ''; total_time = 0
for (event, index, tme) in self._history:
- if not include_reduce and (event == 'partial reduce' or event == 'full reduce'):
+ if event == 'partial reduce' or event == 'full reduce':
+ if separate_reduce:
+ if total_time > 0:
+ hist.append(format_history(total_time, status, timings))
+ if event == 'partial reduce': code = 'r'
+ else: code = 'R'
+ status_red = status[:index] + (len(status) - index) * [code]
+ hist.append(format_history(tme, status_red, timings))
+ total_time = 0
+ oldevent = ''
+ else:
+ total_time += tme
continue
- if not compact or oldevent != event:
- hist.append(format_history(total_time, status, timings))
+ if not compact or event != oldevent:
+ if total_time > 0:
+ hist.append(format_history(total_time, status, timings))
total_time = 0
oldevent = event
total_time += tme
@@ -984,31 +1254,61 @@ class PrecisionLattice(UniqueRepresentation, SageObject):
status[index] = '~'
elif event == 'del':
del status[index]
- elif event == 'partial reduce':
- status_red = status[:index] + (len(status) - index)*['r']
- hist.append(format_history(0, status_red, timings))
- elif event == 'full reduce':
- status_red = status[:index] + (len(status) - index)*['R']
- hist.append(format_history(0, status_red, timings))
- else:
- raise RuntimeError("event not known in the history")
- hist.append(format_history(total_time, status, timings))
+ if total_time > 0 or oldevent == '':
+ hist.append(format_history(total_time, status, timings))
return '\n'.join(hist)
else:
raise NotImplementedError
def timings(self, action=None):
+ """
+ Return cumulated timings (grouped by actions) since the last
+ time history has been cleared.
+
+ INPUT:
+
+ - ``action`` -- ``None`` (the default), ``add``, ``mark``, ``del``,
+ ``partial reduce`` or ``full reduce``; if not None, return the
+ cumulated timing corresponding to this action; otherwise, return
+ a dictionary
+
+ Here are the meanings of the keywords above:
+ - ``add``: time spent in adding new colunmns to the precision matrix
+ (corresponding to the creation of new elements)
+ - ``mark``: time spent in marking elements for deletion
+ - ``del``: time spent in deleting columns of the precision matrix
+ and re-echelonizing the matrix
+ - ``partial reduce``: time spent in partial Hermite reduction
+ - ``full reduce``: time spent in full Hermite reduction
+
+ EXAMPLES::
+
+ sage: R = ZpLP(2, label='timings')
+ sage: prec = R.precision()
+ sage: prec.history_enable()
+ sage: M = random_matrix(R,5,5)
+ sage: N = M^10
+ sage: prec.timings() # somewhat random
+ {'add': 1.0530245304107666,
+ 'del': 0.24358701705932617,
+ 'mark': 0.0013289451599121094,
+ 'partial reduce': 0.21604204177856445
+ 'full reduce': 0}
+
+ TESTS::
+
+ sage: prec.history_clear()
+ sage: prec.timings()
+ {'add': 0, 'del': 0, 'full reduce': 0, 'mark': 0, 'partial reduce': 0}
+ """
if self._history is None:
raise ValueError("History is not tracked")
- tme_by_event = { }
+ tme_by_event = { 'add': 0, 'del': 0, 'mark': 0, 'partial reduce': 0, 'full reduce': 0 }
for (event, _, tme) in self._history:
- if tme_by_event.has_key(event):
- tme_by_event[event] += tme
- else:
- tme_by_event[event] = tme
+ tme_by_event[event] += tme
if action is None:
return tme_by_event
if tme_by_event.has_key(action):
return tme_by_event[action]
else:
- return 0
+ raise ValueError("invalid event")