search

joschout / SubmodularMaximization

A collection of optimization algorithms for maximizing unconstrained submodular set functions.
Apache License 2.0
18 stars 2 forks source link

Ideas for speeding the code up #1

Closed arsovnino closed 3 years ago

arsovnino commented 3 years ago

Hi,

I have been using this implementation to optimize a rather computation intensive submodular function. However, the biased sampling and a few more things were acting as bottlenecks. I replaced set operations with numpy’s own set operations and did get a significant speedup. Any ideas about speeding this up even further?

I’m open to forking and making an upstream contribution so that we get a fast SLS...

joschout commented 3 years ago

Hi,

My focus when creating this repository was on readability of the algorithms. So I fully agree that some things can be made more efficient. An example is that instead of adding/removing elements to a Python set, it would be possible to represent the ground set as an array, and each subset as a binary mask into the ground set array. Although I am not sure whether this would lead to a speedup, as adding/removing elements to a python set has an expected time complexity O(1): https://wiki.python.org/moin/TimeComplexity

As this repository is not my main focus at the moment, perhaps the Apricot package might also help you further: https://github.com/jmschrei/apricot Also, Andreas Krause's SFO Matlab toolbox might give you some extra ideas: https://www.mathworks.com/matlabcentral/fileexchange/20504-submodular-function-optimization

joschout commented 3 years ago

But of course, you are more than welcome to make a fork and share your improvements :).

arsovnino commented 3 years ago

Hey, thanks! Actually I was thinking of using some fast C implementations of bit sets I have made in the past. They are going pretty low-level and use SIMD registries. If I find some free time I'll write Python wrappers for them and use them here :)

Thanks for the quick response.