Manera eficiente de barajar objetos

20

Estoy escribiendo un programa para algún software de prueba. Tengo una clase de pregunta que contiene las ArrayLists para la pregunta, respuesta, opciones, marcas y marcas negativas. Algo como esto:

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

Quiero barajar todas las preguntas, pero para que las preguntas se barajen, todos los objetos deben barajarse. Hubiera abordado este problema de esta manera:

En primer lugar, no habría usado este diseño y no usaría String ArrayList<String>como tipo de variables de instancia, y luego habría usado el Collections.shufflemétodo para barajar objetos. Pero mi equipo insiste en este diseño.

Ahora, la clase de preguntas contiene ArrayLists crecientes a medida que se realiza la entrada a las preguntas. ¿Cómo barajar las preguntas ahora?

usuario1369975
fuente
30
Odio hablar en absoluto, pero si su equipo insiste en este diseño, entonces están equivocados. ¡Dígales! Dígales que lo dije (y lo escribí en Internet, así que tengo que estar en lo cierto).
Joachim Sauer
10
Sí, diles que hay mucha gente aquí que te dice que este tipo de diseño es un error típico de principiantes.
Doc Brown
66
Por curiosidad: ¿qué ventajas ve su equipo en este diseño?
Joachim Sauer
99
Las convenciones de nomenclatura de Java son CamelCase para nombres de clase y camelCase para nombres de variables.
Tulains Córdova
Creo que debes confrontar a tu equipo sobre esta terrible decisión de diseño. Si continúan insistiendo, averigüe por qué. Si se trata solo de terquedad, tal vez comience a pensar en encontrar un nuevo equipo en un futuro no muy lejano. Si tienen razones para esta estructura, considere esas razones según sus méritos.
Ben Lee

Respuestas:

95

Su equipo sufre un problema común: la negación de objetos .

En lugar de una clase que contenga una sola pregunta con toda la información asociada, intente crear una clase llamada questionque contenga todas las preguntas en una sola instancia.

Esa es la manera equivocada de ella, y complica lo que intente hacer un montón ! Ordenar (y barajar) matrices paralelas (o listas) es un negocio desagradable y no hay una API común para ello, simplemente porque generalmente desea evitarlo .

Le sugiero que reestructure su código así:

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 esta manera, barajar su pregunta se vuelve trivial (usando Collections.shuffle()):

Collections.shuffle(questionList);
Joachim Sauer
fuente
39
ni siquiera es negación de objeto, es negación de estructura de datos
jk.
22

Usted no Haces otra lista / cola de índices y barajas eso. Luego, recorre los índices que conducen el orden "barajado" de sus otras colecciones.

Incluso fuera de su escenario con cosas divididas, la colección de pedidos por separado proporciona una serie de beneficios (paralelismo, velocidad al volver a colocar la colección original es costosa, etc.).

Telastyn
fuente
10
Soy reacio a votar esto: es la siguiente mejor solución si este diseño es realmente fijo, pero insistir en este diseño es tan incorrecto que no quisiera dar ninguna sugerencia al respecto. (meh, voté de todos modos ;-))
Joachim Sauer
3
@joachimSauer: aunque estoy de acuerdo, hay muchos otros escenarios (menos ofensivos) en los que la colección original debe permanecer estática, mientras que el camino a través de ellos debe variar.
Telastyn
44
Sí, lo sé. Y barajar una colección de índices es el enfoque correcto para esas situaciones. Mi único temor es que el equipo de OP solo tome esto y diga "lo suficientemente bueno", sin volver a ver su diseño.
Joachim Sauer
1
Esta respuesta es valiosa especialmente para el caso en que uno no tiene la libertad de revisar / recodificar la clase o estructura de colección subyacente, por ejemplo, uno tiene que conformarse con una API para una colección mantenida por el sistema operativo. Mezclar los índices es una gran idea y se mantiene por sí mismo, incluso si no es una idea tan aguda como rehacer el diseño subyacente.
hardmath
@Joachim Sauer: barajar los índices no es necesariamente la mejor solución al problema como se indicó. Vea mi respuesta para una alternativa.
Michael Borgwardt
16

Estoy de acuerdo con las otras respuestas en que la solución correcta es usar un modelo de objeto adecuado.

Sin embargo, en realidad es bastante fácil mezclar varias listas de manera idéntica:

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
fuente
Esa es ... ¡una buena forma de hacerlo! ¡Ahora, para el caso de "clasificación" solo necesitamos encontrar una semilla que produzca una lista ordenada cuando se aplica de esta manera y luego barajamos todas las listas con esta semilla!
Joachim Sauer
1
@JoachimSauer: bueno, la clasificación no era parte del problema. Aunque es una pregunta interesante si hay una forma sistemática de encontrar una semilla para un RNG dado.
Michael Borgwardt
2
@MichaelBorgwardt una vez que llegue a más de 17 preguntas que simplemente no puede expresar la cantidad de posibles baraja en los 48 bits del Java utiliza aleatorio (log_2 (17) = 48.33!)
trinquete monstruo
@ratchetfreak: no me parece un problema real. Y es trivial usar SecureRandom en su lugar si es necesario.
Michael Borgwardt
44
@Telastyn: la lista de índices es IMO, una capa de indirección que hace que su solución sea conceptualmente más compleja, y si es más o menos eficaz depende de la frecuencia con la que se accede a las listas después de la combinación aleatoria. Pero las diferencias de rendimiento serían insignificantes dados los tamaños realistas para que un cuestionario sea respondido por humanos.
Michael Borgwardt
3

Crea una clase Question2:

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

Luego, cree una función que asigne un questiona ArrayList<Question2>, use Collection.Shufflepara ese resultado y cree una segunda función para ArrayList<Question2>volver a asignar question.

Luego, vaya a su equipo e intente convencerlos de que usar un en ArrayList<Question2>lugar de questionmejoraría mucho su código, ya que les ahorraría muchas de esas conversiones innecesarias.

Doc Brown
fuente
1
Esta es una buena idea, pero solo después de que los intentos a priori de cambiar el diseño hayan fallado.
Sebastian Redl
@SebastianRedl: a veces es más fácil convencer a las personas de un mejor diseño al mostrarles la solución en código.
Doc Brown
1

Mi respuesta ingenua e incorrecta original :

Simplemente cree (al menos) nnúmeros aleatorios e intercambie el elemento n con el elemento ien un ciclo for para cada lista que tenga.

En pseudocódigo:

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

}

Actualizar:

Gracias por the_lotus por señalar el artículo de horror de codificación. Ahora me siento mucho más inteligente :-) De todos modos, Jeff Atwood también muestra cómo hacerlo bien, utilizando el algoritmo de 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 principal diferencia aquí es que cada elemento se intercambia solo una vez.

Y aunque las otras respuestas explican correctamente que su modelo de objetos es defectuoso, es posible que no esté en la posición de cambiarlo. Entonces, el algoritmo de Fisher-Yates resolvería su problema sin cambiar su modelo de datos.

codingFriend1
fuente