Implémentation de tableaux dynamiques en Python : du débutant au compétent

Partie 1 Parlons de l'essence des types de séquence Python

Dans ce blog, parlons des différentes classes « séquence » de Python et des trois structures de données intégrées couramment utilisées (liste et tuple) et de la nature de la classe de chaîne. (str).

Je ne sais pas si vous l'avez remarqué, mais ces classes ont un point commun évident. Elles peuvent toutes être utilisées pour enregistrer plusieurs éléments de données. La fonction principale est la suivante : chaque classe prend en charge l'accès en indice (index) aux éléments du. séquence. Par exemple, utilisez la syntaxe Seq[i]​. En fait, chacune des classes ci-dessus est représentée par une structure de données simple telle qu'un tableau.

Mais les lecteurs familiers avec Python savent peut-être que ces trois structures de données présentent quelques différences : par exemple, les tuples et les chaînes ne peuvent pas être modifiés, mais les listes peuvent être modifiées.

1. Structure de tableau dans la mémoire de l'ordinateur

Dans l'architecture informatique, nous savons que la mémoire principale de l'ordinateur est composée d'informations binaires. Ces bits sont généralement classés en unités plus grandes, et ces unités dépendent de l'architecture précise du système. Une unité typique est un octet, ce qui équivaut à 8 bits.

Les systèmes informatiques disposent d'un grand nombre d'octets de stockage, alors comment pouvons-nous trouver quel octet de nos informations existe ? La réponse est l’adresse de stockage que tout le monde connaît habituellement. En fonction de l'adresse de stockage, n'importe quel octet de la mémoire principale est effectivement accessible. En fait, chaque octet de stockage est associé à un nombre binaire unique qui lui sert d'adresse. Comme le montre la figure ci-dessous, chaque octet se voit attribuer une adresse de stockage :

De manière générale, les langages de programmation enregistrent la relation entre un identifiant et l'adresse où est stockée sa valeur associée. Par exemple, lorsque nous déclarons que l'identifiant x peut être associé à une certaine valeur en mémoire, l'identifiant y peut être associé à une autre valeur. Un groupe de variables associées peut être stocké les unes après les autres dans une zone contiguë de la mémoire informatique. Nous appelons cette approche un tableau.

Regardons un exemple en Python. Une chaîne de texte HELLO est stockée sous forme de colonne de caractères ordonnés. On suppose que chaque caractère Unicode de la chaîne nécessite deux octets d'espace de stockage. Le nombre du bas est la valeur d'index de la chaîne.

Nous pouvons voir que les tableaux peuvent stocker plusieurs valeurs sans construire plusieurs variables avec des index spécifiques pour spécifier chaque élément qu'ils contiennent, et dans presque tous les langages de programmation (tels que C, Java, C#, C++) utilisés en Python, mais Python a plus d'avantages. Lorsque Python crée une liste, les lecteurs familiers savent peut-être qu'il n'est pas nécessaire de prédéfinir la taille du tableau ou de la liste. Au contraire, en Python, la liste a une nature dynamique et nous pouvons continuellement ajouter les éléments de données que nous souhaitons. la liste. Examinons ensuite la connaissance des listes Python (les lecteurs qui les connaissent déjà peuvent les parcourir ou les ignorer rapidement).

2. Liste Python

Fonctionnement de la liste Python

• Le format de syntaxe pour créer une liste :

[ele1, ele2, ele3, ele4, ...]

• Le format de syntaxe pour créer un tuple :

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

Les tuples sont plus efficaces en termes d'espace mémoire que les listes car les tuples sont fixes, il n'est donc pas nécessaire de créer un tableau dynamique avec l'espace restant.

Nous créons d'abord une liste dans l'IDE Python, puis examinons brièvement les opérations intégrées de la liste. Nous créons d'abord une liste nommée test_list, puis modifions (insérons ou supprimons) des éléments, inversons ou effaçons les éléments. list, comme suit :

>>> 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
[]

Si nous regardons le code ci-dessus, nous pouvons voir les opérations associées à la liste - ajouter, supprimer, modifier et vérifier. Il existe également des méthodes intégrées qui le sont. ne sont pas présentés ici et sont laissés aux lecteurs pour qu'ils les découvrent et les expérimentent par eux-mêmes.

Bases de l'allocation de mémoire des listes Python

Regardons donc cette démonstration d'espace supplémentaire à travers la pratique du codage et la relation entre la taille réelle du tableau conservé en mémoire et la taille donnée.

Accédez au notebook Jupyter pour vous entraîner. Ou utilisez n’importe quel éditeur ou environnement de développement de votre choix. Copiez le code écrit ci-dessous.

# 导入sys模块能方便我们使用gestsizeof函数
import sys

# set n
n = 20
# set empty list
list = []
for i in range(n):
a = len(list)
# 调用getsizeof函数用于给出Python中存储对象的真实字节数
b = sys.getsizeof(list)
print('Length:{0:3d}; Size of bytes:{1:4d}'.format(a, b))
# Increase length by one
list.append(n)

Exécutez le code et vous pouvez voir le résultat suivant :

Maintenant, à mesure que nous augmentons la longueur de la liste, les octets augmentent également. Analysons-le. Lorsque l'élément à la position Longueur : 1

est rempli dans la liste, le nombre d'octets passe de 64 à 96, soit une augmentation de 32 octets. Étant donné que cette expérience a été réalisée sur une machine 64 bits, cela signifie que chaque adresse mémoire est de 64 bits (soit 8 octets). Les 32 octets supplémentaires correspondent à la taille du tableau alloué pour stocker 4 références d'objet. Lors de l'ajout du 2ème, 3ème ou 4ème élément, il n'y a aucun changement dans l'utilisation de la mémoire. Le nombre d'octets 96 peut fournir des références à 4 objets.

96 = 64 + 8 fois 4

quand Longueur : 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代码进行实现。希望你能从此以复杂的方式学会数组。总结发言，其实越是简单的操作，背后实现原理可能很复杂。

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!