Sự khác biệt lớn về thời gian giữa việc sắp xếp tập hợp so với sắp xếp danh sách trong Python

Question

Tôi đã tự hỏi liệu tôi có nên có cấu trúc dữ liệu của mình dưới dạng tập hợp hay danh sách hay không. Chủ yếu là tôi sẽ thiết lập các hoạt động, nhưng cuối cùng tôi sẽ cần phải sắp xếp nó.

Tôi tự hỏi liệu trước tiên tôi có nên đặt danh sách không, sau đó sử dụng sorted(list(my_set)) hoặc chỉ sắp xếp tập hợp ngay lập tức sorted(my_set). Có thể cho rằng, tôi có thể xem xét một giai đoạn "danh sách" chung, vì việc có một lệnh lặp lại vào thời điểm đó có thể có ý nghĩa.

Vì vậy, tôi đã quyết định thử nghiệm nó, hy vọng danh sách sẽ nhanh hơn.

Benchmarker:

import time 
def sorter(x): 
    t1 = time.time() 
    for i in range(1000000): 
     sorted(x) 
    return time.time() - t1 

dữ liệu:

one = range(1000) 
a1 = list(one) 
b1 = set(one) 
sorter(a1) 
# time: 16.5 s 
sorter(b1) 
# time: 20.7 s 

sau đó tôi nhận ra nó có thể có để làm với thực tế rằng các yếu tố đã được tại chỗ, và nhớ this amazing question & answer.

Sau đó, tôi đã cố gắng một số dữ liệu ngẫu nhiên:

two = numpy.random.randint(1, 1000, 1000) 
a2 = list(two) 
b2 = set(two) 

Với kết quả:

sorter(a2) 
# time: 4min 49s 
sorter(b2) 
# time: 18.9 s 

chênh lệch khổng lồ, những gì đang xảy ra?

Phần thưởng: Nó thậm chí xuất hiện tại thời điểm một phút, rằng sorted(set(a_list)) là ấn tượng nhanh hơn sorted(a_list).

Thực tế trong trường hợp thứ hai, có thể có các bản sao sẽ được lọc và do đó tăng tốc sắp xếp.

Answer 1

tôi mở rộng mã của bạn một chút và hy vọng rằng điều này sẽ cung cấp cho bạn cái nhìn sâu sắc vào những gì đang xảy ra:

import numpy 
import uuid 
import random 
import time 

def sorter(x): 
    t1 = time.time() 
    for i in range(10000): 
     sorted(x) 
    return time.time() - t1 

def pr(name, x): 
    print('sorter {:<12s} {:<11} (length {:>4})'.format(
     name, '{:.8}'.format(sorter(x)), len(x))) 

a2sizes = [] 
b2sizes = [] 

for x in range(1000): 
    two = numpy.random.randint(1, 1000, 1000) 
    a2 = list(two) 
    b2 = set(two) 
    a2sizes.append(len(a2)) 
    b2sizes.append(len(b2)) 

print 'average number of elements in a2', sum(a2sizes)/len(a2sizes) 
n = sum(b2sizes)/len(b2sizes) 
print 'average number of elements in b2', n 

này in ra:

average number of elements in a2 1000 
average number of elements in b2 632 

Điều này là do những va chạm trong ngẫu nhiên số phạm vi

print 
pr('a2', a2) 
# making a list of set gives you already sorted elements 
y = list(b2) 
pr('y', y) 
random.shuffle(y) 
pr('shuffled y ', y) 
pr('b2', b2) 

cho đầu ra:

sorter a2   2.492537 (length 1000) 
sorter b2   0.25028086 (length 633) 
sorter y   0.19689608 (length 633) 
sorter shuffled y 1.4935901 (length 633) 

Điều đó b2 sẽ nhanh hơn vì có ít yếu tố hợp lý hơn, nhưng điều này thậm chí còn nhanh hơn nếu trước tiên bạn tạo danh sách tập hợp phải có lý do nào đó. Rằng nó một lần nữa là chậm hơn nếu bạn shuffle danh sách đó là một lần nữa hợp lý và kết quả xáo trộn là khá gần với kết quả cho a2 khi bồi thường cho độ dài của danh sách.

Vì vậy, cho phép cố gắng đưa cái gì khác trong danh sách:

b3 = set() 
for x in range(1000): 
    b3.add(uuid.uuid4()) 

print '\nuuid elements', len(b3) 

a3 = list(b3) 
pr('a3', a3) 
random.shuffle(a3) 
pr('shuffled a3', a3) 
pr('b3', b3) 

cho (tôi đã có được khá ngạc nhiên khi chỉ còn lại ít hơn 1000 phần tử):

uuid elements 1000 
sorter a3   32.437758 (length 1000) 
sorter shuffled a3 32.178433 (length 1000) 
sorter b3   32.163802 (length 1000) 

Vì vậy, nó phải có một cái gì đó để thực hiện việc có số trong tập hợp:

previous = -1 
ordered = True 
for popped in b2: 
    if popped < previous: 
     print 'popped', popped, previous 
     ordered = False 
    previous = popped 

print '\nOrdered', ordered 

cung cấp cho bạn:

Ordered True 

Thay vì iterating, một set có chức năng pop() bạn có thể thử và sử dụng:

pop()

Remove và trả về một yếu tố tùy ý từ bộ này. Tăng KeyError nếu tập hợp rỗng.

Vì vậy, cho phép tùy tiện lấy yếu tố từ tập b2 và xem nếu có cái gì đó đặc biệt:

previous = -1 
ordered = True 
while(b2): 
    popped = b2.pop() 
    if popped < previous: 
     print 'popped', popped, previous 
     ordered = False 
    previous = popped 

print '\nOrdered', ordered 

cho kết quả tương tự:

Ordered True 

yếu tố Vì vậy, tùy tiện lấy của bộ số lượng truy xuất các số đó theo thứ tự, độc lập với cách đặt hàng các số này được đặt trong. Khi lặp lại là cách tạo danh sách truy xuất phần tử tại một thời điểm để thêm vào danh sách, kết quả của list(b2) là danh sách được sắp xếp và được sắp xếp khá nhanh bằng thuật toán Timsort được sử dụng trong Python.