Попытка оптимизировать быструю сортировку для больших файлов - PullRequest
Новая
       16

Попытка оптимизировать быструю сортировку для больших файлов

1 голос
/ 01 мая 2020

Кто-нибудь знает, как я могу оптимизировать этот код лучше для запуска больших файлов. Это работает с меньшими входами, но мне нужно, чтобы запустить файл с более чем 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)

Ответы [ 2 ]

2 голосов
/ 01 мая 2020

Ваш случайный выбор индекса, который будет использоваться для вашей оси x, использует весь размер входного списка a, а не только часть, которую вы должны сортировать в текущем вызове. Это означает, что очень часто ваш свод вообще не будет в текущем разделе, и поэтому вы не сможете эффективно уменьшить проблему (потому что все значения будут на одной стороне сводки). Это приводит к большому и большему количеству рекурсий, а для больших входов вы почти всегда попадете в верхний предел рекурсии.

Исправление простое, просто измените способ получения x: 

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

Мне нравится randrange намного лучше, чем randint, но вы можете использовать randint(i, i+n-1), если чувствуете другое.

0 голосов
/ 01 мая 2020

Должны ли вы использовать быструю сортировку? Если вы можете использовать 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 - это Гну /usr/local/bin/shuf.

...