尽管我的处理器是双核,但使用多线程实现的快速排序的性能低于普通快速排序。
请提供提高多线程性能的建议。
我正在上传两个版本的快速排序以及用 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图表
多线程快速排序期间的CPU图
普通快速排序在 20.041423797607422 秒内完成任务。 多线程快速排序在 27.749499320983887 秒内完成。
最佳答案
你看著名的GIL实际应用:“互斥锁可防止多个 native 线程同时执行 Python 字节码”。
Guido 的建议是使用 multiprocessing使用 IPC 消息传递而不是具有共享状态的线程。
如果对稳定性没有特殊要求,可以尝试PyPy-STM ,这是移除 GIL 最彻底的尝试。
关于python - 为什么多线程快速排序比Python中的普通快速排序慢?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41893866/