Độ phức tạp thời gian chạy của hàm len[] trong danh sách Python của bạn là O[1]. Phải mất thời gian chạy liên tục cho dù có bao nhiêu phần tử trong danh sách. Tại sao? . Tra cứu giá trị của bộ đếm này mất thời gian liên tục
Các đối tượng danh sách Python theo dõi độ dài của chính chúng. Khi bạn gọi hàm len[...] trên một đối tượng danh sách, đây là điều sẽ xảy ra [đại khái]
- Máy ảo Python tra cứu hàm
len[...]trong từ điển để tìm triển khai liên quan - Bạn chuyển một đối tượng danh sách làm đối số cho hàm
len[]để máy ảo Python kiểm tra phương thức__len__của đối tượng danh sách - Phương thức này được triển khai trong C++ và nó chỉ là một bộ đếm tăng lên mỗi khi bạn thêm một phần tử vào danh sách và giảm đi nếu bạn xóa một phần tử khỏi danh sách. Ví dụ: biến
lengthlưu trữ độ dài hiện tại của danh sách. Phương thức sau đó trả về giá trịself.length - Xong
Đây là một đoạn triển khai C++ của cấu trúc dữ liệu danh sách
static int
list_resize[PyListObject *self, Py_ssize_t newsize]
{
PyObject **items;
size_t new_allocated, num_allocated_bytes;
Py_ssize_t allocated = self->allocated;
// some implementation details
Py_SET_SIZE[self, newsize];
self->allocated = new_allocated;
return 0;
}Độ phức tạp thời gian chạy của các phương thức danh sách Python khác là gì?
Đây là bảng dựa trên wiki Python chính thức
OperationAverage CaseAmortized Worst Casecopy[]O[n]O[n]append[]O[1]O[1]pop[]O[1]O[1]pop[i]O[k]O[k]insert[ . j]O[k]O[k]del list[i. j]O[n]O[n]danh sách[i. j] = yO[k+n]O[k+n]extend[]O[k]O[k]sort[]O[n log n]O[n log n][…] * 10O[nk]ODanh sách Python được triển khai bằng mảng C++. Điều này có nghĩa là việc sửa đổi các phần tử ở đầu mỗi danh sách thường chậm bởi vì tất cả các phần tử phải được dịch chuyển sang bên phải. Nếu bạn thêm một phần tử vào cuối danh sách, nó thường nhanh. Tuy nhiên, việc thay đổi kích thước một mảng đôi khi có thể trở nên chậm nếu phải phân bổ nhiều bộ nhớ hơn cho mảng đó
Những bài viết liên quan
- Hướng dẫn cơ bản về danh sách Python
Đi đâu từ đây
Nếu bạn tiếp tục vật lộn với những lệnh Python cơ bản đó và bạn cảm thấy bế tắc trong quá trình học tập của mình, thì tôi có thứ này cho bạn. Python One-Liners [Liên kết Amazon]
Trong cuốn sách này, tôi sẽ cung cấp cho bạn tổng quan kỹ lưỡng về các chủ đề khoa học máy tính quan trọng như học máy, biểu thức chính quy, khoa học dữ liệu, NumPy và kiến thức cơ bản về Python—tất cả trong một dòng mã Python
Lấy sách từ Amazon
MÔ TẢ SÁCH CHÍNH THỨC. Python One-Liners sẽ chỉ cho người đọc cách thực hiện các tác vụ hữu ích với một dòng mã Python. Sau phần giới thiệu ngắn gọn về Python, cuốn sách bao gồm các chủ đề nâng cao cần thiết như cắt, hiểu danh sách, phát sóng, hàm lambda, thuật toán, biểu thức chính quy, mạng thần kinh, hồi quy logistic, v.v. Mỗi phần trong số 50 phần của cuốn sách giới thiệu một vấn đề cần giải quyết, hướng dẫn người đọc các kỹ năng cần thiết để giải quyết vấn đề đó, sau đó cung cấp một giải pháp Python ngắn gọn với lời giải thích chi tiết
Chris
Trong khi làm việc với tư cách là một nhà nghiên cứu trong các hệ thống phân tán, Dr. Christian Mayer tìm thấy tình yêu của mình với việc dạy sinh viên khoa học máy tính
Để giúp sinh viên đạt được mức độ thành công Python cao hơn, anh ấy đã thành lập trang web giáo dục lập trình Finxter. com. Ông là tác giả của cuốn sách lập trình nổi tiếng Python One-Liners [NoStarch 2020], đồng tác giả của loạt sách tự xuất bản Coffee Break Python, người đam mê khoa học máy tính, cộng tác viên tự do và chủ sở hữu của một trong 10 blog Python lớn nhất thế giới
Niềm đam mê của anh ấy là viết, đọc và mã hóa. Nhưng niềm đam mê lớn nhất của anh ấy là phục vụ các lập trình viên đầy tham vọng thông qua Finxter và giúp họ nâng cao kỹ năng của mình. Bạn có thể tham gia học viện email miễn phí của anh ấy tại đây
Hàm len[] trong Python có một đặc điểm rất đặc biệt mà người ta thường thắc mắc. Hoàn toàn không mất thời gian và thời gian bằng nhau để tính toán độ dài của các cấu trúc dữ liệu có thể lặp lại [chuỗi, mảng, bộ, v.v. ], bất kể kích thước hoặc loại dữ liệu. Điều này rõ ràng ám chỉ độ phức tạp thời gian của
41. Nhưng bạn đã tự hỏi làm thế nào?
Python tuân theo ý tưởng rằng việc giữ độ dài làm thuộc tính sẽ rẻ và dễ bảo trì. len[] thực chất là một hàm gọi phương thức '__len__[]'. Phương thức này được định nghĩa trong các lớp được xác định trước của cấu trúc dữ liệu có thể lặp lại. Phương thức này thực sự hoạt động như một bộ đếm, được tự động tăng lên khi dữ liệu được xác định và lưu trữ. Vì vậy, khi bạn gọi hàm len[], bạn không đưa cho trình thông dịch lệnh tìm độ dài bằng cách duyệt, mà bạn yêu cầu trình thông dịch in một giá trị đã được lưu trữ. Do đó, hàm len[] trong Python chạy ở độ phức tạp
41
Do đó, nó cũng có thể được định nghĩa là
46
47
48
len[]0len[]1
len[]0len[]3
len[]0len[]5 len[]6
len[]7
len[]8
len[]9
410
411_______112
413
414
413
416
413
418
419
len[]0len[]1
đầu ra
4
Ghi chú. Điều này có vẻ rất có lợi, nhưng hãy nhớ rằng nó đặt ra một gánh nặng đáng kể cho trình thông dịch trong giai đoạn định nghĩa dữ liệu. Đây là một trong nhiều lý do khiến Python chậm hơn trong quá trình lập trình cạnh tranh, đặc biệt là với đầu vào lớn