การ Implement Dynamic Array ใน Python

Dynamic Array (อาร์เรย์ไดนามิก)

ใน Python ลิสต์ เซต และดิกชันนารีเป็น mutable objects ในขณะที่ตัวเลข สตริง และทูเพิลเป็น immutable objects Mutable objects หมายถึงเราสามารถเพิ่ม/ลบรายการจากลิสต์ เซต หรือดิกชันนารีได้ อย่างไรก็ตาม นั้นไม่ใช่ในกรณีของ immutable objects เช่น tuple หรือ strings

ใน Python ลิสต์คือ dynamic array มาลองสร้าง dynamic list กัน −

>>> # สร้างลิสต์ว่าง ชื่อ list1 >>> list1 = [] >>> type (list1) 

เพิ่มรายการบนลิสต์ว่างของเรา list1 −

>>> # เพิ่มรายการ >>> list1 =[2, 4, 6] >>> list1 [2, 4, 6] >>> # อีกวิธีหนึ่งในการเพิ่มรายการ ใช้ append >>> list1.append('Tutorialspoint') >>> list1 [2, 4, 6, 'Tutorialspoint']

ลบรายการบางรายการจากลิสต์ −

>>> # ลบรายการจากลิสต์ >>> list1.pop() 'Tutorialspoint' >>> list1 [2, 4, 6]

จากข้างต้นเราเห็นได้ว่าลิสต์จริงๆ แล้วเป็นการขยายของอาร์เรย์ ที่เราสามารถแก้ไขขนาด (เพิ่มหรือลด) ของลิสต์ได้ เราเริ่มต้นด้วยลิสต์ขนาด "ศูนย์" และเพิ่ม "สี่" รายการเข้าไป

พื้นฐานของการ implement Dynamic Array

พิจารณาตัวอย่างที่ลิสต์ .i.e. list1 ถูก append เมื่อขนาดของอาร์เรย์เต็มแล้ว เราต้องทำขั้นตอนด้านล่างเพื่อเอาชนะข้อบกพร่องด้านขนาด นี่คือพื้นฐานหลังการ implement dynamic array −

• จัดสรรอาร์เรย์ใหม่ list2 ด้วยความจุที่ใหญ่กว่า
• ตั้งค่า list2[i] = list1[i], สำหรับ i = 0,1...n-1, โดยที่ n คือจำนวนรายการปัจจุบัน
• ตั้งค่า list1=list2, เนื่องจากตอนนี้ list2 อ้างอิงถึงลิสต์ใหม่ของเรา
• และจากนั้น แค่ insert (append) รายการใหม่ไปที่ลิสต์ของเรา (list1)

มาสร้างโค้ดง่ายๆ วิธี implement แนวคิด dynamic array ใน Python programming เราจะสร้าง dynamic array class ของเราเองโดยใช้ built-in library class ใน Python ที่ชื่อ ctypes ซึ่งจะถูกใช้เป็น raw array จากโมดูล ctypes

dynamicArray.py

import ctypes class DynamicArray(object):     # Initialize it     def __init__(self):         # เราจะมีสาม attributes         self.n = 0 # by default         self.capacity = 1 # by default         self.A = self.make_array(self.capacity) # make_array จะถูกกำหนดภายหลัง     # Length method     def __len__(self):         # จะคืนจำนวน elements ในอาร์เรย์         return self.n     def __getitem__(self, k):         # จะคืน element ที่ index k         if not 0 <=k 
เมื่อ dynamic class ของเราพร้อมใช้งานแล้ว ลองทำบางอย่างกับมัน −
>>> len(arr) 0 >>> arr.append(1) >>> # รายการแรกถูกเพิ่ม >>> len(arr) 1 >>> arr.append('Tutorialspoint') >>> # รายการที่สองถูกเพิ่ม >>> len(arr) 2 >>> arr[1] 'Tutorialspoint'
เสร็จแล้ว เราสร้าง dynamic array ของเราเองแล้ว และเราสามารถปรับขนาดอาร์เรย์ซึ่งเป็นลิสต์ใน Python ได้