Opened 4 years ago

Closed 4 years ago

#17384 closed defect (fixed)

Slowness when calling Graph(a_dictionary)

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.5
Component: graph theory Keywords:
Cc: vdelecroix, tscrim, dimpase, dcoudert, jmantysalo, azi Merged in:
Authors: Nathann Cohen Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: c4bf5cf (Commits) Commit: c4bf5cf6a589bd1f42afc249fad8e82bf35d596a
Dependencies: Stopgaps:

Description

It has been reported by Jean Betrema on sage-devel [1] that building a graph from a dictionary was actually quite slow

sage: d=graphs.Grid2dGraph(100,100).to_dictionary()
sage: %time Graph(d)
CPU times: user 2.67 s, sys: 20 ms, total: 2.69 s
Wall time: 2.63 s
Graph on 10000 vertices

This does not make any sense, and indeed it only comes from a miswritten line in the code. After this branch is applied, it becomes

sage: d=graphs.Grid2dGraph(100,100).to_dictionary()
sage: %time Graph(d)
CPU times: user 104 ms, sys: 4 ms, total: 108 ms
Wall time: 97.2 ms
Graph on 10000 vertices

Nathann

[1] https://groups.google.com/d/msg/sage-devel/x3h4m3LjWkI/1HY80TsjxCoJ

Change History (7)

comment:1 Changed 4 years ago by ncohen

  • Branch set to u/ncohen/17384
  • Component changed from PLEASE CHANGE to graph theory
  • Status changed from new to needs_review

comment:2 Changed 4 years ago by git

  • Commit set to c4bf5cf6a589bd1f42afc249fad8e82bf35d596a

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

c4bf5cftrac #17384: Slowness when calling Graph(a_dictionary)

comment:3 Changed 4 years ago by ncohen

  • Cc jmantysalo added

comment:4 Changed 4 years ago by ncohen

  • Cc azi added

comment:5 follow-up: Changed 4 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to positive_review

I love this set().union(...) ;-D

There are other easy optimizations... follow-up on #17385

Vincent

comment:6 in reply to: ↑ 5 Changed 4 years ago by ncohen

Yo !

There are other easy optimizations... follow-up on #17385

Ahahah. Yeah yeah, you taught me that trick in some design patch I believe :-)

Thanks for the review !

Nathann

comment:7 Changed 4 years ago by vbraun

  • Branch changed from u/ncohen/17384 to c4bf5cf6a589bd1f42afc249fad8e82bf35d596a
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.