Expérimentation avec hachage coucou

Suppression impatiente

Notez que dans le code pour suppression impatiente, on réinsère les éléments après la case vidée (et non pas à partir de la première case identifiée à l’indice i=h(x).) Voir correction en Ligne S1 dans l’énoncé: devoir4.

Quant à la date de remise, vous ne serez pas pénalisé si vous soumettez avant le 17 novembre 20:15 (donc, avec un délai ≤ 72h).

Exemple avec hachage coucou

Pour illustrer ce qu’on veut faire en Devoir 4, voici mon expérimentation avec hachage coucou. C’est une structure très élégante, avec O(1) temps au pire pour recherche et suppression. Rasmus Pagh donne une bonne présentation en ligne sur l’idée.

  1. J’ai encodé la méthode dans la classe koekoeke.CuckooHashingSet:https://github.com/csurosm/Koekoeke/blob/master/src/koekoeke/CuckooHashingSet.java. La classe implémente l’interface de java.util.Set.
  2. J’ai modifié la source de SetTester pour utiliser CuckooHashingSet. En Ligne 480:
    Set<Object> trythis =  new koekoeke.CuckooHashingSet(); 
    
  3. J’ai lancé l’exécution après compilation dans la ligne de commande, 12 fois par taille testée:
    % bash -c 'for N in 65536 131072 262144 524288 1048576 2097152 4194304; do for rep in 1 2 3 4 5 6 7 8 9 10 11 12; do  java -Xmx2G -cp IFT2015-A16.jar SetTester ${N}; done; done' > timings.log 
    
  4. Afin d’importer les données dans un logiciel de feuille de calcul (Microsoft Excel ou Google Sheets), j’ai enlevé les lignes de remarques. (Dans la feuille, j’ai trié les rangées par les colonnes `Phase’ et ‘size’.)
    % grep -v '#' timings.log > timings.txt      
    
  5. J’ai répeté la procédure pour HashSet. Voici la combinaison des deux fichiers (avec 25 répétitions au lieu de 12):  Google spreadsheet. (Temps amorti rapporté dans phase `exec’, usage de mémoire dans phase `final’.)

cuckoo-timingscuckoo-memory

Publicités

Devoir 3

Dans Devoir 3, on vérifie le paradoxe des anniversaires. Il s’agit de compiler la liste de joueurs sur un équipe de sport de votre préférence et compter les jumeaux astrologiques. (On attend que >50% des équipes de >23 joueurs ont des jumeaux astrologiques.)

Énoncé: devoir3. Notez que la soumission est par commentaire à ce message (non-anonyme, bien sûr!).

Mes disponibilités pour la semaine: mardi 11 octobre, 11-12:30 et jeudi 13 octobre, 10-11. Envoyez-moi un email pour autres temps.

Bonne fête à tout le monde!

 

 

 

Indice: programmation en Devoir 2

Voici mes conseils pour développer votre code en 2.2:

  1.  Il faut choisir une représentation pour le côté droit des règles: cela peut être simplement une String (« FF-F ») ou bien vous pouvez introduire une classe dont les instances correspondent aux symboles de l’alphabet, et utiliser votre propre tableau ou liste chaînée pour encoder la chaîne à la droite.
  2. Il faut recueillir les règles alternatives pour la réécriture du même symbole. Servez-vous des classes prédéfinies en java.util ou implantez votre propre structure de données. Par exemple, on peut utiliser un dictionnaire de listes:
        Map<String, List<String>> rewriting_rules = new HashMap<>(); 
    

    Pour stocker la règle F→FF-F, on utilise « F » comme clé, et on ajoute « FF-F » sur la liste associée. Quand on écrit la sortie, il faut définir un opérateur pour chaque règle applicable à un symbole, en parcourant la liste. Consultez l’exemple (lindenmayer.eps) pour identifier les pièces de code PS à écrire pour les caractères individuels dans la chaîne (comme gsave pour « [ » ou L:d T:draw pour « F » [avancer et dessiner]).