Tại sao tìm kiếm trong danh sách được sắp xếp trong python mất nhiều thời gian hơn?

Question

Tôi đã làm một thử nghiệm trong đó tôi đã cố gắng tìm thời gian cần để tìm kiếm một danh sách python. Tôi có một danh sách arr với số nguyên ngẫu nhiên. arr_s có cùng các yếu tố chỉ được sắp xếp.

arr = np.random.randint(low = 0, high = 1000, size = 500) 
arr_s = sorted(arr) 

Bây giờ tôi có thể tạo một mảng ngẫu nhiên của số nguyên find trong đó có yếu tố mà tôi muốn tìm kiếm trong arr và arr_s.

>>> %%timeit 
...:find = np.random.randint(0, 1000, 600) 
...:for i in find: 
...: if i in arr: 
...:  continue 

[OUT]:100 loops, best of 3: 2.18 ms per loop 


>>> %%timeit 
...:find = np.random.randint(0, 1000, 600) 
...:for i in find: 
...: if i in arr_s: 
...:  continue 

[OUT]:100 loops, best of 3: 5.15 ms per loop 

Bây giờ tôi hiểu rằng tôi đã không sử dụng bất kỳ phương pháp cụ thể để tìm kiếm trong mảng được sắp xếp (tìm kiếm ví dụ nhị phân). Vì vậy, nó có thể được thực hiện tìm kiếm tuyến tính tiêu chuẩn nhưng tại sao nó mất nhiều thời gian hơn để tìm kiếm trong mảng được sắp xếp trong mảng unsorted? Tôi nghĩ rằng nó sẽ mất gần như cùng một lúc. Tôi đã thử tất cả các loại mảng find. Các mảng có các số nguyên từ (0, 1000), (-1000, -100) và (-10000, 10000) các vòng lặp luôn mất nhiều thời gian hơn cho mảng được sắp xếp.

Answer 1

arr = np.random.randint(low = 0, high = 1000, size = 500) 
arr_s = sorted(arr) 

arr là một mảng. arr_s là một danh sách. Tìm kiếm một mảng có thể được xử lý một cách hiệu quả bằng cách numpy, nhưng việc tìm kiếm một danh sách yêu cầu con trỏ sau và thực hiện kiểm tra kiểu. Nó không có gì để làm với phân loại.

Lưu ý: in does weird things in numpy. Sử dụng in với ndarrays khó khăn có thể là một ý tưởng tồi.

Answer 2

Danh sách Python không giống như các mảng C. Chúng không chỉ là một khối bộ nhớ đơn giản, trong đó phần tử 1 luôn xuất hiện sau phần tử 0, v.v. Thay vào đó, dưới mui xe Python đang lưu trữ mọi thứ một cách linh hoạt để bạn có thể thêm và loại bỏ các phần tử của các loại tùy ý và di chuyển mọi thứ theo ý muốn.

Trong trường hợp này, tôi đoán là hành động phân loại danh sách sẽ thay đổi tổ chức cơ bản, làm cho nó kém hiệu quả hơn khi truy cập các phần tử.

Answer 3

Tôi không có câu trả lời chính xác nhưng điểm xuất phát có thể là kiểm tra tại các vòng lặp được sử dụng bởi từng đối tượng.

    In [9]: it = arr.__iter__() 
    In [10]: its = arr_s.__iter__() 
    In [11]: type(it) 
    Out[11]: iterator 
    In [12]: type(its) 
    Out[12]: listiterator 

Dường như họ sử dụng hai trình lặp khác nhau có thể giải thích sự khác biệt về tốc độ.