Cara efisien untuk mengacak objek

20

Saya sedang menulis program untuk beberapa perangkat lunak kuis. Saya memiliki kelas pertanyaan yang berisi ArrayLists untuk pertanyaan, jawaban, opsi, tanda dan tanda negatif. Sesuatu seperti ini:

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

Saya ingin mengocok semua pertanyaan, tetapi agar pertanyaan dikocok, semua objek harus dikocok. Saya akan mendekati masalah ini dengan cara ini:

Pertama-tama, saya tidak akan menggunakan desain ini dan menggunakan String tidak ArrayList<String>mengetik sebagai variabel instan, dan kemudian akan menggunakan Collections.shufflemetode untuk mengocok objek. Tapi tim saya bersikeras desain ini.

Sekarang, kelas pertanyaan berisi ArrayLists yang semakin meningkat saat entri ke pertanyaan dibuat. Bagaimana cara mengocok pertanyaan sekarang?

java collections pengguna1369975
sumber
30
Saya benci berbicara secara absolut, tetapi jika tim Anda bersikeras pada desain ini, maka mereka salah. Memberitahu mereka! Katakan kepada mereka bahwa saya mengatakan demikian (dan saya menulisnya di Internet, jadi saya harus benar).
Joachim Sauer
10
Ya, beri tahu mereka bahwa ada banyak orang di sini yang memberi tahu Anda bahwa desain semacam ini adalah kesalahan pemula yang khas.
Doc Brown
6
Karena penasaran: apa kelebihan yang dilihat tim Anda dalam desain ini?
Joachim Sauer
9
Konvensi penamaan Java adalah CamelCase untuk nama kelas dan camelCase untuk nama variabel.
Tulains Córdova
Saya pikir Anda perlu menghadapi tim Anda tentang keputusan desain yang mengerikan ini. Jika mereka terus bersikeras, cari tahu alasannya. Jika itu hanya keras kepala, mungkin mulai berpikir tentang menemukan tim baru di masa depan yang tidak terlalu jauh. Jika mereka memiliki alasan untuk struktur ini, maka pertimbangkan alasan itu berdasarkan kemampuan mereka.
Ben Lee

Jawaban:

95

Tim Anda menderita masalah umum: penolakan objek .

Alih-alih kelas yang menyimpan satu pertanyaan dengan semua informasi yang terkait dengannya, Anda mencoba membuat kelas yang disebut questionyang menampung semua pertanyaan dalam satu contoh.

Itu cara yang salah untuk melakukannya, dan itu menyulitkan apa yang Anda coba lakukan banyak ! Mengurutkan (dan mengacak) array paralel (atau Daftar) adalah bisnis yang tidak menyenangkan dan tidak ada API umum untuk itu, hanya karena Anda biasanya ingin menghindarinya sama sekali .

Saya sarankan Anda menyusun ulang kode Anda seperti ini:

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

Dengan cara ini, mengocok pertanyaan Anda menjadi sepele (menggunakan Collections.shuffle()):

Collections.shuffle(questionList);
Joachim Sauer
sumber
39
itu bahkan bukan objek penolakan itu struktur data penolakan
jk.
22

Kamu tidak. Anda membuat daftar / antrian indeks lain dan mengacaknya. Kemudian Anda mengulangi indeks yang mendorong urutan "mengacak" koleksi Anda yang lain.

Bahkan di luar skenario Anda dengan hal-hal yang terpisah, koleksi pemesanan terpisah memberikan sejumlah manfaat (paralelisme, kecepatan ketika mengulang koleksi asli mahal, dll).

Telastyn
sumber
10
Saya enggan memilih ini: ini adalah solusi terbaik berikutnya jika desain ini memang diperbaiki, tetapi bersikeras pada desain ini sangat salah, bahwa saya tidak ingin memberikan saran tentang hal itu. (meh, tetap dipilih ;-))
Joachim Sauer
3
@ JoachimSauer - sementara saya setuju, ada banyak skenario (kurang ofensif) lainnya di mana koleksi asli harus tetap statis, sementara jalur melalui mereka perlu bervariasi.
Telastyn
4
ya saya tahu. Dan mengacak kumpulan indeks adalah pendekatan yang tepat untuk situasi tersebut. Satu-satunya ketakutan saya adalah bahwa tim OP hanya akan mengambil ini dan mengatakan "cukup baik", tanpa melihat kembali desain mereka.
Joachim Sauer
1
Jawaban ini sangat berharga terutama untuk kasus di mana seseorang tidak memiliki kebebasan untuk merevisi / mengkode ulang kelas koleksi atau struktur yang mendasarinya, misalnya kita harus puas dengan API ke koleksi yang dikelola OS. Mengocok indeks adalah wawasan yang hebat dan berdiri sendiri bahkan jika itu tidak sebanyak wawasan seperti mengulangi desain yang mendasarinya.
hardmath
@ Joachim Sauer: sebenarnya mengocok indeks belum tentu merupakan solusi terbaik untuk masalah seperti yang dinyatakan. Lihat jawaban saya untuk alternatif.
Michael Borgwardt
16

Saya setuju dengan jawaban lain bahwa solusi yang benar adalah dengan menggunakan model objek yang tepat.

Namun, sebenarnya cukup mudah untuk mengacak beberapa daftar dengan cara yang sama:

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
sumber
Itu ... cara yang rapi untuk melakukannya! Sekarang, untuk kasus "penyortiran" kita hanya perlu menemukan benih yang menghasilkan daftar diurutkan ketika diterapkan dengan cara ini dan kemudian kita mengocok semua daftar dengan benih ini!
Joachim Sauer
1
@ JoachimSauer: ya, menyortir bukan bagian dari masalah. Meskipun itu pertanyaan yang menarik apakah ada cara sistematis untuk menemukan benih untuk RNG tertentu.
Michael Borgwardt
2
@MichaelBorgwardt setelah Anda mendapatkan lebih dari 17 pertanyaan, Anda tidak bisa mengungkapkan jumlah kemungkinan pengocokan dalam 48 bit yang digunakan Java secara acak (log_2 (17!) = 48,33)
ratchet freak
@ scratchetfreak: tidak terdengar seperti masalah nyata bagi saya. Dan sepele untuk menggunakan SecureRandom sebagai gantinya jika Anda harus.
Michael Borgwardt
4
@ Telastyn: daftar indeks adalah IMO lapisan tipuan yang membuat solusi Anda lebih kompleks secara konseptual, dan apakah performanya lebih atau kurang tergantung pada seberapa sering daftar diakses setelah shuffle. Tetapi perbedaan kinerja tidak signifikan jika diberikan ukuran realistis agar kuis dijawab oleh manusia.
Michael Borgwardt
3

Buat kelas Question2:

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

Kemudian buat pemetaan fungsi a questionuntuk ArrayList<Question2>, gunakan Collection.Shuffleuntuk hasil itu, dan buat fungsi kedua untuk pemetaan ArrayList<Question2>kembali ke question.

Setelah itu, pergi ke tim Anda dan cobalah meyakinkan mereka bahwa menggunakan ArrayList<Question2>alih - alih questionakan meningkatkan banyak kode mereka, karena itu akan menghemat banyak konversi yang tidak perlu.

Doc Brown
sumber
1
Ini adalah ide yang bagus, tetapi hanya setelah upaya a-priori untuk mengubah desain telah gagal.
Sebastian Redl
@SebastianRedl: terkadang lebih mudah meyakinkan orang tentang desain yang lebih baik ketika hanya menunjukkan kepada mereka solusi dalam kode.
Doc Brown
1

Jawaban naif dan salah saya yang asli :

Cukup buat (setidaknya) nangka acak dan gantilah item n dengan item idalam loop for untuk setiap daftar yang Anda miliki.

Dalam kode semu:

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

}

Memperbarui:

Terima kasih untuk the_lotus karena menunjukkan artikel horor pengkodean. Saya merasa jauh lebih pintar sekarang :-) Pokoknya Jeff Atwood juga menunjukkan cara melakukannya dengan benar, menggunakan algoritma 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);
}

Perbedaan utama di sini adalah bahwa setiap elemen hanya ditukar sekali.

Dan sementara jawaban lain dengan benar menjelaskan bahwa model objek Anda cacat, Anda mungkin tidak berada dalam posisi untuk mengubahnya. Jadi algoritma Fisher-Yates akan menyelesaikan masalah Anda tanpa mengubah model data Anda.

codingFriend1
sumber
7
codinghorror.com/blog/2007/12/the-danger-of-naivete.html
the_lotus