Python >> Tutoriel Python >  >> Python Tag >> Array

Qu'est-ce qu'un tableau en informatique ?

En informatique, une structure de données matricielle consiste en une collection d'éléments, généralement du même type, comme un entier ou une chaîne. Chaque élément est identifié par un index de tableau. Les tableaux sont conçus pour permettre un accès extrêmement efficace aux éléments individuels par index :la complexité d'exécution est constante avec une taille de tableau croissante ! La raison en est que l'index de l'élément est calculé à partir du tuple d'index de l'élément à l'aide d'une formule fermée.

Matrice vidéo

Définition de tableau

Un tableau est un ordonné collection d'éléments indexé parentiers contigus .

  • Commandé :L'ordre des éléments est fixe et bien défini, contrairement aux ensembles qui ne sont pas ordonnés.
  • Éléments :Un tableau est constitué d'éléments, dans la grande majorité des cas ces éléments sont du même type.
  • Indices contigus :Les indices commencent à 0 et s'incrémentent de un pour chaque élément suivant. Tous les entiers entre 0 et n-1 pointent sur exactement un élément. Il n'y a pas de "trous" dans la série d'indices.

Applications de baie

Les tableaux sont largement utilisés dans tous les principaux langages de programmation tels que C++, Java et Python. Par exemple, un moteur de recherche peut stocker toutes les URL des sites Web explorés dans un tableau. Par la suite, il peut trier l'URL par ordre alphabétique en fonction de la structure de données du tableau. Le tableau est souvent la structure de données de choix pour stocker les données de manière fiable et efficace, permettant un accès facile à tous les éléments de données.

Voici quelques applications des tableaux :

  • Les tableaux peuvent implémenter des vecteurs mathématiques.
  • Les tableaux peuvent implémenter des matrices multidimensionnelles.
  • Les tableaux sont utilisés pour implémenter d'autres structures de données telles que des listes, des ensembles, des tables de hachage, des piles et bien d'autres. Ces structures de données, à leur tour, sont utilisées par chaque programme logiciel non trivial.
  • Les tableaux sont utilisés dans les listes de contiguïté et les matrices pour représenter les structures de données de graphe. Voici quelques applications des graphiques.
  • Les tableaux sont utilisés dans la planification du processeur pour créer des listes de priorités afin de déterminer le processus à planifier ensuite sur le processeur.
  • Les tableaux sont utilisés par des algorithmes de tri tels que Quicksort.

Durée d'exécution de la baie et efficacité de l'espace

La plupart des langages de programmation stockent le tableau très efficacement en mémoire. Par exemple, il place tous les éléments dans la même région de mémoire, de sorte qu'un grand nombre de valeurs de tableau peuvent être lues en même temps à partir de la mémoire.

Voici l'efficacité d'exécution d'un tableau pour différentes opérations :

Fonctionnement Complexité d'exécution moyenne Complexité d'exécution dans le pire des cas
Accès
O(1) O(1)
Rechercher
O(n) O(n)
Insertion
O(n) O(n)
Suppression O(n) O(n)

En règle générale :modifier le tableau est relativement coûteux, alors que lire des éléments du tableau est extrêmement bon marché ! Le modèle d'utilisation optimal des tableaux est de ne jamais le modifier et d'accéder fréquemment aux éléments individuels (« lecture-non-écriture » ).

La complexité spatiale d'un tableau est O(n) pour n éléments :chaque élément nécessite un emplacement mémoire explicite. Ainsi, plus d'éléments de tableau entraînent plus d'exigences d'espace. Cependant, la relation croît proportionnellement, pas plus vite, avec l'augmentation du nombre d'éléments :le double des éléments nécessite le double de l'espace.

Indexation des tableaux

Vous pouvez accéder à chaque élément du tableau via des indices.

  • L'indice du premier élément du tableau est 0.
  • L'index du deuxième élément est 1.
  • L'indice du i-ème élément est i-1.

Comme le premier index de tableau est généralement l'entier 0, la plupart des informaticiens l'appellent indexation à base zéro .

Voici un exemple Python d'indexation de tableau utilisant un tableau de chaînes :

>>> authors = ['Rowling', 'King', 'Brown', 'Peterson']
>>> authors[0]
'Rowling'
>>> authors[1]
'King'
>>> authors[2]
'Brown'
>>> authors[3]
'Peterson'

Méthodes de tableau en Python

Notez que Python implémente uniquement le type de données de liste dans la bibliothèque standard. Si vous souhaitez utiliser des tableaux, vous devrez importer la bibliothèque NumPy. Cependant, le type de données de liste est utilisé de manière très similaire au type de données de tableau dans d'autres langages de programmation, nous l'utilisons donc de manière interchangeable ici.

Voici les méthodes de tableau/liste les plus importantes en Python :

Méthode Description
array.append(x) Ajoute l'élément x à array .
array .clear() Supprime tous les éléments de array –qui devient vide.
array.copy() Renvoie une copie de array . Copie uniquement le tableau, pas ses éléments (copie superficielle).
array.count(x) Compte le nombre d'occurrences de l'élément x en array .
array.extend(iter) Ajoute tous les éléments d'un iter itérable (par exemple une liste) à array .
array.index(x) Renvoie la position (index) de la première occurrence de la valeur x en array .
array.insert(i, x) Insère l'élément x à la position (index) i en array .
array.pop() Supprime et renvoie le dernier élément de array .
array.remove(x) Supprime et renvoie la première occurrence de l'élément x en array .
array.reverse() Inverse l'ordre des éléments dans array .
array.sort() Trie les éléments en array par ordre croissant.

Quand utiliser les tableaux ?

En pratique, vous devez décider d'utiliser ou non une liste liée ou un tableau pour stocker une séquence de valeurs de données. Utilisez des tableaux lorsque vous avez besoin d'un accès rapide aux éléments et aux listes lorsque vous devez agrandir ou réduire dynamiquement la séquence.

Renforcez vos compétences en codage

Références

  • https://en.wikipedia.org/wiki/Array_data_structure
  • https://www.toolsqa.com/data-structures/array-in-programming/
  • https://www.w3schools.com/python/gloss_python_arrray_what_is.asp
  • https://techterms.com/definition/array