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 ncohen)

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)

trac_9061.patch (32.1 KB) - added by ncohen 9 years ago.

Download all attachments as: .zip

Change History (10)

comment:1 Changed 9 years ago by ncohen

  • 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 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 9 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 9 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:5 Changed 9 years ago by ncohen

  • Cc abmasse added

comment:6 Changed 9 years ago by ncohen

  • Status changed from needs_review to needs_work

Rebased ! :-)

Nathann

Changed 9 years ago by ncohen

comment:7 Changed 9 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 9 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 9 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.