Effiziente Methode zum Mischen von Objekten

20

Ich schreibe ein Programm für eine Quizsoftware. Ich habe eine Frageklasse, die die ArrayLists für die Frage, die Antwort, die Optionen, die Marken und die negativen Marken enthält. Etwas wie das:

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;    
}

Ich möchte alle Fragen mischen, aber damit Fragen gemischt werden, müssen alle Objekte gemischt werden. Ich hätte dieses Problem folgendermaßen angegangen:

Zunächst hätte ich dieses Design nicht verwendet und String nicht ArrayList<String>als Instanzvariablen verwendet und dann die Collections.shuffleMethode zum Mischen von Objekten verwendet. Aber mein Team besteht auf diesem Entwurf.

Jetzt enthält die Fragenklasse zunehmende ArrayLists, wenn der Eintrag zu den Fragen vorgenommen wird. Wie mische ich die Fragen jetzt?

user1369975
quelle
30
Ich hasse es, absolut zu reden, aber wenn Ihr Team auf diesem Entwurf besteht, dann liegen sie falsch. Erzähl es ihnen! Sagen Sie ihnen, dass ich es gesagt habe (und ich habe es im Internet geschrieben, also muss ich recht haben).
Joachim Sauer
10
Ja, sagen Sie ihnen, dass viele Leute Ihnen sagen, dass diese Art von Design ein typischer Anfängerfehler ist.
Doc Brown
6
Aus Neugier: Welche Vorteile sieht Ihr Team in diesem Design?
Joachim Sauer
9
Java-Namenskonventionen sind CamelCase für Klassennamen und camelCase für Variablennamen.
Tulains Córdova
Ich denke, Sie müssen Ihr Team mit dieser schrecklichen Designentscheidung konfrontieren. Wenn sie weiterhin darauf bestehen, finden Sie heraus, warum. Wenn es nur Sturheit ist, überlegen Sie sich vielleicht, in nicht allzu ferner Zukunft ein neues Team zu finden. Wenn sie Gründe für diese Struktur haben, sollten Sie diese Gründe für sich in Betracht ziehen.
Ben Lee

Antworten:

95

Ihr Team leidet unter einem allgemeinen Problem: der Verweigerung von Objekten .

Anstelle einer Klasse, die eine einzelne Frage mit allen damit verbundenen Informationen enthält, versuchen Sie, eine Klasse mit dem Namen zu erstellen question, die alle Fragen in einer einzelnen Instanz enthält.

Das ist der falsche Weg, und es erschwert, was Sie versuchen, viel zu tun ! Parallele Arrays (oder Listen) zu sortieren (und zu mischen) ist eine unangenehme Angelegenheit und es gibt keine gemeinsame API dafür, einfach weil Sie es normalerweise überhaupt vermeiden wollen .

Ich schlage vor, Sie strukturieren Ihren Code folgendermaßen um:

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>();

Auf diese Weise wird das Mischen Ihrer Frage trivial (mit Collections.shuffle()):

Collections.shuffle(questionList);
Joachim Sauer
quelle
39
es ist nicht einmal Objektverweigerung, es ist Datenstrukturverweigerung
jk.
22

Das tust du nicht. Sie erstellen eine weitere Liste / Warteschlange von Indizes und mischen diese. Dann durchlaufen Sie die Indizes, die die Reihenfolge Ihrer anderen Sammlungen bestimmen.

Auch außerhalb Ihres Szenarios mit getrennten Bereichen bietet die separate Bestellsammlung eine Reihe von Vorteilen (Parallelität, Geschwindigkeit beim Wiedereinsetzen der ursprünglichen Sammlung sind kostspielig usw.).

Telastyn
quelle
10
Ich zögere es, darüber abzustimmen: Es ist die nächstbeste Lösung, wenn dieses Design zwar repariert ist, aber darauf zu bestehen, ist so falsch, dass ich keine Vorschläge dazu machen möchte. (meh, trotzdem aufgestimmt ;-))
Joachim Sauer
3
@joachimSauer - obwohl ich zustimme, gibt es viele andere (weniger anstößige) Szenarien, in denen die ursprüngliche Sammlung statisch bleiben muss, während der Pfad durch sie variieren muss.
Telastyn
4
Ja, ich weiß. Und das Mischen einer Sammlung von Indizes ist der richtige Ansatz für diese Situationen. Meine einzige Befürchtung ist, dass das OP-Team dies einfach aufgreift und "gut genug" sagt, ohne das Design erneut zu überprüfen.
Joachim Sauer
1
Diese Antwort ist besonders für den Fall nützlich, dass man nicht die Freiheit hat, die zugrunde liegende Auflistungsklasse oder -struktur zu überarbeiten / neu zu kodieren, z. Das Mischen der Indizes ist eine großartige Erkenntnis und steht für sich selbst, auch wenn es nicht so einsichtig ist wie das Wiederherstellen des zugrunde liegenden Designs.
Hardmath
@Joachim Sauer: Eigentlich ist das Mischen der Indizes nicht unbedingt die beste Lösung für das angegebene Problem. Siehe meine Antwort für eine Alternative.
Michael Borgwardt
16

Ich stimme den anderen Antworten zu, dass die richtige Lösung darin besteht, ein geeignetes Objektmodell zu verwenden.

Es ist jedoch recht einfach, mehrere Listen auf dieselbe Weise zu mischen:

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
quelle
Das ist ... ein guter Weg, es zu tun! Für den Fall "Sortieren" müssen wir nur einen Startwert finden, der eine sortierte Liste erzeugt, wenn er auf diese Weise angewendet wird, und dann mischen wir alle Listen mit diesem Startwert!
Joachim Sauer
1
@JoachimSauer: na ja, sortieren war nicht Teil des Problems. Obwohl es eine interessante Frage ist, ob es einen systematischen Weg gibt, einen solchen Samen für ein bestimmtes RNG zu finden.
Michael Borgwardt
2
@MichaelBorgwardt Sobald Sie über 17 Fragen haben, können Sie einfach nicht die Menge der möglichen Mischvorgänge in den 48 Bits ausdrücken, die der Java-Zufall verwendet (log_2 (17!) = 48.33)
Ratschenfreak
@ratchetfreak: hört sich für mich nicht nach einem echten Problem an. Und es ist trivial, stattdessen SecureRandom zu verwenden, wenn Sie müssen.
Michael Borgwardt
4
@Telastyn: Die Liste der Indizes ist IMO eine Indirektionsebene, die Ihre Lösung konzeptionell komplexer macht. Ob sie mehr oder weniger performant ist, hängt davon ab, wie oft nach dem Shuffle auf die Listen zugegriffen wird. Bei realistischen Größen für ein Quiz, das von Menschen beantwortet werden soll, wären Leistungsunterschiede jedoch unbedeutend.
Michael Borgwardt
3

Erstelle eine Klasse Question2:

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

Erstellen Sie dann eine Funktion, die ein questionto zuordnet ArrayList<Question2>, verwenden Sie Collection.Shufflefür dieses Ergebnis und erstellen Sie eine zweite Funktion für die Zuordnung ArrayList<Question2>zurück zu question.

Gehen Sie anschließend zu Ihrem Team und versuchen Sie, sie davon zu überzeugen, dass die Verwendung von a ArrayList<Question2>statt questionden Code erheblich verbessern würde, da sie dadurch eine Menge unnötiger Konvertierungen einsparen würden.

Doc Brown
quelle
1
Dies ist eine gute Idee, aber erst nachdem A-priori-Versuche, das Design zu ändern, fehlgeschlagen sind.
Sebastian Redl
@SebastianRedl: Manchmal ist es einfacher, Leute von einem besseren Design zu überzeugen, wenn man ihnen nur die Lösung im Code zeigt.
Doc Brown
1

Meine ursprüngliche naive und falsche Antwort:

Erstellen Sie einfach (mindestens) nZufallszahlen und tauschen Sie Artikel n mit Artikeln iin einer for-Schleife für jede Liste aus, die Sie haben.

Im Pseudocode:

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);

}

Aktualisieren:

Vielen Dank für den Hinweis auf den Horror-Artikel. Ich fühle mich jetzt viel schlauer :-) Wie auch immer, Jeff Atwood zeigt auch, wie man es richtig macht, indem er den Fisher-Yates-Algorithmus verwendet :

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);
}

Der Hauptunterschied besteht darin, dass jedes Element nur einmal ausgetauscht wird.

Und während die anderen Antworten korrekt erklären, dass Ihr Objektmodell fehlerhaft ist, sind Sie möglicherweise nicht in der Lage, es zu ändern. Der Fisher-Yates-Algorithmus würde also Ihr Problem lösen, ohne Ihr Datenmodell zu ändern.

codingFriend1
quelle