3 minutes
Tableaux Types de Données et Analyse
Dernière mise à jour: 15 octobre, 2022§Commençons Par Une Description
Un tableau est une donnée structurée qui est ordonnée et indexée. Les tableaux sont créés de différentes manières dans chaque langue mais ils sont tous indexés presque de la même manière. Dans ce post, je vais parler de la structure de données du tableau dans quelques langues et comment pouvons-nous travailler avec eux.
§Définir le Tableau avec Une Taille et Un Type Initiaux
La façon dont nous définissons les tableaux peut varier et affecter les performances. Pour des exemples dans des langages comme Python, JavaScript et Java, nous n'avons pas besoin de définir la taille initiale du tableau. En Python et JavaScript, nous pouvons conserver différents types de données dans la même structure de tableau. Mais en Java, nous devons définir le type des valeurs que nous allons conserver dans le tableau.
Ne définissant pas de taille initiale pour un tableau, augmentons facilement la taille de notre tableau en y ajoutant simplement plus d'éléments. C'est parce que dans les coulisses, notre langage manipule l'allocation de mémoire elle-même. Il existe de nombreuses méthodes pour augmenter rapidement la taille du tableau. La méthode que j'aime travailler avec les langages dans lesquels nous devons définir une taille consiste à vérifier la taille du tableau et à doubler la taille si nécessaire. J'ai écrit le code qui imitera le comportement d'un tableau dynamique en python. Même s'il est fondamentalement intégré à python, il est important de voir comment cela fonctionne réellement :
import ctypes
# python n'a pas de tableau statique comme en java
class DynamicArray(object):
# the constructor
def __init__(self):
self.n = 0 # Nombre réel d'éléments à l'intérieur du tableau
self.capacity = 1 # capacité initial
self.A = self.make_array(self.capacity) # créer le tableau avec une capacité donnée
# len(instance) renvoie la longueur de l'instance
def __len__(self):
return self.n
def __getitem__(self, k):
# gérer si l'index k existe dans le tableau
if not 0 <= k < self.n:
return IndexError('Hors limite ! Pas d'insertion')
return self.A[k] # Retourner s'il existe bien sur
def append(self, ele):
# si la capacité est atteinte doubler la taille
if self.n == self.capacity:
self._resize(2*self.capacity)
self.A[self.n] = ele # ajouter l'élément
self.n += 1 # augmenter la taille du tableau de un
def insertAt(self, item, index): # insérer à un certain index
if index < 0 or index > self.n:
# si index est négatif ou supérieur à la taille du tableau
print("Indice invalide")
return
# à nouveau si la taille atteint la capacité
if self.n == self.capacity:
self._resize(2*self.capacity)
# déplacer tous les éléments après l'index donné d'un point vers la droite
# pour créer l'espace, aller de droite à gauche
for i in range(self.n-1, index-1, -1):
self.A[i+1] = self.A[i]
#enfin insertion de l'élément
self.A[index] = item
self.n+=1
# supprimer de la fin du tableau
def delete(self):
# gérer un tableau vide
if self.n == 0:
print("Le tableau est vide")
return
# donner 0 au dernier élément du tableau
self.A[self.n-1]
self.n -= 1
# supprimer à un certain index
def removeAt(self, index):
# similaire à la méthode insertAt
if self.n == 0:
print("Le tableau est vide")
if index < 0 or index >= self.n:
return IndexError("L'index est hors limites ! Pas de suppression")
# si c'est le dernier élément du tableau
if index == self.n -1:
self.A[index] = 0
self.n -= 1
return
for i in range(index, self.n-1):
# déplacer les éléments d'un index vers la gauche
self.A[i] = self.A[i+1]
# a supprimé un élément afin de raccourcir le tableau
self.A[self.n-1] = 0
self.n -= 1
# Enfin méthode de redimensionnement pour les augmentations de capacité
# Doubler la capacité à chaque fois
def _resize(self, new_cap):
B = self.make_array(new_cap) # Nouveau tableau, plus grand
# déplacer tout à l'intérieur de la nouvelle valeur
for k in range(self.n):
B[k] = self.A[k]
self.A = B
self.capacity = new_cap
def make_array(self, new_cap):
return (new_cap * ctypes.py_object)()
# Instantiate
arr = DynamicArray()
# Ajouter un nouvel élément
arr.append(1)
arr.append(2)
arr.append(3)
arr.append(4)
arr.append(5)
arr.append(6)
print(len(arr))
Vous pouvez recréer et modifier ce code dans le langage de votre choix pour pratiquer les opérations de tableau dynamique. Par exemple, en C ou Java.
En C, nous définissons les tableaux avec une taille et des types initiaux. Cela présente de nombreux avantages en termes de vitesse et d'utilisation de la mémoire. C'est l'une des raisons pour lesquelles "C" est plus rapide que Python et JavaScript en général.
En python, nous pouvons également utiliser la méthode array pour créer des tableaux fixes (depuis la version 3.3):
import array
list = list(range(10))
arr = array.array('i', list)
arr # array('i', [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
i ici signifie "integer". Il s'agit d'une option plus performante pour les listes intégrées en python. Peut-être envisager de l'utiliser à l'avenir. Vous devez également créer des tableaux avec des tailles et des types de données initiaux lorsque vous utilisez des frameworks populaires en science des données, comme numpy. Par exemple:
import numpy as np
np.ones((2, 5), dtype=float)
Cela nous donnerait la structure suivante :
array([[ 1., 1., 1., 1., 1.],
[ 1., 1., 1., 1., 1.],
[ 1., 1., 1., 1., 1.]])
JavaScript a un objet qui nous permet de créer un tableau typé et dimensionné. TypedArray décrit la structure qui représente et le tableau avec le [tampon de données binaires sous-jacent](https:// developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/ArrayBuffer). Voici comment créer un tableau typé en javascript :
// Nous créons un tableau typé en définissant sa taille en octets et
// le type de données qu'il va contenir
const tp1 = new Int8Array(4); Int8Array [0, 0, 0, 0]
tp1[3] = 77;
console.log(tp1); Int8Array [0, 0, 0, 77]
Si vous voulez en savoir plus sur le constructeur TypedArray, vous pouvez lire cet article. Il vaut vraiment la peine d'être lu je vous assure. Si vous ne savez pas grand-chose sur les types de données, vous voudrez peut-être d'abord lire cet article de wikipedia.
§Analyse des Opérations Sur Les Tableaux
Les opérations d'insertion et de suppression dans les tableaux javascript et les listes python coûtent du temps O (N) (linéaire). La raison derrière cela est que lorsque nous y insérons un élément, nous déplaçons les éléments après le point d'insertion. Nous libérons d'abord l'espace que nous voulons insérer en portant tous les éléments d'un index vers la droite. Lorsque cette opération est terminée, nous insérons l'élément dans l'index donné. La même opération est effectuée en sens inverse lorsque l'on veut faire une suppression. D'abord on vide l'index puis on pousse tout après l'index d'un index vers la gauche.
Les opérations de recherche ne prennent qu'un temps constant car nos tableaux sont indexés. En comparaison avec une liste chaînée par exemple, cette opération est nettement plus rapide (O(N) vs O(1)).
§Conclusion
Lorsque nous commençons à développer des applications et sautons les bases (parce que c'est beaucoup plus amusant de cette façon), cela peut nous coûter en termes de performances. Ce n'est jamais une mauvaise idée d'apprendre les bases de l'informatique et de la programmation pendant votre temps libre.
Maintenant, j'espère que vous avez une meilleure idée de la structure des données du tableau et que je pourrais vous inspirer pour aller plus loin. Continue d'apprendre !
Ilker AkbiyikTable Des Matières
Articles Similaires
