时间戳

首页 > 解决方案 > 尝试为更大的文件优化快速排序

python - 尝试为更大的文件优化快速排序

问题描述

有谁知道我可以如何更好地优化此代码以运行更大的文件。它适用于较小的输入，但我需要它来运行超过 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)

标签： pythonquicksort

解决方案

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

修复很简单，只需更改获取方式x：

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

我喜欢randrange比 好得多randint，但randint(i, i+n-1)如果你有其他感觉，你可以使用。

推荐阅读