Opened 9 years ago
Closed 9 years ago
#9061 closed defect (fixed)
Create an efficient SUM command
Reported by: | ncohen | Owned by: | jason, jkantor |
---|---|---|---|
Priority: | major | Milestone: | sage-4.5 |
Component: | numerical | Keywords: | |
Cc: | mvngu, abmasse | Merged in: | sage-4.5.alpha4 |
Authors: | Nathann Cohen | Reviewers: | Robert Miller |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
This *HAS* to be changed :
p = MixedIntegerLinearProgram() v = p.new_variable() sage: %timeit sum([v[i] for i in xrange(900)]) 5 loops, best of 3: 1.14 s per loop
With this new function :
def mipvariables_sum(L): d = {} for v in L: for (id,coeff) in v._f.iteritems(): d[id] = coeff + d.get(id,0) return LinearFunction(d)
It gives :
sage: from sage.numerical.mip import mipvariables_sum sage: %timeit mipvariables_sum([v[i] for i in xrange(900)]) 625 loops, best of 3: 1.5 ms per loop
Even though it requires a new function to add MIPVariables, it is still better than nothing for the moment.
This patch will define the function given, and replace all the occurences of "sum" in the graph files to have them use this optimization.
Nathann
Attachments (1)
Change History (10)
comment:1 Changed 9 years ago by
- Cc mvngu added
- Description modified (diff)
- Summary changed from Fix broken inequalities in add_constraint method to Create an efficient SUM command
comment:2 Changed 9 years ago by
comment:3 Changed 9 years ago by
For me, the balanced_sum function gives these timings:
sage: p = MixedIntegerLinearProgram() sage: v = p.new_variable() sage: sage: %timeit sum([v[i] for i in xrange(900)]) 5 loops, best of 3: 1.48 s per loop sage: p = MixedIntegerLinearProgram() sage: v = p.new_variable() sage: %timeit sage.misc.misc.balanced_sum([v[i] for i in xrange(900)]) 25 loops, best of 3: 28.2 ms per loop
So I guess your function still wins (which isn't much of a surprise).
comment:4 Changed 9 years ago by
- Status changed from new to needs_review
This patch defines the function sage.numerical.mip.Sum and updates the LP functions to have them use it !
Nathann
comment:5 Changed 9 years ago by
- Cc abmasse added
comment:6 Changed 9 years ago by
- Status changed from needs_review to needs_work
Rebased ! :-)
Nathann
Changed 9 years ago by
comment:7 Changed 9 years ago by
Hello, Nathann!
Did you rebase it on sage-4.4.3? It seems so because it doesn't apply on sage-4.4.4. Since it touches many parts of the code, I don't know what would be the best strategy to make sure it is correctly based and it does not raise any problem with other patches.
Having looked at the code, it will probably be a fast review, as soon as I have checked for the improved efficiency.
comment:8 Changed 9 years ago by
- Reviewers set to Robert Miller
- Status changed from needs_work to positive_review
comment:9 Changed 9 years ago by
- Merged in set to sage-4.5.alpha4
- Resolution set to fixed
- Status changed from positive_review to closed
Can you try
sage.misc.misc.balanced_sum
? It seems to get about the same speedup for me as you indicate.