Un moyen efficace de mélanger les objets

20

J'écris un programme pour un logiciel de quiz. J'ai une classe de questions contenant les ArrayLists pour la question, la réponse, les options, les notes et les notes négatives. Quelque chose comme ça:

class question
{
    private ArrayList<Integer> index_list;
    private ArrayList<String> question_list;        
    private ArrayList<String> answer_list;      
    private ArrayList<String> opt1_list;        
    private ArrayList<String> opt2_list;    
}

Je veux mélanger toutes les questions, mais pour que les questions soient mélangées, tous les objets doivent être mélangés. J'aurais abordé ce problème de cette façon:

Tout d'abord, je n'aurais pas utilisé cette conception et utilisé String ne pas ArrayList<String>taper comme variables d'instance, et j'aurais ensuite utilisé la Collections.shuffleméthode pour mélanger les objets. Mais mon équipe insiste sur cette conception.

Maintenant, la classe de questions contient des listes de tableaux croissantes à mesure que l'entrée des questions est effectuée. Comment mélanger les questions maintenant?

user1369975
la source
30
Je déteste parler absolu, mais si votre équipe insiste sur cette conception, alors ils ont tort. Dis leur! Dites-leur que je l'ai dit (et je l'ai écrit sur Internet, je dois donc avoir raison).
Joachim Sauer
10
Oui, dites-leur qu'il y a beaucoup de gens ici qui vous disent que ce type de design est une erreur typique des débutants.
Doc Brown
6
Par curiosité: quels avantages votre équipe voit-elle dans cette conception?
Joachim Sauer
9
Les conventions de dénomination Java sont CamelCase pour les noms de classe et camelCase pour les noms de variable.
Tulains Córdova
Je pense que vous devez confronter votre équipe à cette terrible décision de conception. S'ils continuent d'insister, découvrez pourquoi. Si c'est juste de l'entêtement, commencez peut-être à penser à trouver une nouvelle équipe dans un avenir pas trop lointain. S'ils ont des raisons pour cette structure, alors considérez ces raisons selon leurs mérites.
Ben Lee

Réponses:

95

Votre équipe souffre d'un problème commun: le déni d'objet .

Au lieu d'une classe qui contient une seule question avec toutes les informations qui lui sont associées, vous essayez de créer une classe appelée questionqui contient toutes les questions dans une seule instance.

C'est la mauvaise façon de procéder et cela complique ce que vous essayez de faire beaucoup ! Trier (et mélanger) des tableaux (ou des listes) parallèles est une tâche délicate et il n'y a pas d'API commune pour cela, simplement parce que vous voulez généralement l'éviter du tout .

Je vous suggère de restructurer votre code comme ceci:

class Question
{
    private Integer index;
    private String question;        
    private String answer;      
    private String opt1;        
    private String opt2;    
}

// somewhere else
List<Question> questionList = new ArrayList<Question>();

De cette façon, mélanger votre question devient trivial (en utilisant Collections.shuffle()):

Collections.shuffle(questionList);
Joachim Sauer
la source
39
ce n'est même pas un déni d'objet, c'est un déni de structure de données
jk.
22

Non. Vous créez une autre liste / file d'attente d'index et mélangez cela. Ensuite, vous parcourez les index qui déterminent l'ordre "mélangé" de vos autres collections.

Même en dehors de votre scénario avec des éléments séparés, la collecte de commande séparée offre un certain nombre d'avantages (le parallélisme, la vitesse lors de la réinstallation de la collection d'origine est coûteux, etc.).

Telastyn
la source
10
Je suis réticent à voter cela: c'est la meilleure solution suivante si ce design est en effet corrigé, mais insister sur ce design est si mauvais, que je ne voudrais pas donner de suggestions à ce sujet. (meh, voté quand même ;-))
Joachim Sauer
3
@joachimSauer - même si je suis d'accord, il existe de nombreux autres scénarios (moins offensants) où la collection d'origine doit rester statique tandis que le chemin à travers eux doit varier.
Telastyn
4
Oui je sais. Et mélanger une collection d'indices est la bonne approche pour ces situations. Ma seule crainte est que l'équipe des OP ne prenne cela et dise "assez bien", sans revoir leur conception.
Joachim Sauer
1
Cette réponse est particulièrement utile dans le cas où l'on n'a pas la liberté de réviser / recoder la classe ou la structure de collection sous-jacente, par exemple, il faut se contenter d'une API pour une collection maintenue par le système d'exploitation. Mélanger les indices est un excellent aperçu et se tient tout seul, même si ce n'est pas aussi clair que de refaire la conception sous-jacente.
hardmath
@Joachim Sauer: le fait de mélanger les indices n'est pas nécessairement la meilleure solution au problème comme indiqué. Voir ma réponse pour une alternative.
Michael Borgwardt
16

Je suis d'accord avec les autres réponses que la bonne solution consiste à utiliser un modèle d'objet approprié.

Cependant, il est en fait assez facile de mélanger plusieurs listes de manière identique:

Random rnd = new Random();
long seed = rnd.nextLong();

rnd.setSeed(seed);
Collections.shuffle(index_list, rnd);
rnd.setSeed(seed);
Collections.shuffle(question_list, rnd);
rnd.setSeed(seed);
Collections.shuffle(answer_list, rnd);
...
Michael Borgwardt
la source
C'est ... une bonne façon de le faire! Maintenant, pour le cas de "tri", nous avons juste besoin de trouver une graine qui produit une liste triée lorsqu'elle est appliquée de cette façon, puis nous mélangeons toutes les listes avec cette graine!
Joachim Sauer
1
@JoachimSauer: eh bien, le tri ne faisait pas partie du problème. Bien qu'il soit intéressant de savoir s'il existe un moyen systématique de trouver une telle graine pour un RNG donné.
Michael Borgwardt,
2
@MichaelBorgwardt une fois que vous avez obtenu plus de 17 questions, vous ne pouvez tout simplement pas exprimer la quantité de shuffles possibles dans les 48 bits que Java Random utilise (log_2 (17!) = 48.33)
ratchet freak
@ratchetfreak: cela ne me semble pas être un vrai problème. Et il est trivial d'utiliser SecureRandom à la place si vous le devez.
Michael Borgwardt,
4
@Telastyn: la liste des index est IMO une couche d'indirection qui rend votre solution conceptuellement plus complexe, et si elle est plus ou moins performante dépend de la fréquence d'accès aux listes après le shuffle. Mais les différences de performances seraient insignifiantes étant donné les tailles réalistes pour un questionnaire auquel les humains devraient répondre.
Michael Borgwardt,
3

Créer une classe Question2 :

class Question2
{
    public Integer index_list;
    public String question_list;        
    public String answer_list;      
    public String opt1_list;        
    public String opt2_list;    
}

Créez ensuite une fonction mappant a questionà ArrayList<Question2>, utilisezCollection.Shuffle pour ce résultat et créez une deuxième fonction pour mapper ArrayList<Question2>vers question.

Ensuite, allez voir votre équipe et essayez de les convaincre que l'utilisation d'un ArrayList<Question2>au lieu de questionaméliorerait beaucoup leur code, car cela leur permettrait d'économiser beaucoup de conversions inutiles.

Doc Brown
la source
1
C'est une bonne idée, mais seulement après l'échec des tentatives de modification de la conception a priori.
Sebastian Redl
@SebastianRedl: il est parfois plus facile de convaincre les gens d'une meilleure conception en leur montrant simplement la solution en code.
Doc Brown
1

Ma réponse naïve et fausse d'origine :

Créez simplement (au moins) ndes nombres aléatoires et échangez l'élément n avec l'élément idans une boucle for pour chaque liste que vous avez.

En pseudo code:

for (in i = 0; i < question_list.length(); i++) {
  int random = randomNumber(0, questions_list.length()-1);
  question_list.switchItems(i, random);
  answer_list.switchItems(i, random);
  opt1_list.switchItems(i, random);
  opt2_list.switchItems(i, random);

}

Mise à jour:

Merci pour the_lotus d'avoir signalé l'article d'horreur sur le codage. Je me sens beaucoup plus intelligent maintenant :-) Quoi qu'il en soit, Jeff Atwood montre également comment le faire correctement, en utilisant l' algorithme Fisher-Yates :

for (int i = question_list.Length - 1; i > 0; i--){
  int n = rand.Next(i + 1); //assuming rand.Next(x) returns values between 0 and x-1
  question_list.switchItems(i, n);
  answer_list.switchItems(i, n);
  opt1_list.switchItems(i, n);
  opt2_list.switchItems(i, n);
}

La principale différence ici est que chaque élément n'est échangé qu'une seule fois.

Et tandis que les autres réponses expliquent correctement que votre modèle d'objet est défectueux, vous pourriez ne pas être en mesure de le changer. Ainsi, l'algorithme Fisher-Yates résoudrait votre problème sans changer votre modèle de données.

codingFriend1
la source