Tại sao xử lý một danh sách ngẫu nhiên nhanh hơn nhiều so với việc xử lý một danh sách có thứ tự?

Question

Tôi đã cố gắng để cải thiện hiệu suất của func chức năng và tôi thấy rằng một sự thay đổi đơn giản trong cách danh sách aX được tạo cải thiện hiệu suất khá một chút:

import timeit 
import numpy as np 

def func(a, b): 
    return [_ for _ in a if _ not in b] 

Na, Nb = 10000, 5000 
b = list(np.random.randint(1000, size=Nb)) 

# Ordered list of Na integers 
a1 = [_ for _ in range(Na)] 
# Random list of Na integers 
a2 = list(np.random.randint(Na, size=Na)) 
# Ordered list of Na integers generated with numpy 
a3 = list(np.arange(Na)) 

start_time = timeit.default_timer() 
ab1 = func(a1, b) 
abt1 = timeit.default_timer() - start_time 
print("Time ab1", abt1) 

start_time = timeit.default_timer() 
ab2 = func(a2, b) 
abt2 = timeit.default_timer() - start_time 
print("Time ab2", abt2) 

start_time = timeit.default_timer() 
ab3 = func(a3, b) 
abt3 = timeit.default_timer() - start_time 
print("Time ab3", abt3) 

print("Ratio 1/2:", abt1/abt2) 
print("Ratio 1/3:", abt1/abt3) 

Trong Python 2.7.13 này dẫn đến:

('Time ab1', 5.296088933944702) 
('Time ab2', 1.5520200729370117) 
('Time ab3', 1.5581469535827637) 
('Ratio 1/2:', 3.412384302428827) 
('Ratio 1/3:', 3.3989662667998095) 

Trong Python 3.5.2 sự khác biệt thậm chí còn lớn hơn:

Time ab1 6.758207322000089 
Time ab2 1.5693355060011527 
Time ab3 1.5148192759988888 
Ratio 1/2: 4.306413317073784 
Ratio 1/3: 4.461395117608107 

Tôi cần phải xử lý một số nguyên danh sách đặt hàng (tức là: a1 hoặc a3), vì vậy câu hỏi của tôi là:

Tại sao danh sách ngẫu nhiên để xử lý nhanh hơn nhiều so với danh sách đã ra lệnh không tạo ra với numpy?

Answer 1

bạn b, a2, và a3 danh sách là danh sách các vô hướng NumPy, trong khi danh sách a1 của bạn là một danh sách các ints Python thường. So sánh các scalar NumPy với các scalars Python thông thường yêu cầu lot kiểm tra và ép buộc loại bổ sung, do đó, kiểm tra func(a1, b), cần so sánh số vô hướng NumPy với các scalars Python thông thường, hoạt động chậm nhất.

Nếu bạn đặt b một danh sách ints Python (bằng cách gọi tolist method thay vì chức năng list), chênh lệch thời gian được đảo ngược.

Bạn có thể cân nhắc sử dụng Python set s hoặc NumPy's set-like operations để thực hiện tác vụ của bạn.

Answer 2

Như được thảo luận here mảng có nhiều mảng nhanh hơn nhiều so với danh sách python. Đây là lý do tại sao các mảng numpy có vẻ nhanh hơn khi bạn vẫn đang sử dụng một mảng numpy khi bạn gọi hàm list().

Sử dụng NumPy .tolist() chức năng chuyển đổi một mảng NumPy để Python thường xuyên đối tượng tất cả các con đường xuống (như user2357112 chỉ ra) và sự khác biệt hiệu suất biến mất, xem:

import timeit 
import numpy as np 

def func(a, b): 
    return [_ for _ in a if _ not in b] 

Na, Nb = 10000, 5000 
b = list(np.random.randint(Na, size=Nb)) # len: 5000, max: 9999 

# Ordered list of Na integers 
a1 = [_ for _ in range(Na)] # len: 10000, max: 9999 
# Random list of Na integers 
a2 = np.random.randint(Na, size=Na).tolist() # len: 10000, max: 9999 
# Ordered list of Na integers generated with numpy 
a3 = np.arange(Na).tolist() 

start_time = timeit.default_timer() 
ab1 = func(a1, b) 
abt1 = timeit.default_timer() - start_time 
print("Time ab1", abt1) 

start_time = timeit.default_timer() 
ab2 = func(a2, b) 
abt2 = timeit.default_timer() - start_time 
print("Time ab2", abt2) 

start_time = timeit.default_timer() 
ab3 = func(a3, b) 
abt3 = timeit.default_timer() - start_time 
print("Time ab3", abt3) 

print("Ratio 1/2:", abt1/abt2) 
print("Ratio 1/3:", abt1/abt3) 

#Time ab1 4.622085004015502 
#Time ab2 4.598610720638726 
#Time ab3 4.63976530848255 
#Ratio 1/2: 1.005104646773301 
#Ratio 1/3: 0.9961893968139456 

Hy vọng rằng đây trả lời câu hỏi đầu tiên của bạn!