5. Viết chương trình Python để đếm số lượng chuỗi có độ dài chuỗi từ 2 trở lên và ký tự đầu tiên và ký tự cuối cùng giống nhau từ một danh sách các chuỗi đã cho
Xem giải pháp6. Viết chương trình Python để loại bỏ các bản sao khỏi danh sách
Xem giải pháp7. Viết chương trình Python để kiểm tra danh sách có rỗng hay không
Xem giải pháp8. Viết chương trình Python để sao chép hoặc sao chép danh sách
Xem giải pháp9. Viết chương trình Python để tìm danh sách các từ dài hơn n từ danh sách các từ đã cho
Xem giải pháp10. Viết chương trình lấy hai danh sách làm đầu vào và kiểm tra xem chúng có ít nhất một thành viên chung không
Xem giải pháp11. Viết chương trình Python để in một danh sách chỉ định sau khi loại bỏ các phần tử thứ 0, thứ 4 và thứ 5. [liệt kê]
Xem giải pháp12. Viết chương trình Python để in các số của một danh sách đã chỉ định sau khi xóa các số chẵn khỏi danh sách đó
Xem giải pháp13. Viết chương trình Python để xáo trộn và in một danh sách đã chỉ định [xáo trộn]
Xem giải pháp14. Viết chương trình Python để tạo và in danh sách 5 phần tử đầu tiên và cuối cùng trong đó các giá trị là bình phương của các số từ 1 đến 30
Trong Chương chúng tôi đã giới thiệu một số giới hạn hiệu suất Big-O đối với kiểu dữ liệu danh sách của Python. Tuy nhiên, chúng tôi chưa có kiến thức cần thiết để hiểu cách Python triển khai kiểu dữ liệu danh sách của nó. trong Chương bạn đã học cách triển khai danh sách được liên kết bằng cách sử dụng các nút và mẫu tham chiếu. Tuy nhiên, việc triển khai các nút và tham chiếu vẫn không phù hợp với hiệu suất của danh sách Python. Trong phần này, chúng ta sẽ xem xét các nguyên tắc đằng sau việc triển khai danh sách Python. Điều quan trọng là phải nhận ra rằng cách triển khai này sẽ không giống với cách triển khai của Python vì danh sách Python thực được triển khai bằng ngôn ngữ lập trình C. Ý tưởng trong phần này là sử dụng Python để thể hiện các ý tưởng chính, không thay thế việc triển khai C
Chìa khóa để triển khai danh sách của Python là sử dụng kiểu dữ liệu được gọi là mảng phổ biến đối với C, C++, Java và nhiều ngôn ngữ lập trình khác. Mảng rất đơn giản và chỉ có khả năng lưu trữ một loại dữ liệu. Ví dụ: bạn có thể có một mảng số nguyên hoặc một mảng số dấu chấm động, nhưng bạn không thể trộn cả hai trong một mảng. Mảng chỉ hỗ trợ hai thao tác. lập chỉ mục và gán cho một chỉ mục mảng
Cách tốt nhất để nghĩ về một mảng là nó là một khối byte liên tục trong bộ nhớ của máy tính. Khối này được chia thành các khối \[n\]-byte trong đó \[n\] dựa trên kiểu dữ liệu được lưu trữ trong mảng. Hình minh họa ý tưởng về một mảng có kích thước để chứa sáu giá trị dấu phẩy động
Một mảng các số dấu phẩy động
Trong Python, mỗi số dấu phẩy động sử dụng 16 byte bộ nhớ. Vì vậy, mảng trong Hình sử dụng tổng cộng 96 byte. Địa chỉ cơ sở là vị trí trong bộ nhớ mà mảng bắt đầu. Trước đây bạn đã thấy các địa chỉ trong Python cho các đối tượng khác nhau mà bạn đã xác định. Ví dụ.
class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
2 cho thấy rằng đối tượng class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
3 được lưu trữ tại địa chỉ bộ nhớ class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
4. Địa chỉ rất quan trọng vì một mảng cài đặt toán tử chỉ mục bằng phép tính rất đơn giảnitem_address = base_address + index * size_of_object
Ví dụ: giả sử rằng mảng của chúng ta bắt đầu tại vị trí
class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
5, là 64 ở dạng thập phân. Để tính vị trí của đối tượng ở vị trí thứ 4 trong mảng ta chỉ cần thực hiện phép tính số học. \[64 + 4 \cchấm 8 = 96\]. Rõ ràng kiểu tính toán này là \[O[1]\]. Tất nhiên điều này đi kèm với một số rủi ro. Đầu tiên, vì kích thước của một mảng là cố định, người ta không thể cứ thêm vô số thứ vào cuối mảng mà không gây ra một số hậu quả nghiêm trọng. Thứ hai, trong một số ngôn ngữ, như C, các giới hạn của mảng thậm chí không được kiểm tra, vì vậy mặc dù mảng của bạn chỉ có sáu phần tử trong đó, việc gán giá trị cho chỉ mục 7 sẽ không dẫn đến lỗi thời gian chạy. Như bạn có thể tưởng tượng, điều này có thể gây ra những vấn đề lớn khó theo dõi. Trong hệ điều hành Linux, việc truy cập một giá trị nằm ngoài ranh giới của một mảng thường sẽ tạo ra thông báo lỗi khá thiếu thông tin “vi phạm phân đoạn. ”Chiến lược chung mà Python sử dụng để triển khai danh sách được liên kết bằng cách sử dụng một mảng như sau
Python sử dụng một mảng chứa các tham chiếu [được gọi là con trỏ trong C] tới các đối tượng khác
Python sử dụng một chiến lược gọi là phân bổ quá mức để phân bổ một mảng có không gian cho nhiều đối tượng hơn mức cần thiết ban đầu
Khi mảng ban đầu cuối cùng được lấp đầy, một mảng mới, lớn hơn được phân bổ quá mức và nội dung của mảng cũ được sao chép sang mảng mới
Ý nghĩa của chiến lược này là khá tuyệt vời. Trước tiên hãy xem chúng là gì trước khi đi sâu vào triển khai hoặc chứng minh bất cứ điều gì
Truy cập một mục tại một vị trí cụ thể là \[O[1]\]
Trung bình thêm vào danh sách là \[O[1]\], nhưng \[O[n]\] trong trường hợp xấu nhất
Xuất hiện từ cuối danh sách là \[O[1]\]
Xóa một mục khỏi danh sách là \[O[n]\]
Chèn một mục vào một vị trí tùy ý là \[O[n]\]
Hãy xem chiến lược được nêu ở trên hoạt động như thế nào để triển khai rất đơn giản. Để bắt đầu, chúng tôi sẽ chỉ triển khai hàm tạo, phương thức
class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
6 và phương thức class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
7. Chúng ta sẽ gọi lớp này là class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
0. Trong hàm tạo, chúng ta sẽ cần khởi tạo hai biến thể hiện. Cái đầu tiên sẽ theo dõi kích thước của mảng hiện tại; . Biến thể hiện thứ hai sẽ theo dõi phần cuối hiện tại của danh sách; . Vì Python không có kiểu dữ liệu mảng nên chúng ta sẽ sử dụng list để mô phỏng mảng. Danh sách chứa mã cho ba phương pháp đầu tiên của class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
0. Lưu ý rằng phương thức khởi tạo khởi tạo hai biến thể hiện được mô tả ở trên và sau đó tạo một mảng không phần tử có tên là class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
4. Hàm tạo cũng tạo một biến thể hiện có tên là class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
5. Chúng ta sẽ hiểu biến này được sử dụng như thế nào ngay sau đâyclass ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
Tiếp theo, chúng ta sẽ cài đặt phương thức
class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
7. Điều đầu tiên mà class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
7 thực hiện là kiểm tra điều kiện trong đó class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
2 lớn hơn số vị trí chỉ mục có sẵn trong mảng [dòng ]. Nếu đây là trường hợp thì class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
6 được gọi là. Lưu ý rằng chúng tôi đang sử dụng quy ước gạch dưới kép để đặt phương thức def __getitem__[self, idx]:
if idx < self.last_index:
return self.my_array[idx]
raise LookupError["index out of bounds"]
def __setitem__[self, idx, val]:
if idx < self.last_index:
self.my_array[idx] = val
raise LookupError["index out of bounds"]
0 ở chế độ riêng tư. Khi mảng được thay đổi kích thước, giá trị mới được thêm vào danh sách tại class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
2 và class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
2 được tăng thêm mộtPhương thức
def __getitem__[self, idx]:
if idx < self.last_index:
return self.my_array[idx]
raise LookupError["index out of bounds"]
def __setitem__[self, idx, val]:
if idx < self.last_index:
self.my_array[idx] = val
raise LookupError["index out of bounds"]
0 tính toán kích thước mới cho mảng bằng cách sử dụng \[2 ^ {size\_exponent}\]. Có nhiều phương pháp có thể được sử dụng để thay đổi kích thước mảng. Một số triển khai nhân đôi kích thước của mảng mỗi lần như chúng ta làm ở đây, một số sử dụng hệ số nhân là 1. 5, và một số sử dụng lũy thừa của hai. Python sử dụng hệ số nhân là 1. 125 cộng với một hằng số. Các nhà phát triển Python đã thiết kế chiến lược này như một sự cân bằng tốt cho các máy tính có tốc độ CPU và bộ nhớ khác nhau. Chiến lược Python dẫn đến một chuỗi các kích thước mảng \[0, 4, 8, 16, 24, 32, 40, 52, 64, 76\ldots\]. Nhân đôi kích thước mảng dẫn đến lãng phí không gian nhiều hơn một chút tại bất kỳ thời điểm nào, nhưng dễ phân tích hơn nhiều. Khi một mảng mới đã được phân bổ, các giá trị từ danh sách cũ phải được sao chép vào mảng mới; . Cuối cùng, các giá trị class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
1 và class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
2 phải được cập nhật, class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
5 phải được tăng lên và def __getitem__[self, idx]:
if idx < self.last_index:
return self.my_array[idx]
raise LookupError["index out of bounds"]
def __setitem__[self, idx, val]:
if idx < self.last_index:
self.my_array[idx] = val
raise LookupError["index out of bounds"]
7 được lưu dưới dạng def __getitem__[self, idx]:
if idx < self.last_index:
return self.my_array[idx]
raise LookupError["index out of bounds"]
def __setitem__[self, idx, val]:
if idx < self.last_index:
self.my_array[idx] = val
raise LookupError["index out of bounds"]
8. Trong một ngôn ngữ như C, khối bộ nhớ cũ được tham chiếu bởi def __getitem__[self, idx]:
if idx < self.last_index:
return self.my_array[idx]
raise LookupError["index out of bounds"]
def __setitem__[self, idx, val]:
if idx < self.last_index:
self.my_array[idx] = val
raise LookupError["index out of bounds"]
8 sẽ được trả về hệ thống một cách rõ ràng để sử dụng lại. Tuy nhiên, hãy nhớ lại rằng trong Python các đối tượng không còn được tham chiếu sẽ tự động được dọn sạch bởi thuật toán thu gom rácTrước khi tiếp tục, hãy phân tích lý do tại sao chiến lược này mang lại cho chúng ta hiệu suất \[O[1]\] trung bình cho
class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
7. Điều quan trọng là lưu ý rằng hầu hết thời gian chi phí để thêm một mục \[c_i\] là 1. Lần duy nhất mà hoạt động tốn kém hơn là khi class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
2 là lũy thừa của 2. Khi class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
2 là lũy thừa của 2 thì chi phí để nối thêm một mục là \[O[last\_index]\]. Chúng ta có thể tóm tắt chi phí để chèn mục \[i_{th}\] như sau\[\begin{split}c_i = \begin{cases} i \text{ if } i \text{ là lũy thừa của 2} \\ 1 \text{ nếu không thì} \end{cases}\end{split}\]
Vì chi phí đắt đỏ để sao chép các mục
class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
2 xảy ra tương đối ít nên chúng tôi phân bổ chi phí hoặc phân bổ dần, chi phí chèn vào tất cả các mục phụ lục. Khi chúng tôi làm điều này, chi phí của bất kỳ lần chèn nào trung bình là \[O[1]\]. Ví dụ: hãy xem xét trường hợp bạn đã thêm bốn mục. Mỗi trong số bốn phần bổ sung này chỉ tốn một thao tác để lưu trữ trong mảng đã được phân bổ để chứa bốn phần tử. Khi mục thứ năm được thêm vào, một mảng mới có kích thước 8 được phân bổ và bốn mục cũ được sao chép. Nhưng bây giờ bạn có chỗ trong mảng cho bốn phần bổ sung chi phí thấp. Về mặt toán học, chúng ta có thể chỉ ra điều này như sau\[\begin{split}\begin{aligned} cost_{total} &= n + \sum_{j=0}^{\log_2{n}}{2^j} \\ &= n + 2n \\ &
Tổng kết trong phương trình trước có thể không rõ ràng đối với bạn, vì vậy hãy nghĩ về điều đó nhiều hơn một chút. Tổng đi từ 0 đến \[\log_2{n}\]. Giới hạn trên của tổng cho chúng ta biết chúng ta cần nhân đôi kích thước của mảng bao nhiêu lần. Thuật ngữ \[2^j\] chiếm các bản sao mà chúng ta cần thực hiện khi mảng được nhân đôi. Vì tổng chi phí để thêm n mặt hàng là \[3n\], chi phí cho một mặt hàng là \[3n/n = 3\]. Bởi vì chi phí là một hằng số, chúng tôi nói rằng nó là \[O[1]\]. Loại phân tích này được gọi là phân tích khấu hao và rất hữu ích trong việc phân tích các thuật toán nâng cao hơn
Tiếp theo, chúng ta hãy chuyển sang các toán tử chỉ mục. Danh sách hiển thị cách triển khai Python của chúng tôi để lập chỉ mục và gán cho một vị trí mảng. Nhớ lại rằng chúng ta đã thảo luận ở trên rằng phép tính cần thiết để tìm vị trí bộ nhớ của mục \[i_{th}\] trong một mảng là một biểu thức số học \[O[1]\] đơn giản. Ngay cả các ngôn ngữ như C cũng ẩn phép tính đó đằng sau một toán tử chỉ mục mảng đẹp, vì vậy trong trường hợp này, C và Python trông rất giống nhau. Trên thực tế, trong Python rất khó lấy vị trí bộ nhớ thực của một đối tượng để sử dụng trong phép tính như thế này, vì vậy chúng tôi sẽ chỉ dựa vào toán tử chỉ mục tích hợp sẵn của danh sách. Để xác nhận điều này, bạn luôn có thể lấy mã nguồn Python và xem tệp
class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
24def __getitem__[self, idx]:
if idx < self.last_index:
return self.my_array[idx]
raise LookupError["index out of bounds"]
def __setitem__[self, idx, val]:
if idx < self.last_index:
self.my_array[idx] = val
raise LookupError["index out of bounds"]
Cuối cùng, chúng ta hãy xem xét một trong những thao tác danh sách đắt tiền hơn, chèn. Khi chúng tôi chèn một mục vào một
class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
0, trước tiên chúng tôi sẽ cần dịch chuyển mọi thứ trong danh sách tại điểm chèn và xa hơn về phía trước một vị trí chỉ mục để nhường chỗ cho mục chúng tôi đang chèn. Quá trình này được minh họa trong HìnhChèn 27. 1 tại Chỉ mục 2 trong ArrayList
Chìa khóa để triển khai đúng
class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
26 là nhận ra rằng khi bạn đang thay đổi các giá trị trong mảng, bạn không muốn ghi đè lên bất kỳ dữ liệu quan trọng nào. Cách để làm điều này là làm việc từ cuối danh sách trở lại điểm chèn, sao chép dữ liệu về phía trước. Việc triển khai class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
26 của chúng tôi được hiển thị trong Danh sách. Lưu ý cách thiết lập class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
28 trên dòng để đảm bảo rằng chúng tôi đang sao chép dữ liệu hiện có vào phần không sử dụng của mảng trước, sau đó các giá trị tiếp theo được sao chép trên các giá trị cũ đã được thay đổi. Nếu vòng lặp bắt đầu tại điểm chèn và sao chép giá trị đó sang vị trí chỉ mục lớn hơn tiếp theo trong mảng, thì giá trị cũ sẽ bị mất vĩnh viễnclass ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
2Hiệu suất của phần chèn là \[O[n]\] vì trong trường hợp xấu nhất, chúng tôi muốn chèn thứ gì đó vào chỉ mục 0 và chúng tôi phải dịch chuyển toàn bộ mảng về phía trước một. Trung bình chúng ta sẽ chỉ cần dịch chuyển một nửa mảng, nhưng đây vẫn là \[O[n]\]. Bạn có thể muốn quay lại Chương và tự nhắc mình cách thực hiện tất cả các thao tác danh sách này bằng cách sử dụng các nút và tham chiếu. Việc thực hiện không phải là đúng hay sai; . Cụ thể, bạn có ý định thêm các mục vào đầu danh sách thường xuyên nhất hay ứng dụng của bạn có thêm các mục vào cuối danh sách không?
Có một số hoạt động thú vị khác mà chúng tôi chưa triển khai cho
class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
0 của mình, bao gồm. class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
20, class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
21, class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
22 và làm cho class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
0 có thể lặp lại. Chúng tôi để lại những cải tiến này cho class ArrayList:
def __init__[self]:
self.size_exponent = 0
self.max_size = 0
self.last_index = 0
self.my_array = []
def append[self, val]:
if self.last_index > self.max_size - 1: |\label{line:lst_arr_size}|
self.__resize[]
self.my_array[self.last_index] = val
self.last_index += 1
def __resize[self]:
new_size = 2 ** self.size_exponent
print["new_size = ", new_size]
new_array = [0] * new_size
for i in range[self.max_size]: |\label{line:lst_arr_cop1}|
new_array[i] = self.my_array[i]
self.max_size = new_size
self.my_array = new_array
self.size_exponent += 1
0 như một bài tập dành cho bạn
List[] hoạt động như thế nào trong Python?
Danh sách chữ được viết trong dấu ngoặc vuông [ ]. Danh sách hoạt động tương tự như chuỗi -- sử dụng hàm len[] và dấu ngoặc vuông [ ] để truy cập dữ liệu, với phần tử đầu tiên ở chỉ mục 0 . [Xem con trăn chính thức. tài liệu danh sách tổ chức. ] Bài tập có dấu = trong danh sách không tạo bản sao.
danh sách [. ] có nghĩa là gì trong Python?
Danh sách là một vùng chứa Python có thứ tự và có thể thay đổi , là một trong những cấu trúc dữ liệu phổ biến nhất trong Python. Để tạo danh sách, các phần tử được đặt trong dấu ngoặc vuông [[]], phân tách bằng dấu phẩy. Như được hiển thị ở trên, danh sách có thể chứa các phần tử thuộc các loại khác nhau cũng như các phần tử trùng lặp.
Bạn có thể sử dụng == cho các danh sách trong Python không?
Phương thức Python set[] và toán tử == để so sánh hai danh sách
. the == operator is used for comparison of the data items of the list in an element-wise fashion.
Cú pháp của danh sách trong Python là gì?
Danh sách. Danh sách được dùng để lưu trữ nhiều mục trong một biến duy nhất . Danh sách là một trong 4 loại dữ liệu tích hợp trong Python được sử dụng để lưu trữ các bộ sưu tập dữ liệu, 3 loại còn lại là Tuple, Set và Dictionary, tất cả đều có chất lượng và cách sử dụng khác nhau.