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

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。

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

Trying to optimize quicksort for larger files

python

quicksort