chức năng trong và chỉ mục của danh sách [Python]

Question

Tôi đang cố gắng hiểu hoạt động bên trong của lệnh in và index() của cấu trúc dữ liệu danh sách.

Khi tôi nói:

if something not in some_list : 
    print "do something" 

Có đi qua toàn bộ danh sách trong nội bộ, tương tự như một vòng lặp for hay nó sử dụng, cách tiếp cận tốt hơn như hashtables, vv

Ngoài ra index() trong danh sách, cung cấp cho một lỗi nếu mục không có trong danh sách. Là hoạt động của cả hai in và index() giống nhau? Nếu index() là tốt hơn thì có thể bắt lỗi khi một mục không có mặt và nếu có thể, nó có phải là lập trình tốt không?

Answer 1

Câu hỏi hay! Có, cả hai phương pháp bạn đề cập sẽ lặp lại danh sách, nhất thiết. Python không sử dụng hashtables cho danh sách vì không có giới hạn nào cho các phần tử danh sách có thể băm.

Nếu bạn biết về "Big O" notation, cấu trúc dữ liệu list được thiết kế để truy cập O (1) bằng cách tìm kiếm chỉ mục đã biết, ví dụ: my_list[13]. Nó là O (n) để kiểm tra thành viên.

Có các cấu trúc dữ liệu khác được tối ưu hóa cho tốc độ O (1) để kiểm tra thành viên (ví dụ: __contains__), cụ thể là set và dict. Chúng được thực hiện với hashtables.

Dưới đây là một ví dụ về cách bạn có thể sử dụng IPython để xác minh time-complexity bộ và danh sách, để xác nhận những tuyên bố:

In [1]: short_list, long_list = range(1000), range(10000) 

In [2]: timeit 'potato' not in short_list 
10000 loops, best of 3: 40.9 µs per loop 

In [3]: timeit 'potato' not in long_list 
1000 loops, best of 3: 440 µs per loop 

In [4]: small_set, big_set = set(short_list), set(long_list) 

In [5]: timeit 'potato' not in small_set 
10000000 loops, best of 3: 72.9 ns per loop 

In [6]: timeit 'potato' not in big_set 
10000000 loops, best of 3: 84.5 ns per loop 

Answer 2

Đối với danh sách, cả hai phương pháp (in và index()) lặp qua danh sách để kiểm tra mục bạn đang tìm kiếm, thật không may. Họ sẽ ngừng lặp lại ngay sau khi kết quả kiểm tra thành viên được biết, có nghĩa là họ sẽ lặp lại đến cuối nếu mục đó không được tìm thấy. Theo như tôi biết, nếu bạn phải làm việc với danh sách, cấu trúc not in là Python nhất và là một trong những bạn nên đi với (nhưng bạn nên đổ những dấu ngoặc đơn không cần thiết).

Nếu bạn không cần sử dụng danh sách cụ thể, loại có sẵn trong kiểu set có thể hoạt động bình thường. Bộ này là một cấu trúc dữ liệu tương tự như danh sách, nhưng nó sử dụng một thuật toán băm để kiểm tra sự hiện diện của một mục, vì vậy nếu bạn đang làm rất nhiều loại công việc đó, bạn có thể cân nhắc việc chuyển đổi. Đọc các tài liệu tôi đã liên kết với mặc dù, bởi vì các bộ là không có thứ tự, do đó, chúng không hỗ trợ những thứ như cắt hoặc lập chỉ mục.

Có, bạn có thể lên kế hoạch cho những lần mục bạn đang kiểm tra không có trong cấu trúc dữ liệu của bạn. Bạn đang tìm kiếm một Try/Except Block:

example_list = [1,2,3] 

try: 
    index_of_4 = example_list.index(4) 
except ValueError: 
    print("Oops! 4 wasn't in the list!") 

Khi bạn biết trường hợp ngoại lệ có thể xảy ra trong chương trình của bạn, bạn có thể quấn mã vi phạm trong một khối như thế này để duyên dáng đón và phục hồi từ ngoại lệ. Nó thực sự là thực hành lập trình tốt để phục hồi từ các lỗi và ngoại lệ như một cách duyên dáng như bạn có thể, ngay cả khi điều đó có nghĩa là chỉ cần in một thông báo lỗi và thoát ra.