python - 为什么多线程快速排序比Python中的普通快速排序慢？

Question

尽管我的处理器是双核，但使用多线程实现的快速排序的性能低于普通快速排序。

请提供提高多线程性能的建议。

我正在上传两个版本的快速排序以及用 python3(3.5.2) 编写的示例测试用例生成器

多线程快速排序

#quicksort in multithreading

from queue import Queue 
import threading
import time

n = int(input().strip())
arr = [int(arr_temp) for arr_temp in input().strip().split(' ')]
f = open('results.txt','w')

q = Queue()
q.put([0,n-1])

def aux(i,j):
    if i<j:
        pivot = j
        k = 0
        global arr 
        while k<pivot:
            if arr[k]>arr[pivot]:
                tmp = arr[k]
                itr = k+1
                while itr<=pivot:
                    arr[itr-1]=arr[itr]
                    itr+=1
                arr[pivot]=tmp

                k-=1
                pivot-=1
            else:
                pass
            k+=1
        q.put([i, pivot-1])
        q.put([pivot+1, j])
    else:
        pass



def qsort_threader():
    while  True:
        if q.empty():
            pass
        else:
            indices = q.get()
            aux(indices[0],indices[1])
            q.task_done()


start = time.time()

for i in range (0,15):
    t = threading.Thread(target = lambda: qsort_threader())
    t.daemon = True
    t.start()

q.join()
print(time.time()-start)
f.write(str(arr))

这也是普通版本

普通快速排序

#normal quicksort

import threading
import time

n = int(input().strip())
arr = [int(arr_temp) for arr_temp in input().strip().split(' ')]
f = open('results.txt','w')

def xsort(i=0,j=n-1):
    #print(threading.currentThread().getName())
    if i<j:
        pivot = j
        k = 0
        global arr 
        while k<pivot:
            if arr[k]>arr[pivot]:
                tmp = arr[k]
                itr = k+1
                while itr<=pivot:
                    arr[itr-1]=arr[itr]
                    itr+=1
                arr[pivot]=tmp

                k-=1
                pivot-=1
            else:
                pass
            k+=1

        xsort(i,pivot-1)
        xsort(pivot+1,j)
    else:
        pass



start = time.time()
xsort()
print(time.time()-start)
f.write(str(arr))
f.close()

下面是测试代码生成器

测试用例生成器

f = open('testfile.txt','w')
n = int(input("no of integers to generate ? "))
f.write(str(n)+'\n')
from random import randint as r
for i in range(0,n):
    f.write(str(r(-100000,100000))+' ')
f.close()

我还上传了在 10000 个未排序随机数的测试用例上运行程序期间 CPU 性能图的屏幕截图

正常快速排序期间的CPU图表

see the 100% usage of CPU-3

多线程快速排序期间的CPU图

No CPU is utilized properly

普通快速排序在 20.041423797607422 秒内完成任务。多线程快速排序在 27.749499320983887 秒内完成。

Answer 1

你看著名的GIL实际应用:“互斥锁可防止多个 native 线程同时执行 Python 字节码”。

Guido 的建议是使用 multiprocessing使用 IPC 消息传递而不是具有共享状态的线程。

如果对稳定性没有特殊要求，可以尝试PyPy-STM ，这是移除 GIL 最彻底的尝试。