CODEWITHSUNDEEP
pythonpython-3.xoptimizationpython-multiprocessing
Yuzuriha Inori
Yuzuriha Inori

Reputation: 165

Optimizing and multiprocessing a specific part of program for faster execution

I am running a specific program which takes ages to complete, and then I realized I might be doing something entirely stupid. Combining this with the fact that the program does not utilize the full power of my CPU, I turn here for help in optimizing the core of the code.

I am not very comfortable with multiprocessing in Python, and so the answers all around this site are not helping that much.

The specific code I am working with is:


k=10000

for i in range(2,k):
  n=i

  people=[]
  for i in range(1,n+1):
    people.append(i) #create list of people, labelled with integers

  while(len(people)>1): #the game ends when there is 0 or 1 people left
    shoot=[]

    for i in people:
      choice=i
      while(choice==i):
        choice=random.choice(people) #i-th chooses a person to kill and can't choose himself
      shoot.append(choice)

    for i in shoot:
      if(i in people):
        people.remove(i) #remove killed people

The problem is that the people array can be a huge list (k an be a huge number) and the number of operations in the worst case is of the order of k factorial which can be pretty large.

I would like to use any optimizations you might suggest and also, if possible, to know how to use multiprocessing here. I have 8 virtual cores if that's any help.

Any input is appreciated.

Upvotes: 1

Views: 76

Answers (1)

Bruno Mello
Bruno Mello

Reputation: 4618

I don't think it can be faster than this: 

import numpy as np
import concurrent
import random

k=10
num_workers = 8

def choose_shoot(people, idx):
    shoot = random.choice(tuple(people - set([idx])))
    return shoot

def find_shoot(n):

    people = set(np.arange(1, n+1))

    while(len(people)>1):

        shoot = set([*map(lambda x: choose_shoot(people, x), people)])
        people = set([*filter(lambda x: x not in shoot, people)])

    return people, len(people)

with concurrent.futures.ThreadPoolExecutor(max_workers=num_workers) as pool:
        survivors, sizes = zip(*list(pool.map(find_shoot, range(2, k+1))))

The sizes is the size of each set of survivors if you want the number of singletons:

num_singletons = sizes.count(1)
num_empty = sizes.count(0)

Upvotes: 1

Related Questions