Opened 10 years ago

Closed 10 years ago

Create an efficient SUM command

Reported by: Owned by: ncohen jason, jkantor major sage-4.5 numerical mvngu, abmasse sage-4.5.alpha4 Nathann Cohen Robert Miller N/A

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

comment:1 Changed 10 years ago by ncohen

• Description modified (diff)
• Summary changed from Fix broken inequalities in add_constraint method to Create an efficient SUM command

comment:2 Changed 10 years ago by jason

Can you try `sage.misc.misc.balanced_sum`? It seems to get about the same speedup for me as you indicate.

```p = MixedIntegerLinearProgram()
v = p.new_variable()
%timeit sage.misc.misc.balanced_sum([v[i] for i in xrange(900)])
```

comment:3 Changed 10 years ago by jason

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 10 years ago by ncohen

• 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:6 Changed 10 years ago by ncohen

• Status changed from needs_review to needs_work

Rebased ! :-)

Nathann

comment:7 Changed 10 years ago by abmasse

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 10 years ago by rlm

• Authors set to Nathann Cohen
• Reviewers set to Robert Miller
• Status changed from needs_work to positive_review

comment:9 Changed 10 years ago by rlm

• Merged in set to sage-4.5.alpha4
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.