Evaluating a function parallely using itertools product

Question

I have to evaluate a function (let's call it my_func()) that takes 8 parameters as input and returns a scalar upon different matrix computations. Since I don't have any constrains on my_func(), I have no choice but to brute force all possibilities which amounts to 8^8 = 16777216. I started off using itertools's product functions and passed the generated sequences to the my_func() sequentially. Kindly take a look at the sample of my code below,

So far.....

from itertools import product
import numpy as np

def my_func(a,b,c,d,e,f,g,h): #Function that I have to evaluate
    #do some matrix computations and return some scalar q# 
    return q

def Evaluate():
    Range = [x for x in np.arange(0,3.60,0.5)] # A list that contains 8 elements
    it = itertools.product(Range, repeat=8) #Generate all possiblities
    Max = 0
    for i in it:
        Sum = my_func(*i)
        if Sum > Max:
            Max = present
    return Max

Result = Evaluate() #Output

Pitfalls...

Unfortunately, executing the above code sequentially takes ages to produce the output. This is because my_func is quite heavy. I have no choice but to somehow parallelize this code so that I can take advantage of multiple processors available to run my code.

Questions:

Since itertools.product is a generator I cannot parallelize this to evaluate my_func() simultaneously for different sets of parameters. Is there any way I can parallelize the code? if no is the asnswer, should I abondon the idea of using itertools and try someting else?

Kindly help me find a solution.

Thanks for suggesting any ideas.

Cheers!!

is the function that returns the scalar symmetric under index permutations? if I do f(1,0,0...,0) does it return the same as f(0,0,...,1)? — elelias, Mar 17 '16 at 13:40
Unfortunately, the scalar is not symmetric under permutations, I wish it would have been. The function returns different values for different sets of arguments. — Prdeep_nitro, Mar 17 '16 at 13:45
Your code appears to be missing a line, eg `for i in it:`. BTW, `my_func(*i)` is more compact than your call. Also consider `Range = [i/2 for i in range(8)]`; make that `i/2.` if your on Python 2 and not using `from __future__ import division`. — PM 2Ring, Mar 17 '16 at 13:55
@PM 2Ring thanks for the suggestions. I have added that missing line to my code. cheers!! — Prdeep_nitro, Mar 17 '16 at 14:16

score 4 · Accepted Answer · answered Mar 17 '16 at 13:37

4

You can parallelize a generator ! You can use the multiprocessing library, which offers the Pool class which does exactly what you want. Here you can get more ample documentation, but essentially, what you want to do is :

with Pool(processes=4) as pool:
  pool.map(my_func, itertools.product(Range, repeat=8))

You should look into the alternatives to pool.map to find the one which suits you most.

answered Mar 17 '16 at 13:37

alpha1554

605
5
15

Thanks for the quick reply. I noticed that by mapping itertools.product(Range, repeat=8) to my_func, soon runs out of memory. I think all the 8^8 possibilities are generated, stored and then passed as chunks to different processors. Any workarounds? – Prdeep_nitro Mar 17 '16 at 14:44
You may want to look into the answers given here : http://stackoverflow.com/questions/5318936/python-multiprocessing-pool-lazy-iteration and here : http://stackoverflow.com/questions/14677287/multiprocessing-with-large-data – alpha1554 Mar 17 '16 at 15:08

Ami Tavory · Answer 2 · 2016-03-17T15:11:44.713

The number of cores you'll use is probably much smaller than 8⁸ .

This leads to the following parallallelization scheme. Call multiprocessing.Pool.map on

itertools.product(<all-combinations-of-first-2-or-3-parameters>)

Within each process, perform the parallellization on the remaining parameters, and return only a single result - the best tuple of parameters found.

This will be much more efficient anyway than passing each of the 8⁸ combinations. There's an overhead to these things.

Example

Say you decide to map over the first three parameters. Then your product is a sequence of triplets: ..., (1, 3, 2), .... You use something like multiprocessing.Pool.map on each such triplet, so let's consider it from the point of view of the function:

def find_best_for_triplet(xyz):
    x, y, z = xyz[0], xyz[1], xyz[2]

    for ... in itertools.product(<all-combinations-of-last-5-parameters>)
        # Here you have all 8 of your parameters: x, y, z, and the last 5

    return xyz + (last-five-parameters) of the min

On a separate matter - in practice, the Nelder Mead method works well on optimizing high-dimensional problems, and is much cheaper than brute force. You might wish to give an implementation of it a try.

Hello Dr. Tavory, Thanks for the help. Certainly passing 8^8 combinations is a lot of overhead, in fact number of parameters will even go up to 10, then I have to brute-force 10^10 which is awful lot. I read your answer several times but couldn't get my head around it. Are you suggesting to evaluate the function with only a subset of parameters (keeping the rest const) in a single process? Could you kindly explain a bit further in your answer? — Prdeep_nitro, Mar 17 '16 at 14:54
@Prdeep_nitro I've added a clarification/explanation. Let me know if you need something further. — Ami Tavory, Mar 17 '16 at 15:12

Evaluating a function parallely using itertools product

2 Answers2