Quicksort Python - List comprehension vs Recursion (thói quen phân vùng)

Question

Tôi đã xem bài nói chuyện Three Beautiful Quicksorts và đang rối tung xung quanh với quicksort. Việc thực hiện của tôi trong python rất giống với c (chọn trục xoay, phân vùng xung quanh nó và đệ quy trên phân vùng nhỏ hơn và lớn hơn). Mà tôi nghĩ không phải là pythonic.

Vì vậy, đây là triển khai sử dụng tính năng hiểu danh sách trong python.

def qsort(list): 
    if list == []: 
     return [] 
    pivot = list[0] 
    l = qsort([x for x in list[1:] if x < pivot]) 
    u = qsort([x for x in list[1:] if x >= pivot]) 
    return l + [pivot] + u 

Cho phép gọi đệ quy metho qsortR. bây giờ tôi nhận thấy rằng qsortR chạy chậm hơn nhiều so với qsort cho các danh sách lớn (r). Trên thực tế "độ sâu đệ quy tối đa vượt quá trong cmp" ngay cả đối với 1000 elems cho phương pháp đệ quy. Mà tôi đặt lại trong sys.setrecursionlimit.

Một số con số:

list-compr 1000 elems 0.491770029068 
recursion 1000 elems 2.24620914459 
list-compr 2000 elems 0.992327928543 
recursion 2000 elems 7.72630095482 

Tất cả mã là here.

Tôi có một vài câu hỏi:

• Tại sao danh sách hiểu nhanh hơn rất nhiều?
• Một số chứng ngộ về giới hạn đệ quy trong python. Lần đầu tiên tôi đặt nó là 100000 trong trường hợp nào tôi nên cẩn thận?
  • (chính xác nghĩa là gì 'tối ưu hóa đệ quy đuôi', làm thế nào nó được thực hiện?)
• Cố gắng sắp xếp 1000000 yếu tố hogged bộ nhớ của máy tính xách tay của tôi (với phương pháp đệ quy). Tôi nên làm gì nếu tôi muốn sắp xếp quá nhiều yếu tố? Loại tối ưu hóa nào có thể?

Answer 1

1. Tại sao danh sách hiểu nhanh hơn rất nhiều?

   Vì việc hiểu danh sách ngụ ý vòng lặp C nhanh hơn nhiều so với cách chung chung của việc sử dụng khối for của Python.

2. Một số chứng ngộ về giới hạn đệ quy trong python. Lần đầu tiên tôi đặt nó là 100000 trong trường hợp nào tôi nên cẩn thận?

   Trong trường hợp bạn hết bộ nhớ.

3. Đang cố gắng sắp xếp 1000000 phần tử lưu trữ bộ nhớ của máy tính xách tay của tôi (với phương pháp đệ quy). Tôi nên làm gì nếu tôi muốn sắp xếp quá nhiều yếu tố? Loại tối ưu hóa nào có thể?

   Đệ trình đệ quy của Python mang lại chi phí như vậy vì mọi cuộc gọi hàm phân bổ nhiều không gian bộ nhớ ngăn xếp cho mỗi cuộc gọi.

   Nói chung, lặp lại là câu trả lời (sẽ cho hiệu suất tốt hơn trong 99% các trường hợp sử dụng thống kê).

   Nói về cấu trúc bộ nhớ, nếu bạn có cấu trúc dữ liệu đơn giản, như ký tự, số nguyên, phao nổi: hãy sử dụng tích hợp array.array, bộ nhớ này hiệu quả hơn nhiều so với list.

Answer 2

Bạn đã thử viết một triển khai không đệ quy là partition? Tôi nghi ngờ rằng sự khác biệt hiệu suất là hoàn toàn việc thực hiện partition. Bạn đang đệ quy cho từng yếu tố trong việc triển khai của bạn.

Cập nhật

Dưới đây là một thực hiện nhanh chóng. Nó vẫn không siêu nhanh hoặc thậm chí hiệu quả, nhưng nó tốt hơn nhiều so với đệ quy ban đầu của bạn.

>>> def partition(data): 
... pivot = data[0] 
... less, equal, greater = [], [], [] 
... for elm in data: 
... if elm < pivot: 
... less.append(elm) 
... elif elm > pivot: 
... greater.append(elm) 
... else: 
... equal.append(elm) 
... return less, equal, greater 
... 
>>> def qsort2(data): 
... if data: 
... less, equal, greater = partition(data) 
... return qsort2(less) + equal + qsort2(greater) 
... return data 
... 

Tôi cũng nghĩ rằng có một số lượng lớn danh sách tạm thời được tạo trong phiên bản "truyền thống".

Answer 3

Hãy thử so sánh việc hiểu danh sách với thuật toán tại chỗ khi bộ nhớ thực sự lớn. Đoạn mã dưới đây nhận được thời gian thực hiện gần khi sắp xếp các số nguyên 100K, nhưng có thể bạn sẽ bị kẹt trong giải pháp đọc danh sách khi phân loại các số nguyên 1M. Tôi đã thực hiện các bài kiểm tra bằng cách sử dụng một máy 4Gb. Toàn bộ mã: http://snipt.org/Aaaje2

class QSort: 
def __init__(self, lst): 
    self.lst = lst 

def sorted(self): 
    self.qsort_swap(0, len(self.lst)) 
    return self.lst 

def qsort_swap(self, begin, end): 
    if (end - begin) > 1: 
     pivot = self.lst[begin] 
     l = begin + 1 
     r = end 
     while l < r: 
      if self.lst[l] <= pivot: 
       l += 1 
      else: 
       r -= 1 
       self.lst[l], self.lst[r] = self.lst[r], self.lst[l] 

     l -= 1 
     self.lst[begin], self.lst[l] = self.lst[l], self.lst[begin]  
     # print begin, end, self.lst 
     self.qsort_swap(begin, l) 
     self.qsort_swap(r, end)