Hi Christian,
On 2018-03-06, Christian Stump <christian.st...@gmail.com> wrote:
> Let me add that the situations I care about are n,m <= 20, the entries are
><=5 and the matrices are sparsely filled. An random and typical example is
That matrix seems far too small to say anything substantial about
timings. However, profiling the hash computation in a loop, it seems that the
method add_edge is called quite frequently. However, I don't really see
where the time spent in the function _matrix_to_digraph (which seems to
be the bottle neck here) is spent.
I haven't really been able to work around the bottle neck, but got a
minor improvement (4%) as follows:
add_edges is frequently used, so, I tried to not create an empty graph and
then add edges to it, but instead create the list of vertices and edges and
then create the graph from these lists. However, there is no gain at all, as
DiGraph.__init__ calls add_edges basically in the same way as you do.
I changed the use of the list edge_labels.
You basically use it to tell at what point an edge label has been
created, and do this by frequently computing the index. It seems slightly
better to me to to store the same information in a dict. So, replace
edge_labels.index((i,j)) and the error catching by
edge_labels.setdefault((i,j), ...).
Also, it seems slightly faster to obtain the hash of a frozen set than
of a sorted tuple:
sage: dg_canon = dg.canonical_label(partition=partition, algorithm="bliss",
return_graph=False)
sage: %timeit hash(frozenset(dg_canon))
100000 loops, best of 3: 2.79 µs per loop
sage: %timeit hash(tuple(sorted(dg_canon)))
100000 loops, best of 3: 4.57 µs per loop
And of course using cython helps as well. With the following Cython code, I am
down to 272 µs per loop, while your original Python code gave me 325 µs
per loop:
##################
def matrix_canonical_hash(M, n, m):
dg,partition = _matrix_to_digraph(M, n, m)
dg_canon = dg.canonical_label(partition=partition, algorithm="bliss",
return_graph=False)
return hash(frozenset(dg_canon))
from sage.matrix.matrix0 cimport Matrix
from sage.all import matrix, DiGraph
cpdef _matrix_to_digraph(Matrix M, int n, int m):
cdef dict edge_labels = dict()
cdef int n_labels = 0
cdef int new_vertex = n+m
cdef list Edges = []
cdef list new_partition = []
cdef int i,j
for i,j in M.nonzero_positions():
a = M.get_unsafe(i,j)
if i < n:
b = M.get_unsafe(j,i)
else:
b = -M.get_unsafe(i, j)
if a > 0:
if a == 1 and b == -1:
Edges.append((i,j))
else:
x = edge_labels.setdefault((a,b), n_labels)
if n_labels < len(edge_labels):
new_partition.append([])
n_labels += 1
Edges.append((i,new_vertex))
Edges.append((new_vertex,j))
new_partition[x].append(new_vertex)
new_vertex += 1
elif i >= n:
if a == -1 and b == 1:
Edges.append((j,i))
else:
a = -a
b = -b
x = edge_labels.setdefault((a,b), n_labels)
if n_labels < len(edge_labels):
new_partition.append([])
n_labels += 1
Edges.append((j,new_vertex))
Edges.append((new_vertex,i))
new_partition[x].append(new_vertex)
new_vertex += 1
cdef list partition = [list(range(n))]
if m > 0:
partition.append(list(range(n,n+m)))
if new_partition:
partition.extend(new_partition)
return DiGraph([range(new_vertex),Edges],sparse=True), partition
M = matrix([(0, -1, 0, 0, 0, 0, 0, 1),
(1, 0, 1, 0, 0, 0, 0, 0),
(0, -1, 0, 0, 1, 0, 0, 0),
(0, 0, 0, 0, 0, 1, 0, 0),
(0, 0, -1, 0, 0, 0, 1, 0),
(0, 0, 0, -1, 0, 0, -1, 0),
(0, 0, 0, 0, -1, 1, 0, 0),
(-2, 0, 0, 0, 0, 0, 0, 0),
(-1, 1, 0, 0, 0, 0, 0, 0),
(0, 1, 0, 0, 0, 0, 0, -1),
(0, 1, 0, 1, 0, -1, 0, -1),
(0, 2, -1, 1, 0, -1, 0, -1),
(0, 2, -1, 0, 0, -1, 0, -1),
(0, 2, 0, 0, -1, -1, 0, -1),
(0, 2, 0, 0, -1, 0, -1, -1),
(0, 2, 0, 0, 0, 0, -2, -1)]
)
###############
Best regards,
Simon
--
You received this message because you are subscribed to the Google Groups
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.
