Built-in data structures

Reading time3 min

En bref

Résumé de l’article

Lorsqu’on souhaite stocker plus d’une valeur dans une variable, une structure de données est nécessaire. Les langages de programmation de haut niveau, comme Python, proposent (entre autres) quatre structures de données intégrées : listes, ensembles, tuples et dictionnaires.

Cet article décrit brièvement les spécificités de chacun de ces types de données.

Points clés

  • Une liste est utilisée pour stocker plusieurs valeurs indexées et peut évoluer.

  • Un ensemble stocke plusieurs valeurs uniques et immuables de manière non ordonnée et peut évoluer.

  • Un tuple stocke plusieurs valeurs indexées immuables.

  • Un dictionnaire est une structure pour stocker des paires clé/valeur.

Contenu de l’article

1 — Qu’est-ce qu’une liste ?

Le type liste est sans doute la structure de données la plus couramment utilisée pour stocker plusieurs valeurs dans une seule variable. Ses principales propriétés sont :

  • Les valeurs dans une liste sont ordonnées (c’est une séquence), ce qui signifie que chaque valeur est associée à un indice allant de 0 à la taille de la liste moins un.
  • Une liste permet les valeurs dupliquées.
  • Une liste est un type de données mutable, permettant ainsi la modification de ses valeurs.
  • Une liste est dynamique, ce qui signifie que des valeurs peuvent être ajoutées ou supprimées.
  • Une liste permet la sélection par tranches.
# Define a list
my_structure = [1, 2, 3, 4, 5]
print(f"Initial list: {my_structure} with id {id(my_structure)}")

# Illustration of dynamic property
my_structure.append(6)

# Illustration of mutable property
my_structure[0] = 2
print(f"Modified list: {my_structure} still with id {id(my_structure)}")

# Illustration of slice selection
print(f"Two last elements: {my_structure[-2:]}")
import java.util.ArrayList;
import java.util.List;

public class ExampleList {
    public static void main(String[] args) {
        List<Integer> T = new ArrayList<>();
        T.add(1);
        T.add(2);
        T.add(3);
        T.add(4);
        T.add(5);

        System.out.println("Initial list: " + T + " with ref " + System.identityHashCode(T));

        T.add(6); // Appending an integer instead of a string
        T.set(0, 2); // Modifying the first element

        System.out.println("Modified list: " + T + " still with ref " + System.identityHashCode(T));
        System.out.println("Two last elements: " + T.subList(T.size() - 2, T.size()));
    }
}
Output
Initial list: [1, 2, 3, 4, 5] with id 138495927307072
Modified list: [2, 2, 3, 4, 5, 6] still with id 138495927307072
Two last elements: [5, 6]
TODO

2 — Qu’est-ce qu’un ensemble ?

Un ensemble possède les mêmes propriétés que celles de la théorie mathématique des ensembles. Ses principales propriétés sont :

  • Les valeurs dans un ensemble sont non ordonnées, par conséquent une valeur ne peut pas être modifiée.
  • Un ensemble n’autorise pas les valeurs dupliquées.
  • Un ensemble est un type de données mutable, permettant ainsi l’ajout ou la suppression de valeurs.
# Define a set
my_structure = {1, 3, 5, 5}
print(f"Initial set: {my_structure} with id {id(my_structure)}")

# Add an element
my_structure.add(6)
print(f"Modified set: {my_structure} with id {id(my_structure)}")

# Test if an element belongs to the set
print(f"Contains 4: {4 in my_structure}")
import java.util.HashSet;
import java.util.Set;

public class ExampleSet {
    public static void main(String[] args) {
        Set<Integer> T = new HashSet<>();
        T.add(1);
        T.add(3);
        T.add(5);
        T.add(5); // Duplicate element, will not be added

        System.out.println("Initial set: " + T + " with hash code " + System.identityHashCode(T));
        T.add(6);
        System.out.println("Modified set: " + T + " with hash code " + System.identityHashCode(T));
        System.out.println("Contains 4: " + T.contains(4));
    }
}
Output
Initial set: {1, 3, 5} with id 127760255235264
Modified set: {1, 3, 5, 6} with id 127760255235264
Contains 4: False
TODO

3 — Qu’est-ce qu’un tuple ?

Un tuple est utilisé pour stocker plusieurs valeurs qui ne changent pas. Ses principales propriétés sont :

  • Les valeurs dans un tuple sont ordonnées (c’est une séquence).
  • Un tuple permet les valeurs dupliquées.
  • Un tuple est un type de données immuable, donc son contenu ne peut pas évoluer.
# Initialize a tuple
my_structure = (1, "3", 3.14)
print(f"Initial tuple: {my_structure} with id {id(my_structure)}")
print(f"Second element: {my_structure[1]}")

# Extend the tuple into a new variable
my_structure += ("4",)
print(f"New tuple: {my_structure} with id {id(my_structure)}")
import java.util.Arrays;

public class ExampleTuple {
    public static void main(String[] args) {
        Object[] T = {1, "3", 3.14};
        System.out.println("Initial tuple: " + Arrays.toString(T) + " with hash code " + System.identityHashCode(T));
        System.out.println("Second element: " + T[1]);
        
        Object[] newT = Arrays.copyOf(T, T.length + 1);
        newT[newT.length - 1] = "4";
        System.out.println("New tuple: " + Arrays.toString(newT) + " with hash code " + System.identityHashCode(newT));
    }
}
Output
Initial tuple: (1, '3', 3.14) with id 132604205639104
Second element: 3
New tuple: (1, '3', 3.14, '4') with id 132604205672832
TODO

4 — Qu’est-ce qu’un dictionnaire ?

Un dictionnaire, aussi appelé tableau associatif, hash ou map, indexe les valeurs en utilisant des clés afin de donner une sorte de sémantique à chaque valeur stockée. Il peut être vu comme une fonction surjective $dict : key \rightarrow value$. Ses principales propriétés sont :

  • Un dictionnaire est utilisé pour stocker des paires clé/valeur.
  • Un dictionnaire n’autorise pas les clés dupliquées.
  • Un dictionnaire est un type de données mutable, permettant ainsi la modification de ses valeurs.
  • Un dictionnaire est dynamique, ce qui signifie que des paires clé/valeur peuvent être ajoutées ou supprimées à tout moment.

Voici un exemple de programme qui indexe les mots d’un texte dans un dictionnaire :

# Define the text to index
text = "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Sed lacinia, nibh a tincidunt luctus, tortor nunc molestie ante, ut egestas est sapien quis orci. Nunc laoreet eget ipsum id rhoncus. Curabitur vel nibh bibendum, eleifend nibh gravida, tempus massa. Donec id felis blandit, pretium nisl ut, sagittis ligula. Curabitur vitae accumsan ex. Pellentesque interdum condimentum sem, eu aliquet arcu mollis ac. Mauris pellentesque lobortis mi, eget aliquam mauris gravida vel. Nulla quis dui vel arcu malesuada vulputate. Praesent nisi ex, tincidunt fermentum augue eu, cursus vehicula ipsum. Nam vel diam gravida, ultrices eros sed, cursus libero. Etiam maximus tincidunt metus in maximus."

# Process the text
words = text.split()
indexes = {}
for i, word in enumerate(words):
    if word not in indexes:
        indexes[word] = []
    indexes[word].append(i)
print(indexes)
// Needed imports
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * To run this code, you need to have Java installed on your computer, then:
 * - Create a file named `Main.java` in a directory of your choice.
 * - Copy this code in the file.
 * - Open a terminal in the directory where the file is located.
 * - Run the command `javac Main.java` to compile the code.
 * - Run the command `java -ea Main` to execute the compiled code.
 * Note: '-ea' is an option to enable assertions in Java.
 */
public class Main {

    /**
     * This function was translated from the Python code.
     * This is also the case for the contents of the "main" function.
     *
     * @param text The text to index.
     * @return     The dictionary containing the indexes of all the words in the text.
     */
    public static Map<String, List<Integer>> indexWords(String text) {
        // Split the text into words
        String[] words = text.split("\\s+");
        // Create a map to store the indexes
        Map<String, List<Integer>> indexes = new HashMap<>();

        // Loop over the words and populate the index map
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            // If the word is not yet in the map, add it
            if (!indexes.containsKey(word)) {
                indexes.put(word, new ArrayList<>());
            }
            // Append the current index to the list
            indexes.get(word).add(i);
        }

        return indexes;
    }

    /**
     * This is the entry point of your program.
     * It contains the first codes that are going to be executed.
     *
     * @param args Command line arguments received.
     */
    public static void main(String[] args) {
        // Let's test the method
        String text = "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Sed lacinia, nibh a tincidunt luctus, tortor nunc molestie ante, ut egestas est sapien quis orci. Nunc laoreet eget ipsum id rhoncus. Curabitur vel nibh bibendum, eleifend nibh gravida, tempus massa. Donec id felis blandit, pretium nisl ut, sagittis ligula. Curabitur vitae accumsan ex. Pellentesque interdum condimentum sem, eu aliquet arcu mollis ac. Mauris pellentesque lobortis mi, eget aliquam mauris gravida vel. Nulla quis dui vel arcu malesuada vulputate. Praesent nisi ex, tincidunt fermentum augue eu, cursus vehicula ipsum. Nam vel diam gravida, ultrices eros sed, cursus libero. Etiam maximus tincidunt metus in maximus.";
        Map<String, List<Integer>> index = indexWords(text);
        System.out.println(index);
    }

}
Output
{'Lorem': [0], 'ipsum': [1, 27], 'dolor': [2], 'sit': [3], 'amet,': [4], 'consectetur': [5], 'adipiscing': [6], 'elit.': [7], 'Sed': [8], 'lacinia,': [9], 'nibh': [10, 32, 35], 'a': [11], 'tincidunt': [12, 80, 98], 'luctus,': [13], 'tortor': [14], 'nunc': [15], 'molestie': [16], 'ante,': [17], 'ut': [18], 'egestas': [19], 'est': [20], 'sapien': [21], 'quis': [22, 71], 'orci.': [23], 'Nunc': [24], 'laoreet': [25], 'eget': [26, 65], 'id': [28, 40], 'rhoncus.': [29], 'Curabitur': [30, 48], 'vel': [31, 73, 88], 'bibendum,': [33], 'eleifend': [34], 'gravida,': [36, 90], 'tempus': [37], 'massa.': [38], 'Donec': [39], 'felis': [41], 'blandit,': [42], 'pretium': [43], 'nisl': [44], 'ut,': [45], 'sagittis': [46], 'ligula.': [47], 'vitae': [49], 'accumsan': [50], 'ex.': [51], 'Pellentesque': [52], 'interdum': [53], 'condimentum': [54], 'sem,': [55], 'eu': [56], 'aliquet': [57], 'arcu': [58, 74], 'mollis': [59], 'ac.': [60], 'Mauris': [61], 'pellentesque': [62], 'lobortis': [63], 'mi,': [64], 'aliquam': [66], 'mauris': [67], 'gravida': [68], 'vel.': [69], 'Nulla': [70], 'dui': [72], 'malesuada': [75], 'vulputate.': [76], 'Praesent': [77], 'nisi': [78], 'ex,': [79], 'fermentum': [81], 'augue': [82], 'eu,': [83], 'cursus': [84, 94], 'vehicula': [85], 'ipsum.': [86], 'Nam': [87], 'diam': [89], 'ultrices': [91], 'eros': [92], 'sed,': [93], 'libero.': [95], 'Etiam': [96], 'maximus': [97], 'metus': [99], 'in': [100], 'maximus.': [101]}
{mollis=[59], ante,=[17], sem,=[55], vel.=[69], adipiscing=[6], est=[20], cursus=[84, 94], eleifend=[34], accumsan=[50], Pellentesque=[52], egestas=[19], augue=[82], nunc=[15], mi,=[64], orci.=[23], mauris=[67], maximus.=[101], id=[28, 40], Nulla=[70], molestie=[16], vel=[31, 73, 88], elit.=[7], ut=[18], lobortis=[63], Etiam=[96], luctus,=[13], in=[100], lacinia,=[9], fermentum=[81], vulputate.=[76], sed,=[93], eu=[56], Sed=[8], pellentesque=[62], vitae=[49], ipsum=[1, 27], amet,=[4], felis=[41], Curabitur=[30, 48], laoreet=[25], tempus=[37], Mauris=[61], ac.=[60], arcu=[58, 74], dolor=[2], bibendum,=[33], metus=[99], rhoncus.=[29], ex,=[79], vehicula=[85], ex.=[51], diam=[89], sit=[3], interdum=[53], a=[11], nisi=[78], tortor=[14], blandit,=[42], tincidunt=[12, 80, 98], nisl=[44], ipsum.=[86], ultrices=[91], condimentum=[54], aliquam=[66], massa.=[38], ut,=[45], Praesent=[77], nibh=[10, 32, 35], gravida,=[36, 90], Donec=[39], libero.=[95], Lorem=[0], aliquet=[57], malesuada=[75], pretium=[43], sapien=[21], Nunc=[24], dui=[72], quis=[22, 71], Nam=[87], eu,=[83], consectetur=[5], eget=[26, 65], sagittis=[46], ligula.=[47], gravida=[68], eros=[92], maximus=[97]}

Pour aller plus loin

On dirait que cette section est vide !

Y a-t-il quelque chose que vous auriez aimé voir ici ? Faites-le nous savoir sur le serveur Discord ! Peut-être pourrons-nous l’ajouter rapidement. Sinon, cela nous aidera à améliorer le cours pour l’année prochaine !

Pour aller au-delà