reframed icon indicating copy to clipboard operation
reframed copied to clipboard

Use `set()` instead of `[]` for `var_ids` in Solver

Open Prunoideae opened this issue 1 year ago • 2 comments

https://github.com/cdanielmachado/reframed/blob/1927419e9d7d986e8c3e7f86a442c839373d8b8d/reframed/solvers/solver.py#L36-L40

Will make add_variable to have performance regression if over 40k variables are added into the problem, and adding 200k variables will have 10mins overhead due to the query of a python list is O(n):

image

While replacing it with set() will make it done within a second as the set is O(1) complexity:

image

Prunoideae avatar Jul 14 '24 09:07 Prunoideae

Thank you, that is very useful feedback!

I'm actually working on refactoring that class (outside the main branch):

https://github.com/cdanielmachado/reframed/compare/solvers

And I just replaced lists with dicts... i wonder how they compare to sets.

Just out of curiosity, which solver are you using ?

cdanielmachado avatar Jul 14 '24 19:07 cdanielmachado

I think dict is the same as set as they both are based on a hash table to query or insert items. Languages like Java don't have a separate implementation of sets, where they are just dict with only keys and empty values.

I was using a fine-tuned Gurobi solver with an academic license. The MILP problem being solved was somehow infeasible due to the presence of a few metabolic models, so I reran the solving for several times to debug and noticed the performance problem.

Prunoideae avatar Jul 15 '24 00:07 Prunoideae