python - 为什么我的线程 python 合并排序的 CPU 使用率对于每个内核只有 50%？

Question

问题

为什么我的线程 python 合并排序的 CPU 使用率对于每个内核只有 50%？

为什么这会导致相对较小的输入（100000）出现“无法创建新线程”错误

我怎样才能使它更pythonic？（非常难看。）

Linux/Ubuntu 12.4 64 位 i5 移动（四）

from random import shuffle
from threading import *

import time
import Queue


q = Queue.LifoQueue()

def merge_sort(num, q):
  end = len(num)

  if end > 1:
    mid = end / 2
    thread = Thread(target=merge_sort, args=(num[0:mid],q,))
    thread1 = Thread(target=merge_sort, args=(num[mid:end],q,))

    thread.setDaemon(True)
    thread1.setDaemon(True)

    thread.start()
    thread1.start()

    thread.join()
    thread1.join()

    return merge(q.get(num), q.get(num))
  else:
    if end != 0:
     q.put(num)
    else:
     print "?????"
     return


def merge(num, num1):
  a = []
  while len(num) is not 0 and len(num1) is not 0:
    if num[0] < num1[0]:
      a.append(num.pop(0))
    else:
      a.append(num1.pop(0))
  if len(num) is not 0:
    for i in range(0,len(num)):
      a.append(num.pop(0))
  if len(num1) is not 0:
    for i in range(0,len(num1)):
      a.append(num1.pop(0))
  q.put(a)
  return a



def main():

    val = long(raw_input("Please enter the maximum value of the range:")) + 1
    start_time = time.time()
    numbers = xrange(0, val)
    shuffle(numbers)


    numbers = merge_sort(numbers[0:val], q)

#    print "Sorted list is: \n"
#    for number in numbers:
#      print number

    print str(time.time() - start_time) + " seconds to run.\n"

if __name__ == "__main__":
    main()

Answer 1

对于 100000 输入，您的代码尝试创建 ~200000 个线程。Python 线程是真正的 OS 线程，因此您看到的 50% CPU 负载可能是系统忙于处理线程。在我的系统上，错误发生在大约 32000 个线程左右。

您编写的代码不可能工作：

from random import shuffle

#XXX won't work    
numbers = xrange(0, val)
shuffle(numbers)

xrange()不是可变序列。

注意：排序所花费的时间比数组的随机洗牌要少得多：

import numpy as np

numbers = np.random.permutation(10000000) # here spent most of the time
numbers.sort()

如果要使用不同的线程对数组的某些部分进行排序；你能行的：

from multiprocessing.dummy import Pool # use threads 

Pool(2).map(lambda a: a.sort(), [numbers[:N//2], numbers[N//2:]])

a.sort()释放 GIL，因此代码使用 2 个 CPU。

如果您包括合并排序部分所需的时间；numbers.sort()在单个线程中一次（）对整个数组进行排序可能会更快。

Answer 2

您可能想考虑使用Parallel Python，因为默认情况下，由于Global Interpreter Lock (GIL) ， CPython将被限制为一个核心。这就是 CPython 无法执行真正的 CPU 绑定并发操作的原因。但是，CPython 仍然擅长执行 IO 绑定任务。

这里有一篇很好的文章描述了 CPyton 的线程限制。