Эффективный способ перемешивания объектов

20

Я пишу программу для некоторых программ викторины. У меня есть класс вопросов, содержащий ArrayLists для вопроса, ответа, опций, отметок и отрицательных отметок. Что-то вроде этого:

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

Я хочу перетасовать все вопросы, но для перетасовки вопросов необходимо перетасовать все объекты. Я бы подошел к этой проблеме следующим образом:

Прежде всего, я бы не использовал этот дизайн и не использовал ArrayList<String>тип String в качестве переменных экземпляра, а затем использовал бы Collections.shuffleметод для перемешивания объектов. Но моя команда настаивает на этом дизайне.

Теперь класс вопросов содержит растущие списки ArrayLists по мере ввода вопросов. Как перетасовать вопросы сейчас?

user1369975
источник
30
Я ненавижу говорить в абсолютах, но если ваша команда настаивает на этом дизайне, то они не правы. Скажи им! Скажите им, что я так сказал (и я написал это в Интернете, поэтому я должен быть прав).
Йоахим Зауэр
10
Да, скажите им, что здесь есть много людей, которые говорят вам, что такой дизайн - типичная ошибка начинающих.
Док Браун
6
Из любопытства: какие преимущества видит ваша команда в этом дизайне?
Иоахим Зауэр
9
Соглашения об именах Java: CamelCase для имен классов и camelCase для имен переменных.
Тулаинс Кордова
Я думаю, вам нужно противостоять вашей команде по поводу этого ужасного дизайнерского решения. Если они продолжат настаивать, выясните почему. Если это просто упрямство, возможно, начните думать о поиске новой команды в не слишком отдаленном будущем. Если у них есть причины для этой структуры, то рассмотрите эти причины по существу.
Бен Ли

Ответы:

95

Ваша команда страдает от общей проблемы: отказ объекта .

Вместо класса, который содержит один вопрос со всей информацией, связанной с ним, вы пытаетесь создать класс с именем, questionкоторый содержит все вопросы в одном экземпляре.

Это неправильный путь, и это усложняет то, что вы пытаетесь сделать много ! Сортировка (и перетасовка) параллельных массивов (или списков) - это неприятное дело, и для него нет единого API, просто потому, что вы обычно этого вообще избегаете .

Я предлагаю вам реструктурировать свой код следующим образом:

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

Таким образом, перетасовка вашего вопроса становится тривиальной (использование Collections.shuffle()):

Collections.shuffle(questionList);
Йоахим Зауэр
источник
39
это даже не отрицание объекта, это отрицание структуры данных
jk.
22

Вы не Вы создаете другой список / очередь индексов и перемешиваете это. Затем вы перебираете индексы, которые управляют «перемешанным» порядком ваших других коллекций.

Даже за пределами вашего сценария с разделенными вещами отдельный сбор заказов обеспечивает ряд преимуществ (параллелизм, скорость переустановки исходного набора дорогостоящая и т. Д.).

Telastyn
источник
10
Я не хочу голосовать за это: это следующее лучшее решение, если этот дизайн действительно исправлен, но настаивать на этом проекте настолько неправильно, что я не хотел бы давать какие-либо предложения по этому поводу. (Мех, все равно проголосовал ;-))
Йоахим Зауэр
3
@joachimSauer - хотя я согласен, есть много других (менее оскорбительных) сценариев, в которых исходная коллекция должна оставаться статичной, в то время как путь через них должен изменяться.
Теластин
4
Да, я знаю. И перетасовывание набора индексов является правильным подходом для таких ситуаций. Я единственно боюсь, что команда OP просто возьмется за это и скажет «достаточно хорошо», не пересматривая их дизайн.
Иоахим Зауэр
1
Этот ответ особенно важен для случая, когда у человека нет свободы пересматривать / перекодировать базовый класс или структуру коллекции, например, нужно обойтись API-интерфейсом для поддерживаемой ОС коллекции. Перетасовка индексов является отличным пониманием и стоит сама по себе, даже если она не настолько проницательна, как переделка основного дизайна.
hardmath
@Joachim Sauer: перетасовка индексов не обязательно является лучшим решением проблемы, как указано. Смотрите мой ответ для альтернативы.
Майкл Боргвардт
16

Я согласен с другими ответами, что правильное решение состоит в том, чтобы использовать правильную объектную модель.

Однако на самом деле довольно легко перетасовать несколько списков одинаковым образом:

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);
...
Майкл Боргвардт
источник
Это ... отличный способ сделать это! Теперь для случая «сортировки» нам просто нужно найти начальное число, которое при таком способе создает отсортированный список, а затем мы перемешиваем все списки с этим начальным числом!
Йоахим Зауэр
1
@JoachimSauer: ну, сортировка не была частью проблемы. Хотя это интересный вопрос, существует ли системный способ найти такое семя для данного RNG.
Майкл Боргвардт
2
@MichaelBorgwardt, как только вы получите более 17 вопросов, вы просто не сможете выразить количество возможных перемешиваний в 48 битах, которые использует java Random (log_2 (17!) = 48.33)
урод
@ratchetfreak: не похоже на настоящую проблему для меня. И вместо этого тривиально использовать SecureRandom, если необходимо.
Майкл Боргвардт
4
@Telastyn: список индексов - это IMO - уровень косвенности, который делает ваше решение концептуально более сложным, и то, насколько оно более или менее эффективно, зависит от того, как часто к спискам обращаются после случайного воспроизведения. Но различия в производительности были бы незначительными, учитывая реалистичные размеры, чтобы люди могли ответить на вопрос.
Майкл Боргвардт
3

Создать класс Question2:

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

Затем создайте функцию отображения а questionдля ArrayList<Question2>, использования Collection.Shuffleдля этого результата, и создать вторую функцию для отображения ArrayList<Question2>обратно в question.

После этого обратитесь к своей команде и попытайтесь убедить их, что использование ArrayList<Question2>вместо этого значительно questionулучшит их код, поскольку это избавит их от многих ненужных преобразований.

Док Браун
источник
1
Это хорошая идея, но только после неудачных попыток изменить дизайн.
Себастьян Редл
@SebastianRedl: иногда легче убедить людей в лучшем дизайне, просто показывая им решение в коде.
Док Браун
1

Мой оригинальный наивный и неправильный ответ:

Просто создайте (как минимум) nслучайные числа и поменяйте элемент n с элементом iв цикле for для каждого вашего списка.

В псевдокоде:

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

}

Обновить:

Спасибо за the_lotus за указание на статью об ужасах кодирования. Теперь я чувствую себя намного умнее :-) В любом случае, Джефф Этвуд также показывает, как это сделать правильно, используя алгоритм Фишера-Йейтса :

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

Основное отличие здесь заключается в том, что каждый элемент заменяется только один раз.

И хотя другие ответы правильно объясняют, что ваша объектная модель имеет недостатки, вы не можете быть в состоянии изменить ее. Таким образом, алгоритм Фишера-Йейтса решит вашу проблему без изменения модели данных.

codingFriend1
источник