Оптимизация и многопроцессорная обработка определенной части программы c для более быстрого выполнения

Question

Я запускаю специальную c программу, на завершение которой требуется много времени, и затем я понял, что могу делать что-то совершенно глупое. В сочетании с тем фактом, что программа не использует полную мощность моего процессора, я обращаюсь за помощью в оптимизации ядра кода.

Мне не очень комфортно с многопроцессорной обработкой в ​​Python, и поэтому ответы по всему сайту не очень помогают.

Специфический код c, с которым я работаю:

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

Проблема в том, что массив people может быть огромным списком (k может быть огромным числом), а количество операций в худшем случае имеет порядок k факториала, который может быть довольно большой

Я хотел бы использовать любые оптимизации, которые вы можете предложить, а также, если возможно, узнать, как использовать многопроцессорность здесь. У меня есть 8 виртуальных ядер, если это поможет.

Любой вклад приветствуется.

Answer 1

Не думаю, что это может быть быстрее, чем это:

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))))

Размер - это размер каждого набора выживших, если вы хотите количество синглетонов:

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