Xavier Tannier [email protected] Objets Java pour la RI Indexation et Recherche d'Information

Xavier [email protected]

Objets Java pour la RI

Indexation et Recherche d'Information

Les collections en Java


Objets JavaXavier Tannier

L’interface List

• Une liste = une collection d’éléments ordonnés

• Doublons possibles

• Exemples :– ArrayList<E> (un tableau redimensionnable)– LinkedList<E> (pour faire du FIFO / file)– ArrayDeque<E> (pour faire du FIFO et LIFO)

3



Les files prioritaires

• Exemples:– PriorityQueue<E>

– PriorityBlockingQueue<E> ("thread-safe")

• Permettent de créer des files en plaçant les éléments prioritaires en tête (grâce à un Comparator<E>)

4



Listes : que choisir ?

add get contains remove Commentaire

Tableau O(1) O(1) O(n) O(n) Non redimensionnable.

ArrayList O(1) / O(n)

O(1) O(n) O(n) Insertion plus lente lorsque le tableau doit être redimensionné.

LinkedList O(1) O(1) (en tête)

O(n) O(n) / O(1)

À utiliser si on accède aux éléments de tête. Suppression par l’itérateur en O(1)

ArrayDeque O(1) O(1)(en tête et en queue)

O(n) O(n) À utiliser si on accède aux éléments de tête ou de queue.En pratique plus rapide que LinkedList.

PriorityQueue O(log(n)) O(1)(en tête)

O(log(n)) O(log(n)) N’utiliser que si l’ordre souhaité n’est pas celui d’insertion.

5



L’interface Set

• Une collection d’éléments sans doublons

• Exemples :– HashSet<E> (rangement par le hashcode, ordre non conservé)

– LinkedHashSet<E> (rangement par le hashcode tout en conservant l’ordre d’insertion)

– TreeSet<E> (ensemble ordonné par un Comparator<E>)

6



Ensembles : que choisir ?


HashSet O(1) O(1) O(1) O(1) Ne conserve pas l’ordre des éléments.

TreeSet O(log(n)) O(log(n)) O(log(n)) O(log(n)) Souvent plus rapide de créer un HashSet puis de tout ordonner d’un coup dans un TreeSet.

LinkedHashSet O(1) O(1) O(1) O(1) Globalement plus lent que le HashSet (maintient en plus une liste chaînée), sauf pour le parcours qui est plus rapide.

7



L’interface Map

• Dictionnaire qui relie des clés et des valeurs.

• Les clés ne peuvent pas être dupliquées.

• Exemples :– HashMap<K, V> (rangement par le hashcode, ordre non conservé)

– LinkedHashMap<K, V> (rangement par le hashcode tout en conservant l’ordre d’insertion)

– TreeMap<K, V> (ensemble ordonné par un Comparator<E>)

8



Maps : que choisir ?


HashMap O(1) O(1) O(1) O(1) Ne conserve pas l’ordre des éléments.

TreeMap O(log(n)) O(log(n)) O(log(n)) O(log(n))

LinkedHashMap O(1) O(1) O(1) O(1) Globalement plus lent que le HashMap (maintient en plus une liste chaînée), sauf pour le parcours qui est plus rapide.

9



Et un dictionnaire bi-directionnel ?

• On aimerait avoir un dictionnaire qui marche dans les deux sens– Quel est l’identifiant de ce mot ?– À quel mot correspond cet identifiant ?

• Ça n’existe pas dans l’API native de java– Interface BidiMap de org.apache.commons.collections – À faire soi-même (voir plus loin)

10

Les objets Javaet la mémoire



Les objets Java

• L’API Java fournit énormément de classes d’objets qui couvrent de nombreux besoins essentiels (notamment les collections)

• Ces classes fournissent également de nombreuses méthodes pour faciliter la manipulation des objets

• On a souvent tendance à utiliser ces classes par facilité

• Les surcoûts possibles si on n’y prête pas garde:– Le temps de calcul (exemple : contains + add, contains + get, etc…)– La mémoire

• En raison des « frais généraux » (overheads) imposés par la gestion des objets• Exemple : entier pour conserver la taille d’une collection, etc.

12



Objets java et overheads : exemples

• Double : 24 octets

– (données = 33 % de la taille de l’objet)– NB : Ces valeurs (et toutes les suivantes) peuvent varier selon l’architecture

13

entête données (double) alignement

12 octets 8 octets 4 octets

• Boolean : 16 octets (!)entête données alignement

12 octets 1 octet 3 octets




• char[2] : 24 octets

14

entête données (2 car.) alignement

16 octets 4 octets 4 octets

• String : – Dépend beaucoup des versions et des architectures– Faites le test à la maison :

• Créez 100 000 instances vides de String• Regardez la mémoire consommée• Faites la même chose avec 100 000 instances de String de 20 caractères




• TreeMap

15

overheads

48 octets

overheads

40 octets

données

X octets

pour chaque entrée

Pour 100 entrées d’un TreeMap<Double, Double> : - 8,6 Ko - 82 % d’overheads




• double[100] – double[100]

– 1632 octets– 2 % d’overheads

16

overheads données (double × 100)

16 octets 800 octets

overheads données (double × 100)

16 octets 800 octets

Toujours se demander :Est-ce vraiment utile ?

• Le TreeMap<Double, Double> permet en plus :– D’avoir un tableau redimensionnable– De garantir l’ordre pendant la mise à jour

Exemple :Le dictionnaire



Dictionnaire : besoins

• Un lien bi-directionnel entre identifiant et terme– Quel est l’identifiant de ce mot ?– À quel mot correspond cet identifiant ?

• Indispensable pour gérer efficacement un index

Pourquoi ?

• La solution de facilité :– HashMap<String, Integer>– HashMap<Integer, String>

18



Qu’est-ce qu’une HashMap ?• HashMap<K, V>• Capacité initiale de 2n (avec par défaut n = 4 : 16 éléments)

table = new Entry[2^n]Une « Entry » est une liste chaînée de paires <K, V>

• Ajout d’une paire <k, v> :h = hashcode(k)i = couper h pour qu’il rentre dans n bitsentries = table[i]si entries == null on crée une nouvelle liste chaînée avec k dedansSinon (collision) on ajoute k à entriessi le nombre d’entrées dépasse un certain seuil on les recopie dans un tableau deux fois plus grand

19



Qu’est-ce qu’une HashMap ?

• Recherche d’une valeur pour la clé k :h = hashcode(k)i = couper h pour qu’il rentre dans n bitsentries = table[i]On parcourt entries jusqu’à trouver la clé recherchéeOn renvoie la valeur correspondante

20



Les overheads du dictionnaire

• Avec deux HashMap• Pour un vocabulaire de 100 000 mots :• Nombre d’objets

= au moins ( 1 + 100 000 + 100 000 + 100 000 ) × 2

= plus de 600 000 overheads

HashMapEntry String Integer

2 sens

21



Alternative

• On sait qu’on aura environ n mots• Capacité fixe de n

table = new String[n]

• Ajout d’un mot mot :h = hashcode(k)id = couper h pour qu’il rentre dans log2 (n) bitschaîne = table[id]si chaîne != null mais chaîne != k (collision) j = id + 1 tant que table[j] != null j++ table[j] = chaînesinon table[id] = chaîne

22



Alternative

• Recherche du mot correspondant à l’identifiant idmot = table[id]

• Recherche de l’identifiant pour la clé mot

h = hashcode(k)id = couper h pour qu’il rentre dans log2 (n) bitschaîne = table[id]si chaîne == mot renvoyer idsinon j = id + 1 tant que table[j] != null j++ renvoyer j

23



Alternative : les overheads

• Avec un tableau de String + un HashMap pour les collisions du

hashcode• Pour un vocabulaire de 100 000 mots, avec 1 % de collisions• Nombre d’objets

= au moins 1 + 100 000 + 1 + 1 000 + 1 000 + 1 000

= plus de 100 000 overheads

ObjetString HashMap pour les collisions

24



Alternative

• Tableau de String beaucoup plus économe en mémoire que la double HashMap

• Performances équivalentes en temps de calcul

• La HashMap propose de nombreuses autres fonctionnalités :– Taille redimensionnable (au prix d’un temps de calcul élevé)– Itération– D’autres méthodes prédéfinies devront être recodées (size(), contains(),

remove(), …)

• Mais ces fonctionnalités sont superflues dans notre cas

25

Bilan



Bilan

• Quand la mémoire est importante :– Se méfier des objets Java « tout prêts »– Se méfier de l’encapsulation sauvage

– Réfléchir aux fonctionnalités vraiment utiles• Préférer les types primitifs (int) aux objets (Integer) quand c’est possible• Accepter de recoder des choses si c’est nécessaire

– MAIS• Ne pas en profiter pour bâcler son code

Efficacité et structure correcte ne sont pas incompatibles !• Ne pas réinventer la roue en moins bien

Les algorithmes de base de l’API Java (tri, ajout, etc.) sont les meilleurs possibles

27

Documents

Xavier Tannier [email protected] Objets Java pour la RI Indexation et Recherche d'Information