Skuteczny sposób tasowania obiektów

20

Piszę program do jakiegoś oprogramowania quizowego. Mam klasę pytań zawierającą ArrayLists dla pytania, odpowiedzi, opcji, znaków i znaków ujemnych. Coś takiego:

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

Chcę tasować wszystkie pytania, ale aby pytania były tasowane, wszystkie obiekty muszą być tasowane. Podszedłbym do tego problemu w następujący sposób:

Po pierwsze, nie użyłbym tego projektu i nie używałbym String ArrayList<String>jako zmiennych instancji, a następnie użyłbym Collections.shufflemetody do losowego przesyłania obiektów. Ale mój zespół nalega na ten projekt.

Teraz klasa pytań zawiera coraz większą liczbę ArrayLists w miarę wprowadzania danych do pytań. Jak teraz tasować pytania?

użytkownik1369975
źródło
30
Nienawidzę mówić absolutnie, ale jeśli twój zespół nalega na ten projekt, to są w błędzie. Powiedz im! Powiedz im, że tak powiedziałem (i napisałem to w Internecie, więc muszę mieć rację).
Joachim Sauer
10
Tak, powiedz im, że jest tu wiele osób, które mówią, że ten rodzaj projektu jest typowym błędem dla początkujących.
Doc Brown
6
Z ciekawości: jakie zalety widzi Twój zespół w tym projekcie?
Joachim Sauer
9
Konwencje nazewnictwa Java to CamelCase dla nazw klas i camelCase dla nazw zmiennych.
Tulains Córdova
Myślę, że musisz skonfrontować swój zespół z tą okropną decyzją projektową. Jeśli nadal nalegają, dowiedz się, dlaczego. Jeśli to tylko upór, być może zacznij myśleć o znalezieniu nowego zespołu w niezbyt odległej przyszłości. Jeśli mają powody dla takiej struktury, rozważ je z racji swoich zalet.
Ben Lee,

Odpowiedzi:

95

Twój zespół ma typowy problem: odmowa obiektu .

Zamiast klasy, która zawiera jedno pytanie ze wszystkimi powiązanymi z nią informacjami, próbujesz utworzyć klasę o nazwie, questionktóra zawiera wszystkie pytania w jednym wystąpieniu.

To zły sposób, aby to zrobić i komplikuje to, co próbujesz zrobić dużo ! Sortowanie (i tasowanie) równoległych tablic (lub list) to paskudna sprawa i nie ma dla nich wspólnego API, po prostu dlatego, że zwykle w ogóle chcesz tego uniknąć .

Sugeruję restrukturyzację kodu w następujący sposób:

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

W ten sposób tasowanie pytania staje się banalne (używanie Collections.shuffle()):

Collections.shuffle(questionList);
Joachim Sauer
źródło
39
nawet nie jest to odmowa obiektowa, to odmowa struktury danych
jk.
22

Ty nie. Tworzysz kolejną listę / kolejkę indeksów i przetasujesz ją. Następnie iterujesz w dół indeksy, które określają kolejność „przetasowania” innych kolekcji.

Nawet poza scenariuszem, w którym rzeczy są rozdzielone, oddzielna kolekcja zamawiania zapewnia szereg korzyści (równoległość, szybkość ponownego umieszczania oryginalnej kolekcji jest kosztowna itp.).

Telastyn
źródło
10
Niechętnie głosuję nad tym: jest to najlepsze rozwiązanie, jeśli ten projekt jest rzeczywiście naprawiony, ale naleganie na ten projekt jest tak błędne, że nie chciałbym dawać żadnych sugestii na jego temat. (meh, mimo to głosowano ;-))
Joachim Sauer
3
@joachimSauer - choć się zgadzam, istnieje wiele innych (mniej ofensywnych) scenariuszy, w których oryginalna kolekcja musi pozostać statyczna, a ścieżka przez nie musi się różnić.
Telastyn
4
tak, wiem. A przetasowanie kolekcji wskaźników jest właściwym podejściem do takich sytuacji. Obawiam się tylko, że zespół PO po prostu weźmie to i powie „wystarczająco dobry”, bez ponownego przeglądania ich projektu.
Joachim Sauer
1
Ta odpowiedź jest cenna szczególnie w przypadku, gdy nie ma się możliwości zmiany / przekodowania podstawowej klasy lub struktury kolekcji, np. Trzeba zadowolić się interfejsem API do kolekcji utrzymywanej przez system operacyjny. Tasowanie indeksów jest świetnym wglądem i pozostaje samo w sobie, nawet jeśli nie jest tak wnikliwe, jak ponowne opracowanie podstawowego projektu.
hardmath
@Jachachim Sauer: tasowanie indeksów niekoniecznie jest najlepszym rozwiązaniem problemu, jak stwierdzono. Zobacz moją odpowiedź na alternatywę.
Michael Borgwardt
16

Zgadzam się z innymi odpowiedziami, że poprawnym rozwiązaniem jest użycie odpowiedniego modelu obiektowego.

W rzeczywistości jednak dość łatwo jest tasować wiele list w identyczny sposób:

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
źródło
To ... fajny sposób na zrobienie tego! Teraz w przypadku „sortowania” musimy tylko znaleźć ziarno, które po zastosowaniu w ten sposób tworzy posortowaną listę, a następnie tasujemy wszystkie listy z tym ziarnem!
Joachim Sauer
1
@JachachimSauer: sortowanie nie było częścią problemu. Chociaż interesujące jest pytanie, czy istnieje systematyczny sposób na znalezienie takiego ziarna dla danego RNG.
Michael Borgwardt
2
@MichaelBorgwardt, gdy masz ponad 17 pytań, po prostu nie możesz wyrazić ilości możliwych przetasowań w 48 bitach, których używa java Losowo (log_2 (17!) = 48,33)
maniak zapadkowy
@ratchetfreak: nie brzmi dla mnie jak prawdziwy problem. Jeśli to konieczne, używanie SecureRandom jest banalne.
Michael Borgwardt
4
@Telastyn: lista indeksów to IMO warstwa pośrednia, która sprawia, że ​​twoje rozwiązanie jest bardziej złożone koncepcyjnie, a to, czy jest ono bardziej lub mniej wydajne, zależy od częstotliwości dostępu do list po tasowaniu. Jednak różnice w wydajności byłyby nieznaczne, biorąc pod uwagę realistyczne rozmiary quizu, na który odpowiedzieliby ludzie.
Michael Borgwardt
3

Utwórz klasę Question2 :

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

Następnie utwórz funkcję odwzorowującą questionna ArrayList<Question2>, użyjCollection.Shuffle dla tego wyniku i utwórz drugą funkcję do odwzorowania z ArrayList<Question2>powrotem question.

Następnie idź do swojego zespołu i spróbuj przekonać ich, że użycie ArrayList<Question2>zamiast zamiast questionznacznie poprawiłoby ich kod, ponieważ zaoszczędziłoby im to wiele niepotrzebnych konwersji.

Doktor Brown
źródło
1
To dobry pomysł, ale dopiero po niepowodzeniu prób zmiany projektu z góry.
Sebastian Redl
@SebastianRedl: czasem łatwiej jest przekonać ludzi do lepszego projektu, pokazując im rozwiązanie w kodzie.
Doc Brown
1

Moja oryginalna naiwna i zła odpowiedź:

Po prostu utwórz (przynajmniej) nliczby losowe i zamień przedmiot na n przedmioti w pętli for dla każdej listy, którą masz.

W pseudokodzie:

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

}

Aktualizacja:

Dzięki za the_lotus za wskazanie artykułu o horrorze kodowania. Teraz czuję się znacznie mądrzejszy :-) W każdym razie Jeff Atwood pokazuje również, jak to zrobić dobrze, używając algorytmu 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);
}

Główną różnicą jest to, że każdy element jest zamieniany tylko raz.

I podczas gdy inne odpowiedzi poprawnie wyjaśniają, że twój model obiektowy jest wadliwy, możesz nie być w pozycji, aby go zmienić. Tak więc algorytm Fisher-Yates rozwiązałby twój problem bez zmiany modelu danych.

codingFriend1
źródło