Théorie 4.1: liste naïve #
- Une liste est un tableau qui peut grandir et rapetisser
Liste<Character> liste = new Liste<>(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 ListeNaive<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
addest typiquement utilisé dans une boucle -
P.ex. pour mélanger une liste:
Liste<Character> melanger(Liste<Character> entree){
Liste<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
addrequiert une autre boucle sur les éléments - on va avoir une boucle dans une boucle et donc
O(n2)
- si chaque