Cleanup Graph.__init__ and DiGraph.__init__

[vdelecroix]

While reading #17384, I thought that a global cleanup of Graph.__init__ and DiGraph.__init__ would be good. We implement:

1)

- data = dict([u, list(data[u])] for u in data)
+ data = {u: list(v) for u,v in data.iteritems()}

2) call to uniq is bad since it calls a useless sorted: each appearance of {{{len(uniq(X))}}} is replaced with {{{len(set(X))}}}.

3) dict.iteritems is more readable and faster

sage: d = {randint(0,1000): [randint(0,1000) for _ in range(10)] for _ in range(100)}
sage: timeit("for i in d: j = d[i]", number=2000)
2000 loops, best of 3: 9.75 µs per loop
sage: timeit("for i,j in d.iteritems(): pass", number=2000)
2000 loops, best of 3: 7.3 µs per loop

4) avoid iterating through the elements of the adjacency matrix when possible

and more...

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​c4bf5cf	trac #17384: Slowness when calling Graph(a_dictionary)
​3bea4e5	trac #17385: replacement uniq -> set
​3f8a98b	trac #17385: various optimization

[dcoudert]

I was not expecting bool is False to be faster than bool === False. Amazing.

sage: bool = True
sage: %timeit bool is False
10000000 loops, best of 3: 70.3 ns per loop
sage: %timeit bool == False
10000000 loops, best of 3: 88.7 ns per loop
sage:
sage: bool = False
sage: %timeit bool == False
10000000 loops, best of 3: 88.9 ns per loop
sage: %timeit bool is False
10000000 loops, best of 3: 70.2 ns per loop

For me the patch is OK (installation, test, doc), so I give positive review.

[vdelecroix]

Thanks for the review.

To answer your interrogation is and == are very different, and is will always be faster.

The command bool is False is treated without asking anything to the object bool. It is just the Python kernel that checks whether the memory addresses match or not. For == a method of the object bool is called. Even if the comparison is implemented with something like return self is other you do not avoid that function call.

But I am not sure that those 18 non seconds are of critical importance in the creation of a graph... it was more a matter of uniformization ;-)

Vincent

[tscrim]

While that's an improvement, the fastest way is to do if x: or if not x:.

sage: x = True
sage: %timeit if x is True: pass
10000000 loops, best of 3: 165 ns per loop
sage: %timeit if x is False: pass
10000000 loops, best of 3: 148 ns per loop
sage: %timeit if x: pass
10000000 loops, best of 3: 91.9 ns per loop
sage: %timeit if not x: pass
10000000 loops, best of 3: 80.1 ns per loop
sage: x = False
sage: %timeit if x is True: pass
10000000 loops, best of 3: 148 ns per loop
sage: %timeit if x is False: pass
10000000 loops, best of 3: 165 ns per loop
sage: %timeit if x: pass
10000000 loops, best of 3: 79.1 ns per loop
sage: %timeit if not x: pass
10000000 loops, best of 3: 91.9 ns per loop

So I'd change things to use that. Plus you can simplify things like:

+         if ((loops is None or loops is False) and
-         if (not loops and

(and if statements like that are more common).

[vdelecroix]

Replying to tscrim:

While that's an improvement, the fastest way is to do if x: or if not x:.

You are right... I will do the changes (but your timings are not complete since you forgot the case x = None). There were occurrences at other places in the code. The advantage I see is that, while you read it, you know that None is one possible choice whereas

if not x and some_condition:
    if x is False:
        raise ValueError
    x = True

is a bit less verbose.

Vincent

[tscrim]

True. When I was doing my timings I wasn't thinking of the None simplifications, but FTR:

sage: x = None
sage: %timeit if x is None: pass
10000000 loops, best of 3: 117 ns per loop
sage: %timeit if x is not None: pass
10000000 loops, best of 3: 102 ns per loop
sage: %timeit if x: pass
10000000 loops, best of 3: 88 ns per loop
sage: %timeit if not x: pass
10000000 loops, best of 3: 101 ns per loop

I would say the loss of verbosity (according to FF, I'm not making that word up like I thought) is covered by python ducktyping. Anyways, I don't really care that much, so if you don't think it should be changed, then feel free to leave it. Thanks for cleaning this up.

[dcoudert]

I agree that we should try to let the code as readable as possible, especially for non critical code.

If we want to optimize further, there is apparently a small difference between x is not None and not x is None ;-)

sage: x = None
sage: %timeit if x is not None: pass
10000000 loops, best of 3: 57.8 ns per loop
sage: %timeit if not x is None: pass
10000000 loops, best of 3: 57.2 ns per loop

[vdelecroix]

Hi,

Actually it was good to have another look at the code since I introduced a bug for weighted digraph.... (see the test in the last commit that will appear in a second).

@dcoudert: actually is not is an operator that should be as fast as is. While not involves some function call... it is strange that you get those timings.

Vincent

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​2a5495d

trac #17384: more cleanup after reviewer's comment

[vdelecroix]

I am a bit worried about the code duplication. It was a pain to me to look systematically at both graph.py and digraph.py to search for potential mistakes. And most of it are very similar if not identical... if you have a magic solution for that.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​0fa9c20

trac #17385: more cleanup after reviewer's comment

[vdelecroix]

(wrong commit message, sorry)

[dcoudert]

I don't understand why you write

if not loops and any(u in neighb for u,neighb in data.iteritems()):
   if loops is False:

Obviously, if the first test is True, then we have loops==False. So you don't need the second one.

The same holds for if not weighted and any(...): if weighted is False: and if not multiedges and any(...): if multiedges is False: and ...

[vdelecroix]

Replying to dcoudert:

I don't understand why you write

if not loops and any(u in neighb for u,neighb in data.iteritems()):
   if loops is False:

Obviously, if the first test is True, then we have loops==False. So you don't need the second one.

Nope: loops can be None (or anything that does evaluate to False such as 0, [], (), etc). Have a look at 6.

[ncohen]

Yoooooooo !!

"While reading #17384, I thought that a global cleanup of Graph.init and DiGraph?.init would be good. We implement:"

Aahahaha. And do you want to know why I did not rewrite it all ? Because I thought that nobody would be willing to review the patch afterwards :-P

Thanks for your branch, I will try to review it today ;-)

Nathann

[vdelecroix]

Already two reviewers on #17385... for a "nobody" it is a lot! But if you have improvements to share, please do.

Vincent

[ncohen]

Yo !

Already two reviewers on #17385... for a "nobody" it is a lot! But if you have improvements to share, please do.

True true, I do not complain :-P

As to improvements, it was not really the goal: I would really like to make those functions cleaner by splitting them into subfunction, and perhaphs unify a bit better Graph/Digraph? is possible. Just a rewrite, but for a cleaner code.

Nathann

[ncohen]

By the way there is also this thing that has been waiting for a year or so ... #15706.

Nathann

[ncohen]

Hellooooooooo !

Well, I just finished reading the patch and it looks good, thanks for that ! One remark:

• Error on a loop: in the doctest you added, the error messages refers to a dictionary that the user never built. Also, "no loop but a loop" is not very informative.... What about 'The graph was built with loops=False but a loop was found in its data' or something ?

Nathann

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​ca66134

trac #17385: better error message

[ncohen]

sage -t --long /home/ncohen/.Sage/src/doc/en/thematic_tutorials/lie/affine_finite_crystals.rst
**********************************************************************
File "/home/ncohen/.Sage/src/doc/en/thematic_tutorials/lie/affine_finite_crystals.rst", line 359, in doc.en.thematic_tutorials.lie.affine_finite_crystals
Failed example:
    G.is_isomorphic(Gdual, edge_labels = True, certify = True)
Expected:
    (True, {[[1]]: [[-2]], [[2]]: [[-1]], [[-2]]: [[1]], [[-1]]: [[2]], []: [[0]]})
Got:
    (True, {[]: [[0]], [[1]]: [[-2]], [[2]]: [[-1]], [[-2]]: [[1]], [[-1]]: [[2]]})

[vdelecroix]

Replying to ncohen:

sage -t --long /home/ncohen/.Sage/src/doc/en/thematic_tutorials/lie/affine_finite_crystals.rst
**********************************************************************
File "/home/ncohen/.Sage/src/doc/en/thematic_tutorials/lie/affine_finite_crystals.rst", line 359, in doc.en.thematic_tutorials.lie.affine_finite_crystals
Failed example:
    G.is_isomorphic(Gdual, edge_labels = True, certify = True)
Expected:
    (True, {[[1]]: [[-2]], [[2]]: [[-1]], [[-2]]: [[1]], [[-1]]: [[2]], []: [[0]]})
Got:
    (True, {[]: [[0]], [[1]]: [[-2]], [[2]]: [[-1]], [[-2]]: [[1]], [[-1]]: [[2]]})

This has something to do with this ticket? Strictly speaking, those dictionary are the same... the thing is that the keys have no well defined ordering. The only reasonable thing I see is to remove this certify = True in the test. What do you think?

Vincent

[ncohen]

This has something to do with this ticket?

It seems. Does not happen otherwise O_o

Strictly speaking, those dictionary are the same... the thing is that the keys have no well defined ordering. The only reasonable thing I see is to remove this certify = True in the test. What do you think?

It is possible to test it with the_certificate == { the actual dictionary } but it seems overkill. +1 for a certify=False.

Nathann

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​472f7e0

trac #17385: fix doctest in affine finite crystals

[ncohen]

Looks good, thanks !

Nathann

P.S.: You should do a "git pull" on the develop branch

[vbraun]

Conflicts, probably #15706

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​a425713

Merge Sage-6.5.beta5

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0e8d1c4

trac #17385: uniq -> set (remains from #15706)

[vdelecroix]

Merged. I guess a last check-up would be fine.

Vincent

[ncohen]

Merged. I guess a last check-up would be fine.

I ran a "make ptestlong" just because my office's computer was feeling useless. No problem, good to go ;-)

Nathann