为什么我的线程python merge sort的CPU使用率只有每个内核的50%？

Question

问题

为什么我的线程python merge sort的CPU使用率仅为每个内核的50%？在

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

我怎样才能让这个更像Python？（很难看。）

Linux/Ubuntu12.4 64位i5移动（quad）

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

您可能需要研究使用Parallel Python，因为默认情况下，CPython将被限制为一个核心，因为Global Interpreter Lock (GIL)。这就是为什么CPython不能执行真正的CPU绑定并发操作。但是，CPython仍然很擅长执行IO绑定的任务。在

有一篇很好的文章描述了CPytonhere的线程限制。在

Answer 2

对于100000个输入，代码尝试创建大约200000个线程。Python线程是真正的操作系统线程，因此您看到的50%的CPU负载可能是系统忙于处理线程。在我的系统中，大约有32000个线程出错。在

您编写的代码可能无法工作：

from random import shuffle

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

xrange()不是可变序列。在

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

^{pr2}$

如果要使用不同的线程对数组的部分进行排序，可以执行以下操作：

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()）进行排序可能会更快。在