Structure de données efficace pour comparer les éléments avec les attributs les plus courants

Question

J'ai besoin d'une suggestion pour une structure de données efficace pour le problème suivant.

J'ai deux listes d'étudiants (hommes et femmes) avec leurs classes respectives (triées par date) qu'ils ont déjà prises. La liste est déjà alphabétisée avec leur nom, prénom.

Un utilisateur donnera un nom d'étudiant, c.-à-d. L'étudiant X, et ce que le programme doit faire est de trouver quel étudiant partage le plus de classes avec l'étudiant X.

Answer 1

Il semble que vous ayez besoin de Associative Arrays. Un tableau associatif mappe un objet clé d'un certain type à un autre objet, éventuellement d'un type différent. Il est souvent juste appelé une "carte" puisque c'est ce qu'il fait. Une carte peut être implémentée par un Hash Table, ce qui veut dire que vous avez constamment le temps de chercher vos clés -> mappages d'objets. Je suggère deux tables de hachage pour ce problème. Le premier à mapper les noms des élèves à des listes de classes prises. La seconde pour mapper les noms de classe aux élèves qui ont suivi le cours. Vos recherches étudiant -> cours seront très rapides, et votre recherche de classe -> étudiant sera rapide aussi. En outre, lorsque vous traitez un élève particulier X, vous pouvez en utiliser un troisième pour mapper un nom d'étudiant en nombre entier, en comptant combien de fois il a partagé un cours avec l'élève X. Cela finira par être une mise en œuvre assez efficace.

Mieux encore, cela peut s'avérer être une implémentation très simple. Le mappage relationnel est une tâche si courante et les tableaux associatifs sont si utiles que de nombreuses langues les ont intégrés ou dans la bibliothèque standard. Python a son dictionnaire, Perl a son hash, Java a un HashMap (et beaucoup d'autres types de cartes), C++ a std :: map, bien que cela ne soit pas supporté par une table de hachage et n'a pas d'accès constant. À moins que vous ne soyez interdit d'utiliser la bibliothèque standard de votre langue pour cet exercice, vous ne devriez pas avoir trop de difficulté à faire fonctionner une solution efficace.

Answer 2

je ferais ceci:

class Clazz { 
    Date when; 
    String name; 
} 
class Student { 
    boolean isFemale; 
    String name; 
    Map<Date, Clazz> classesTaken; 
} 
List<Student> students = ... 

public Student findMostShared(Student who) { 
    Student max = null; 
    int maxCount = 0; 
    for (Student s : students) { 
     if (s == who) { continue; } 
     int c = 0; 
     for (Clazz z : s.classesTaken.values()) { 
      if (who.classesTaken.containsKey(z.when)) { 
       c++; 
      } 
     } 
     if (c > maxCount) { 
      maxCount = c; 
      max = s; 
     } 
    } 
    return max; 
}