Théorie 4.1: liste avec tableau #
- Une liste est un tableau qui peut grandir et rapetisser
ListeJava<Character> liste = new ListeJava<>(Character.class);
liste; // []
liste.add('a') // [a]
liste.add('b') // [a,b]
liste.add('c') // [a,b,c]
liste.set(1,'d') // [a,d,c]
liste.remove('a') // [b,c]
-
Comment implanter une liste de façon efficace?
-
Ça dépend. Efficace pour quelle opération?:
- la modification d’éléments existants? (module 5.1)
- l’ajout et le retrait de nouveaux éléments? (module 5.2)
-
Rappel, voici les méthodes d’une liste
void add(E e); // ajoute à la fin
void addAll(E[] valeurs_a_ajouter); // insère toutes les valeurs
void insert(int position, E e); // insère une nouvelle valeur à la position i
void set(int position, E e); // modifie la valeur à la position i
E get(int position); // obtenir la valeur à la position i
void clear(); // vide la liste
int size(); // taille de la liste
boolean isEmpty(); // si vide
boolean contains(Object o); // si la liste contient la valeur o
int indexOf(Object o); // indice de la valeur o
void removeValue(Object o); // indice de la valeur o
void remove(int position); // indice de la valeur o
O(1)
: temps constant
#
-
Quand on a parlé d’efficacité, on a définit:
- Efficace:
O(log(n))
: temps logarithmiqueO(n)
: temps linéaire
- Pas efficace:
O(n2)
: temps quadratiqueO(2n)
: temps exponentiel
- Efficace:
-
Il faut ajouter:
- Efficace:
O(1)
: temps constant- le nombre d’instructions ne dépend pas de la taille des données
- Efficace:
-
Accéder à une valeur dans un tableau se fait en temps contant:
char[] tableau = new char[TAILLE];
char element(int position){
return tableau[position]; // 1 instruction
// même si TAILLE est grand
- Même chose pour modifier une valeur dans un tableau:
char[] tableau = new char[TAILLE];
void modifier(int position, char element){
tableau[position] = element; // 1 instruction
// même si TAILLE est grand
}
Liste par tableau naïve #
- Le plus simple est de mémoriser les éléments de la liste dans un tableau
public class ListeJavaNaive<E extends Object> extends ListeJava<E> {
private E[] elements;
- La modification d’un élément existant se fera en temps constant
@Override
public void set(int i, E e) {
elements[i] = e;
}
- Pour ajouter un nouvel élément, c’est plus compliqué:
@Override
public void add(E e) {
E[] nouveauxElements = nouveauTableau(elements.length + 1);
for(int i = 0; i < elements.length; i++){
nouveauxElements[i] = elements[i];
}
nouveauxElements[nouveauxElements.length - 1] = e;
elements = nouveauxElements;
}
-
Pour ajouter un élément, il faut:
- créer un nouveau tableau plus grand d’un emplacement
- copier les éléments existants dans le nouveau tableau
- mémoriser le nouvel élement dans le nouvel emplacement
-
L’opération se fait en temps linéaire
O(n)
-
Le problème est que
add
est typiquement utilisé dans une boucle -
P.ex. pour mélanger une liste:
ListeJava<Character> melanger(ListeJava<Character> entree){
ListeJava<Character> resultat;
resultat = nouvelleListe();
while(!entree.isEmpty()){
int positionAuHasard = alea.nextInt(entree.size());
Character elementAuHasard = entree.get(positionAuHasard);
resultat.add(elementAuHasard); // cache une boucle?
entree.remove(positionAuHasard); // cache une boucle?
}
return resultat;
}
-
On a une boucle qui visite les éléments de
entree
- si chaque
add
requiert une autre boucle sur les éléments - on va avoir une boucle dans une boucle et donc
O(n2)
- si chaque
Liste par tableau plus efficace #
-
Si on veut être plus efficace, il faut éviter de toujours recopier les éléments
-
Une façon de faire est d’utiliser un tableau plus grand
public class ListeJavaTableau<E extends Object> extends ListeJava<E> {
private final int TAILLE_INITIALE = 1; // Pour tester agrandir
private E[] grosTableau;
private int indiceDernierElement = -1;
- Quand on ajoute un élément, on peut simplement mémoriser que la liste grandit
@Override
public void add(E e) {
indiceDernierElement++;
grosTableau[indiceDernierElement] = e;
- Évidemment, il faudra parfois faire grandir le tableau aussi:
@Override
public void add(E e) {
if(indiceDernierElement == grosTableau.length - 1) {
agrandir();
}
indiceDernierElement++;
grosTableau[indiceDernierElement] = e;
-
Néanmoins,
add
est beaucoup plus efficace: -
Ainsi que retirer à la fin:
-
C’est un exemple de compromis temps/espace mémoire
- en utilisant plus d’espace mémoire, on améliore le temps d’exécution
-
Par contre, retirer au début est presqu’identique:
Exemples #
Ajouts à partir d’une liste vide #
liste
|
[null,null,null,...,null]
indiceDernierElement == -1
|
liste.add('a')
|
[a,null,null,...,null]
indiceDernierElement == 0
|
liste.add('b')
|
[a,b,null,...,null]
indiceDernierElement == 1
|
Un retrait au milieu #
liste
|
[a,b,c,d,e,null,...,null]
indiceDernierElement == 4
|
liste.remove('c')
|
[a,b,d,d,e,null,...,null]
[a,b,d,e,e,null,...,null]
indiceDernierElement == 3
|
Implanter un mélangeur efficace #
- Re-considérer notre mélangeur:
ListeJava<Character> melanger(ListeJava<Character> entree){
ListeJava<Character> resultat;
resultat = nouvelleListe();
while(!entree.isEmpty()){
int positionAuHasard = alea.nextInt(entree.size());
Character elementAuHasard = entree.get(positionAuHasard);
resultat.add(elementAuHasard); // efficace
entree.remove(positionAuHasard); // à éviter!
}
return resultat;
}
-
L’efficacité du mélangeur est améliorée:
-
Mais on peut faire mieux!
-
Comment modifier notre mélangeur pour ne pas utiliser
remove
? -
On pourrait alors avoir:
-
Pour écrire du code efficace, il faut:
- savoir quelles opérations sont coûteuses sur notre structure de données