在Python中使用多线程计算阶乘

Question

我使用Python2.7，有一个任务是编写一个使用多个线程计算阶乘的函数。我试着用传统的递归方法，比如

def factorial(n):
    if n < 1:
        return 1
    else:
        return n * factorial(n - 1)

但这种方式似乎不适合多线程处理。有没有使用多线程计算阶乘的方法？在

Answer 1

我真的很喜欢the idea presented in the other answer。在

当阶乘是数[1，n]的computed as the product时：

numbers = range(1,n+1)

您可以使用切片生成要由工人处理的数字。例如：

^{pr2}$

Map这是一个process pool，然后减少这些产品的结果得到你的最终解决方案。在

不要使用threading模块来实现这一点。这是一个占用CPU的任务，它将被Global Interpreter Lock阻止。multiprocessing模块使用进程而不是线程来绕过这一步。在

Answer 2

阶乘就是一系列数字的相乘。因为乘法是associative，所以可以按任何顺序乘法。更具体地说，可以将序列分成任意数量的部分，独立地将这些部分相乘，然后组合结果。在

由于CPython的GIL，您可能一次只运行一个线程，但任务的本质可能是简单地练习线程同步。在

^{}和^{}看起来是适合这份工作的工具。我将给出两个可能实现的示例：

• 创建一个Queue和多个Thread对象，每个对象都将
  • 乘以预定义的数字范围，然后
  • 将结果放入队列。在
• 启动线程并等待它们完成
• 在主线程中，将队列中的所有数字相乘

另一个更有趣的实现是：

• 将所有要相乘的数字压入Queue

• 创建多个线程，每个线程将

  • 从内部状态1开始
  • 从Queue中取一个数字，如果可以的话（即不阻塞）
  • 把状态乘以它

• 这里有趣的部分是如何在队列为空后继续操作：

  • 线程可以简单地将结果推送到另一个Queue并退出，让主线程在所有线程退出后进行最后的乘法

  • 相反，线程可能会将结果推回到队列并退出。但是，您需要以某种方式确保在获得最终结果（并将其推入队列）之前并不是所有线程都退出。在

    • 一种方法是在联锁计数器中跟踪有多少部分结果被推送到队列中，并防止线程在检测到要处理最后一个结果时退出：

      #at initialization
      partial_results_lock = threading.Lock()
      partial_results_left=<number of threads>
      
      # in the thread, if the queue is empty
      with partial_results_lock:
          queue.push(state)
          state=1
          partial_results_left-=1
          if partial_result_left!=0: return # after we start over and push
                                            #the final result, the counter will become -1
      <start over>
      

Answer 3

在多线程应用程序中，最好最小化不同线程之间存在的数据依赖关系。在

在您提到的阶乘递归解决方案中，很难找到不依赖于其他计算结果的计算。在

一种不同的方法是将阶乘分解成多个部分。 例如，对于两个线程，可以执行以下操作：

n! = [1 * 2 * 3 * .. * (n/2)] * [(n/2 + 1) * ... * n]

第一个线程将计算值：

v1 = 1 * 2 * 3 * .. * (n/2)

第二个线程将计算：

v2 = (n/2 + 1) * ... * n

然后，当两个线程都完成时，主线程将计算n! = v1 * v2。在

这可以通过将输入阶乘分解为k不同的部分（而不是上面的示例中的两个）来推广使用k线程。在