Dynamische Arrays in Python implementieren: vom Anfänger bis zum Experten

Teil 1 Lassen Sie uns über die Essenz der Python-Sequenztypen sprechen.

In diesem Blog sprechen wir über die verschiedenen „Sequenz“-Klassen von Python und die drei integrierten, häufig verwendeten Datenstrukturen (Liste und Tupel) sowie die Natur der String-Klasse (str).

Ich weiß nicht, ob Sie es bemerkt haben, aber diese Klassen haben offensichtlich eine Gemeinsamkeit. Sie können alle zum Speichern mehrerer Datenelemente verwendet werden. Die Hauptfunktion ist: Jede Klasse unterstützt den Indexzugriff auf die Elemente Verwenden Sie beispielsweise die Syntax Seq[i]​. Tatsächlich wird jede der oben genannten Klassen durch eine einfache Datenstruktur wie ein Array dargestellt.

Aber Leser, die mit Python vertraut sind, wissen möglicherweise, dass diese drei Datenstrukturen einige Unterschiede aufweisen: Beispielsweise können Tupel und Zeichenfolgen nicht geändert werden, Listen jedoch.

1. Array-Struktur im Computerspeicher

In der Computerarchitektur wissen wir, dass der Hauptspeicher eines Computers normalerweise aus Bitinformationen besteht, und diese Einheiten hängen von der genauen Systemarchitektur ab. Eine typische Einheit ist ein Byte, was 8 Bits entspricht.

Computersysteme verfügen über eine große Anzahl an Speicherbytes. Wie können wir also herausfinden, welches Byte unserer Informationen vorhanden ist? Die Antwort ist die Speicheradresse, die normalerweise jeder kennt. Basierend auf der Speicheradresse kann effektiv auf jedes Byte im Hauptspeicher zugegriffen werden. Tatsächlich ist jedem Speicherbyte eine eindeutige Binärzahl zugeordnet, die als Adresse dient. Wie in der Abbildung unten gezeigt, wird jedem Byte eine Speicheradresse zugewiesen:

Im Allgemeinen zeichnen Programmiersprachen die Beziehung zwischen einem Bezeichner und der Adresse auf, an der der zugehörige Wert gespeichert ist. Wenn wir beispielsweise erklären, dass der Bezeichner x einem bestimmten Wert im Speicher zugeordnet werden kann, kann der Bezeichner y einem anderen Wert zugeordnet werden. Eine Gruppe zusammengehöriger Variablen kann nacheinander in einem zusammenhängenden Bereich des Computerspeichers gespeichert werden. Wir nennen diesen Ansatz ein Array.

Schauen wir uns ein Beispiel in Python an. Eine Textzeichenfolge HELLO wird als Spalte geordneter Zeichen gespeichert. Es wird davon ausgegangen, dass jedes Unicode-Zeichen der Zeichenfolge zwei Bytes Speicherplatz benötigt. Die unterste Zahl ist der Indexwert der Zeichenfolge.

Wir können sehen, dass Arrays mehrere Werte speichern können, ohne dass mehrere Variablen mit spezifischen Indizes erstellt werden müssen, um jedes Element darin anzugeben. Dies wird in fast allen Programmiersprachen (wie C, Java, C#, C++) verwendet in Python, aber Python hat noch mehr Vorteile. Wenn Python eine Liste erstellt, wissen vertraute Leser möglicherweise, dass die Größe des Arrays oder der Liste nicht vordefiniert werden muss. Im Gegenteil, in Python ist die Liste dynamisch und wir können die gewünschten Datenelemente kontinuierlich hinzufügen die Liste. Schauen wir uns als Nächstes das Wissen über Python-Listen an (Leser, die bereits damit vertraut sind, können sie schnell durchsuchen oder überspringen).

2. Python-Liste: Funktionsweise der Python-Liste

(ele1, ele2, ele3, ele4, ...)

• Tupel sind speicherplatzeffizienter als Listen, da Tupel fest sind, sodass kein dynamisches Array mit verbleibendem Speicherplatz erstellt werden muss.

Wir erstellen zunächst eine Liste in der Python-IDE und werfen dann einen groben Blick auf die integrierten Operationen der Liste. Wir erstellen zunächst eine Liste mit dem Namen test_list und ändern (einfügen oder löschen) Elemente, kehren sie um oder löschen sie Liste wie folgt:

rrree

Wenn wir uns den obigen Code ansehen, können wir die zugehörigen Vorgänge der Liste sehen – Hinzufügen, Löschen, Ändern und Überprüfen. Es gibt auch einige integrierte Methoden werden hier nicht gezeigt und sind dem Leser überlassen, ihn selbst zu entdecken und zu erleben.

• Grundlagen hinter der Speicherzuweisung von Python-Listen

Schauen wir uns also diese Demonstration des zusätzlichen Speicherplatzes durch Codierungspraxis und die Beziehung zwischen der tatsächlichen Größe des im Speicher gehaltenen Arrays und der gegebenen Größe an.

Gehen Sie zum Üben zum Jupyter-Notizbuch. Oder verwenden Sie einen beliebigen Editor oder eine Entwicklungsumgebung Ihrer Wahl. Kopieren Sie den unten geschriebenen Code.

>>> test_list = []# 创建名为test_list的空列表
>>> test_list.append("Hello")
>>> test_list.append("World")
>>> test_list
['Hello', 'World']
>>> test_list = ["Hello", "Array", 2019, "easy learning", "DataStructure"]# 重新给test_list赋值
>>> len(test_list)# 求列表的长度
5
>>> test_list[2] = 1024# 修改列表元素
>>> test_list
['Hello', 'Array', 1024, 'easy learning', 'DataStructure']
>>>
>>> test_list.insert(1, "I love")# 向列表中指定位置中插入一个元素
>>> test_list
['Hello', 'I love', 'Array', 1024, 'easy learning', 'DataStructure']
>>> test_list.append(2020)# 向列表末尾增加一个元素
>>> test_list
['Hello', 'I love', 'Array', 1024, 'easy learning', 'DataStructure', 2020]
>>>
>>> test_list.pop(1)# 删除指定位置的元素
'I love'
>>> test_list.remove(2020)# 删除指定元素
>>> 
>>> test_list.index('Hello')# 查找某个元素的索引值
0
>>> test_list.index('hello')# 如果查找某个元素不在列表中，返回ValueError错误
Traceback (most recent call last):
File "<pyshell#11>", line 1, in <module>
test_list.index('hello')
ValueError: 'hello' is not in list
>>> 
>>> test_list.reverse()# 反转整个列表
>>> test_list
['DataStructure', 'easy learning', 2019, 'Array', 'Hello']
>>> test_list.clear()# 清空列表
>>> test_list
[]

Führen Sie den Code aus und Sie können die folgende Ausgabe sehen:

Wenn wir nun die Länge der Liste erhöhen, nehmen auch die Bytes zu. Lassen Sie es uns analysieren. Wenn das Element an Position Länge: 1

in der Liste gefüllt ist, springt die Anzahl der Bytes von 64 auf 96, was einer Steigerung von 32 Bytes entspricht. Da dieses Experiment auf einer 64-Bit-Maschine durchgeführt wurde, bedeutet dies, dass jede Speicheradresse 64 Bit (d. h. 8 Byte) umfasst. Die zusätzlichen 32 Byte entsprechen der Größe des Arrays, das zum Speichern von 4 Objektreferenzen vorgesehen ist. Beim Hinzufügen des 2., 3. oder 4. Elements ändert sich die Speichernutzung nicht. Die Anzahl der Bytes 96 kann Referenzen auf 4 Objekte bereitstellen.

96 = 64 + 8 mal 4

bei Länge: 10

时，字节数从一开始的64跳到192，能存下16个对象的引用，

192 = 64 + 8 times 16

一直到Length: 17

后又开始跳转，所以理论上264个字节数应该可以存下25个对象

264 = 64 + 8 times 25

但因为我们在代码中设置n=20，然后程序就终止了。

我们可以看到Python内置的list类足够智能，知道当需要额外的空间来分配数据时，它会为它们提供额外的大小，那么这究竟是如何被实现的呢？

好吧，答案是动态数组。说到这里，不知道大家学Python列表的时候是不是这样想的——列表很简单嘛，就是list()类、用中括号[]括起来，然后指导书籍或文档上的各类方法append、insert、pop...在各种IDE一顿操作过后，是的我觉得我学会了。

但其实背后的原理真的很不简单，比如我举个例子：A[-1]这个操作怎么实现？列表切片功能怎么实现？如何自己写pop()默认删除列表最右边的元素(popleft删除最左边简单)？...这些功能用起来爽，但真的自己实现太难了（我也还在学习中，大佬们请轻喷！）如果我们能学习并理解，肯定可以加强我们对数组这一结构的理解。

3、动态数组

什么是动态数组

动态数组是内存的连续区域，其大小随着插入新数据而动态增长。在静态数组中，我们需要在分配时指定大小。在定义数组的时候，其实计算机已经帮我们分配好了内存来存储，实际上我们不能扩展数组，因为它的大小是固定的。比如：我们分配一个大小为10的数组，则不能插入超过10个项目。

但是动态数组会在需要的时候自动调整其大小。这一点有点像我们使用的Python列表，可以存储任意数量的项目，而无需在分配时指定大小。

所以实现一个动态数组的实现的关键是——如何扩展数组？当列表list1的大小已满时，而此时有新的元素要添加进列表，我们会执行一下步骤来克服其大小限制的缺点：

1. 分配具有更大容量的新数组list2
2. 设置list2[i] = list1[i] (i=0,1,2,...，n-1)，其中n是该项目的当前编号
3. 设置list1 = list2，也就是说，list2正在作为新的数组来引用我们的新列表。
4. 然后，只要将新的元素插入（添加）到我们的列表list1即可。

接下来要思考的问题是，新数组应该多大？通常我们得做法是：新数组的大小是已满的旧数组的2倍。我们将在Python中编程实现动态数组的概念，并创建一个简单的代码，很多功能不及Python强大。

实现动态数组的Python代码

在Python中，我们利用ctypes的内置库来创建自己的动态数组类，因为ctypes模块提供对原始数组的支持，为了更快的对数组进行学习，所以对ctypes的知识可以查看官方文档进行学习。关于Python的公有方法与私有方法，我们在方法名称前使用双下划线**__**使其保持隐藏状态，代码如下：

# -*- coding: utf-8 -*-
# @Time: 2019-11-01 17:10
# @Author: yuzhou_1su
# @ContactMe : https://blog.csdn.net/yuzhou_1shu
# @File: DynamicArray.py
# @Software: PyCharm

import ctypes


class DynamicArray:
"""A dynamic array class akin to a simplified Python list."""

def __init__(self):
"""Create an empty array."""
self.n = 0 # count actual elements
self.capacity = 1# default array capacity
self.A = self._make_array(self.capacity)# low-level array

def is_empty(self):
""" Return True if array is empty"""
return self.n == 0

def __len__(self):
"""Return numbers of elements stored in the array."""
return self.n

def __getitem__(self, i):
"""Return element at index i."""
if not 0 <= i < self.n:
# Check it i index is in bounds of array
raise ValueError('invalid index')
return self.A[i]

def append(self, obj):
"""Add object to end of the array."""
if self.n == self.capacity:
# Double capacity if not enough room
self._resize(2 * self.capacity)
self.A[self.n] = obj# Set self.n index to obj
self.n += 1

def _resize(self, c):
"""Resize internal array to capacity c."""
B = self._make_array(c) # New bigger array
for k in range(self.n):# Reference all existing values
B[k] = self.A[k]
self.A = B# Call A the new bigger array
self.capacity = c # Reset the capacity

@staticmethod
def _make_array(c):
"""Return new array with capacity c."""
return (c * ctypes.py_object)()

def insert(self, k, value):
"""Insert value at position k."""
if self.n == self.capacity:
self._resize(2 * self.capacity)
for j in range(self.n, k, -1):
self.A[j] = self.A[j-1]
self.A[k] = value
self.n += 1

def pop(self, index=0):
"""Remove item at index (default first)."""
if index >= self.n or index < 0:
raise ValueError('invalid index')
for i in range(index, self.n-1):
self.A[i] = self.A[i+1]
self.A[self.n - 1] = None
self.n -= 1

def remove(self, value):
"""Remove the first occurrence of a value in the array."""
for k in range(self.n):
if self.A[k] == value:
for j in range(k, self.n - 1):
self.A[j] = self.A[j+1]
self.A[self.n - 1] = None
self.n -= 1
return
raise ValueError('value not found')

def _print(self):
"""Print the array."""
for i in range(self.n):
print(self.A[i], end=' ')
print()

测试动态数组Python代码

上面我们已经实现了一个动态数组的类，相信都很激动，接下来让我们来测试一下，看能不能成功呢？在同一个文件下，写的测试代码如下：

def main():
# Instantiate
mylist = DynamicArray()

# Append new element
mylist.append(10)
mylist.append(9)
mylist.append(8)
# Insert new element in given position
mylist.insert(1, 1024)
mylist.insert(2, 2019)
# Check length
print('The array length is: ', mylist.__len__())
# Print the array
print('Print the array：')
mylist._print()
# Index
print('The element at index 1 is :', mylist[1])
# Remove element
print('Remove 2019 in array:')
mylist.remove(2019)
mylist._print()
# Pop element in given position
print('Pop pos 2 in array:')
# mylist.pop()
mylist.pop(2)
mylist._print()


if __name__ == '__main__':
main()

测试结果

激动人心的时刻揭晓，测试结果如下。请结合测试代码和数组的结构进行理解，如果由疏漏，欢迎大家指出。

The array length is:5
Print the array：
10 1024 2019 9 8 
The element at index 1 is : 1024
Remove 2019 in array:
10 1024 9 8 
Pop pos 2 in array:
10 1024 8 

Part2总结

通过以上的介绍，我们知道了数组存在静态和动态类型。而在本博客中，我们着重介绍了什么是动态数组，并通过Python代码进行实现。希望你能从此以复杂的方式学会数组。总结发言，其实越是简单的操作，背后实现原理可能很复杂。

Das obige ist der detaillierte Inhalt vonDynamische Arrays in Python implementieren: vom Anfänger bis zum Experten. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!