Opened 6 months ago

Closed 5 months ago

#30269 closed enhancement (fixed)

memory efficient implementation of distances distribution

Reported by: dcoudert Owned by:
Priority: major Milestone: sage-9.2
Component: graph theory Keywords:
Cc: gh-vipul79321 Merged in:
Authors: David Coudert Reviewers: Jonathan Kliem
Report Upstream: N/A Work issues:
Branch: a68be4a (Commits) Commit: a68be4a0442c0dbb51c5cb25b117069c0c25c9c2
Dependencies: Stopgaps:

Description

We reduce space usage from O(n^2) to O(n) in the computation of distances distribution of unweighted (di)graphs by avoiding to compute and store into memory the full distance matrix.

Change History (6)

comment:1 Changed 6 months ago by dcoudert

  • Branch set to public/graphs/30269_distribution
  • Commit set to 871098ba94334e722ef8994b7343ed4f4dd71722
  • Status changed from new to needs_review

New commits:

​871098btrac #30269: better distances distribution

comment:2 Changed 5 months ago by gh-kliem

Why don't you use calloc for count? I heard it might be faster, because sometimes the allocator knows where memory initialized to 0 is. It's also one less line.

Otherwise looks good.

comment:3 Changed 5 months ago by gh-kliem

  • Reviewers set to Jonathan Kliem

You can put it on positive review once done (or of course argue why it is more natural etc. not to use calloc).

comment:4 Changed 5 months ago by git

  • Commit changed from 871098ba94334e722ef8994b7343ed4f4dd71722 to a68be4a0442c0dbb51c5cb25b117069c0c25c9c2

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

​5928a37trac #30269: merged with 9.2.beta8
​a68be4atrac #30269: use calloc instead of allocarray

comment:5 Changed 5 months ago by dcoudert

  • Status changed from needs_review to positive_review

You are right, it's better to use calloc here.

Thank you.

comment:6 Changed 5 months ago by vbraun

  • Branch changed from public/graphs/30269_distribution to a68be4a0442c0dbb51c5cb25b117069c0c25c9c2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.