3 ms·

Slightly tangential, but I wonder if the massive amount of people using Python makes it easier to "sell" OR/SAT/etc. tools to developers. I've been working wit

Slightly tangential, but I wonder if the massive amount of people using Python makes it easier to "sell" OR/SAT/etc. tools to developers. I've been working with some young devs who only learned Python and web stuff (?!). One thing I've noticed about these devs is that they have some really bad intuitions about how long it takes to brute force problems like this. Brute forcing the hardest problem in this article requires less than 3 seconds for a C program but requires 3 minutes for a Python program. Bumping the capacity to 10,000 (so from 8 million options to one trillion options) takes about 40 minutes in C, but would probably take all day in Python. Once you get much past 10,000 the effort of pulling in a library starts to make sense because, even though C brute force is still tractable, you need to start parallelizing things and that's more effort than an import statement. Also, note to author: there are several mistakes in this article. There are bonds errors in your army examples and you used capacity = 19 instead of capacity = 1000 in one of the questions for the bread/meat/beer problem.

vikingerik 4y ago
Yet if the Python program took 3 fewer minutes to write/test/debug than the C program, then that way does come out ahead.
- throwawaygh 4y ago
  The code is identical, modulo minor syntactic sugar. We're talking about 6 ints, 3 for loops, and 3 boolean comparisons between integers.
runeblaze 4y ago
I think it is just not in standard curriculum. The algorithms class deals with theoretical bounds. The programming classes deal with OOP design. Only in competitive programming did I actually learn how to estimate running time.
klyrs 4y ago
I sat down for 2 minutes and wrote a brute-force solution that ran the 10k scenario in 400ms in python. Hint: you only need two loops.
- milansuk 4y ago
  I wrote it in C with just one loop: for(i=0; i <= 10000; i+=37) and one condition: if(i > 0 && i%13==0 && i%19==0) and it takes only 0.000003 sec.
  - klyrs 4y ago
    I was referring to the beer/meat/bread problem, but yeah. Brute force is ruthlessly effective for small problems.
  - shoo 4y ago
    if all the inputs are constants and don't depend on program input, it'd be interesting to disassemble that to see if the compiler solved the problem at compile time and generated a "load <constant_precomputed_solution>" you may not necessarily be timing what you think you are timing
- throwawaygh 4y ago
  > brute-force solution... Hint: you only need two loops. Well, yes, there are all sorts of tricks, including the use of a solver :) In my earlier post, read "brute-force" as "full enumeration". The comment was about dev's intuitions re: the time required to fully enumerate a space; ie when is it worth thinking about anything other than the stupidest solution possible.
shoo 4y ago
i agree that naively trying to do compute heavy stuff in pure python compared to C / cython is likely to be 100x slower, and 1000x slower than a thoughtfully rewritten array-oriented version of the computation in C / cython that allocates slabs of memory up front and then avoids frequent tiny allocations anywhere near hot loops. but real world applied optimisation problems (not simple illustrative toy problems as in the article) often have an exponentially large number of candidate or feasible solutions, attempting to brute force the search space in C is not going to be a fruitful exercise. e.g. you might be trying to solve a facility location problem to place `m` depots on nodes in a graph with `n` vertices, where each node can have 0 or 1 depot, so the space of feasible solutions is `2^n`, the powerset of the set of nodes. for a smallish applied problem, n might be `n=5000` . there might be a bunch of set-cover-like constraints that require a bunch of demand nodes on the graph are close enough to a depot node to be "covered", and objective function costs for each depot constructed or the distance from each demand node to the closest depot. commercial mixed integer solvers such as Gurobi have a whole bag of tricks to reduce the problem into a smaller problem during a presolve phase before the real MIP solver even gets woken up. a presolve phase employs a bunch of heuristics to detect common kinds of problem structure or substructure -- for example in the toy "optimisation and beer" problem it might immediately recognise that the only constraint is a knapsack constraint and palm the entire problem to a specialised knapsack solver which trivially solves the problem. more realistic applied problems are often weirder and messier -- more generally a presolve might be able to eliminate some but not all of the decision variables, or use substructure-specific techniques harvested from the literature to prove and inject additional constraints that make the real MIP solver's search space smaller.
- throwawaygh 4y ago
  > allocates slabs of memory up front and then avoids frequent tiny allocations anywhere near hot loops. My observation was intended primarily as a pedagogic critique. The C solutions to these problems don't require any cleverness and are transliterations of the Python equivalents. I agree re: optimizers of course. The article would be better if the final example was something where even really cleverly optimized "is this really correct?" enumeration techniques under-performed the optimizer.

vikingerik 4y ago

Yet if the Python program took 3 fewer minutes to write/test/debug than the C program, then that way does come out ahead.

throwawaygh 4y ago
The code is identical, modulo minor syntactic sugar. We're talking about 6 ints, 3 for loops, and 3 boolean comparisons between integers.

runeblaze 4y ago

I think it is just not in standard curriculum. The algorithms class deals with theoretical bounds. The programming classes deal with OOP design. Only in competitive programming did I actually learn how to estimate running time.

klyrs 4y ago

I sat down for 2 minutes and wrote a brute-force solution that ran the 10k scenario in 400ms in python. Hint: you only need two loops.

milansuk 4y ago
I wrote it in C with just one loop: for(i=0; i <= 10000; i+=37) and one condition: if(i > 0 && i%13==0 && i%19==0) and it takes only 0.000003 sec.
- klyrs 4y ago
  I was referring to the beer/meat/bread problem, but yeah. Brute force is ruthlessly effective for small problems.
- shoo 4y ago
  if all the inputs are constants and don't depend on program input, it'd be interesting to disassemble that to see if the compiler solved the problem at compile time and generated a "load <constant_precomputed_solution>" you may not necessarily be timing what you think you are timing
throwawaygh 4y ago
> brute-force solution... Hint: you only need two loops. Well, yes, there are all sorts of tricks, including the use of a solver :) In my earlier post, read "brute-force" as "full enumeration". The comment was about dev's intuitions re: the time required to fully enumerate a space; ie when is it worth thinking about anything other than the stupidest solution possible.

shoo 4y ago

i agree that naively trying to do compute heavy stuff in pure python compared to C / cython is likely to be 100x slower, and 1000x slower than a thoughtfully rewritten array-oriented version of the computation in C / cython that allocates slabs of memory up front and then avoids frequent tiny allocations anywhere near hot loops. but real world applied optimisation problems (not simple illustrative toy problems as in the article) often have an exponentially large number of candidate or feasible solutions, attempting to brute force the search space in C is not going to be a fruitful exercise. e.g. you might be trying to solve a facility location problem to place `m` depots on nodes in a graph with `n` vertices, where each node can have 0 or 1 depot, so the space of feasible solutions is `2^n`, the powerset of the set of nodes. for a smallish applied problem, n might be `n=5000` . there might be a bunch of set-cover-like constraints that require a bunch of demand nodes on the graph are close enough to a depot node to be "covered", and objective function costs for each depot constructed or the distance from each demand node to the closest depot. commercial mixed integer solvers such as Gurobi have a whole bag of tricks to reduce the problem into a smaller problem during a presolve phase before the real MIP solver even gets woken up. a presolve phase employs a bunch of heuristics to detect common kinds of problem structure or substructure -- for example in the toy "optimisation and beer" problem it might immediately recognise that the only constraint is a knapsack constraint and palm the entire problem to a specialised knapsack solver which trivially solves the problem. more realistic applied problems are often weirder and messier -- more generally a presolve might be able to eliminate some but not all of the decision variables, or use substructure-specific techniques harvested from the literature to prove and inject additional constraints that make the real MIP solver's search space smaller.

throwawaygh 4y ago
> allocates slabs of memory up front and then avoids frequent tiny allocations anywhere near hot loops. My observation was intended primarily as a pedagogic critique. The C solutions to these problems don't require any cleverness and are transliterations of the Python equivalents. I agree re: optimizers of course. The article would be better if the final example was something where even really cleverly optimized "is this really correct?" enumeration techniques under-performed the optimizer.