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
- Branch set to public/graphs/30269_distribution
- Commit set to 871098ba94334e722ef8994b7343ed4f4dd71722
- Status changed from new to needs_review
comment:2 Changed 5 months ago by
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
- 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
- Commit changed from 871098ba94334e722ef8994b7343ed4f4dd71722 to a68be4a0442c0dbb51c5cb25b117069c0c25c9c2
comment:5 Changed 5 months ago by
- 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
- 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.
New commits:
trac #30269: better distances distribution