尝试优化大型文件的快速排序

Question

有人知道我如何更好地优化此代码以运行较大的文件。它适用于较小的输入，但是我需要它来运行一个超过200,000字的文件。有什么建议吗？

谢谢。

import random
import re

def quick_sort(a,i,n):
    if n <= 1:
        return
    mid = (len(a)) // 2
    x = a[random.randint(0,len(a)-1)]
    p = i - 1
    j = i
    q = i + n
    while j < q:
        if a[j] < x:
            p = p + 1
            a[j],a[p] = a[p],a[j]
            j = j + 1
        elif a[j] > x:
            q = q - 1
            a[j],a[q] = a[q],a[j]
        else:
            j = j + 1
    quick_sort(a,i,p-i+1)
    quick_sort(a,q,n-(q-i))

file_name = input("Enter file name: ")
my_list = []
with open(file_name,'r') as f:     
    for line in f:                     
        line = re.sub('[!#?,.:";\']', '', line).lower()
        token = line.split()    
        for t in token:
            my_list.append(t)

a = my_list
quick_sort(a,0,len(my_list))
print("List After Calling Quick Sort: ",a)

Answer 1

您为枢轴x使用的索引的随机选择正在使用输入列表a的整个大小，而不仅是您应该在当前调用中排序的部分。这意味着您的数据透视图通常根本不在当前部分中，因此您将无法有效地减少问题（因为所有值都在数据透视表的同一侧）。这会导致很多递归，对于较大的输入，您几乎总是会碰到递归上限。

解决方法很简单，只需更改获取x的方式即可：

x = a[random.randrange(i, i+n)]

[我喜欢randrange比randint好很多，但是如果您感觉相反，可以使用randint(i, i+n-1)。

Answer 2

您必须使用快速排序吗？如果可以使用heapq或PriorityQueue，则.get /（.pop()）方法将自动实现排序：

import sys
from queue import PriorityQueue

pq = PriorityQueue()

inp = open(sys.stdin.fileno(), newline='\n')

#inp = ['dag', 'Rug', 'gob', 'kex', 'mog', 'Wes', 'pox', 'sec', 'ego', 'wah'] # for testing
for word in inp:
    word = word.rstrip('\n')
    pq.put(word)

while not pq.empty():
    print(pq.get())

然后使用一些较大的随机单词输入或文件进行测试，例如：

shuf /usr/share/dict/words | ./word_pq.py

其中shuf是Gnu /usr/local/bin/shuf。