環境
>>> import pulp >>> pulp.__version__ '2.5.1'
本文
制約を大量に追加する場合 例えば;
を追加した場合、下記のコードだと実行時間 28.81 s かかります。(f(i)は実数を返す何かしらの関数)
prob = pulp.LpProblem() # 変数の生成 x = [pulp.LpVariable(f'x{i}', 0, 1, 'Continuous') for i in range(10000)] sum_x = pulp.lpSum(x) for i in range(1000): prob += sum_x <= f(i) # 制約の追加
ここで、
prob = pulp.LpProblem() # 変数の生成 x = [pulp.LpVariable(f'x{i}', 0, 1, 'Continuous') for i in range(10000)] sum_x = pulp.lpSum(x) for i in range(1000): - prob += sum_x <= f(i) # 制約の追加 + sum_x.subInPlace(f(i)) # sum_x - f(i) ← sum_x + prob += pulp.LpConstraint(sum_x, pulp.const.LpConstraintLE) # sum_x - i < 0 + sum_x.addInPlace(f(i)) # sum_x ← sum_x - f(i)
に書き換えた場合、実行時間は 16.41 s になります。
なぜ速くなるか
下記のコードは全て GitHub - coin-or/pulp at v2.1 から抜粋.
class LpElement(object) の__sub__
メソッドは以下のように定義されいて、
def sub(self, other): return LpAffineExpression(self) - other
そしてclass LpAffineExpression(_DICT_TYPE)の__sub__
メソッドは
def sub(self, other): return self.copy().subInPlace(other) def copy(self): """Make a copy of self except the name which is reset""" # Will not copy the name return LpAffineExpression(self)
というようにオブジェクトの生成(copy)が一回挟まれます。
それに比べてclass LpAffineExpression(_DICT_TYPE)のsubInPlaceは
オブジェクトの生成なしに直接self.constantを変更して、引き算を反映させるのでオブジェクトの生成が行われません。
基本的に新しいオブジェクト生成時にはメモリ確保から行われますが、このメモリの動的確保は通常の演算と比較してかなり時間がかかります。 そのためこのメモリの動的確保を省略できているので、速くなっているんですね。
def subInPlace(self, other): if isinstance(other,int) and (other == 0): return self if other is None: return self if isinstance(other,LpElement): self.addterm(other, -1) elif isinstance(other,LpAffineExpression): self.constant -= other.constant for v,x in other.items(): self.addterm(v, -x) elif isinstance(other,dict): for e in other.values(): self.subInPlace(e) elif (isinstance(other,list) or isinstance(other, Iterable)): for e in other: self.subInPlace(e) else: self.constant -= other return self