metodos - metodo buscar en listas java

Búsqueda de objetos en ArrayList

Question

Soy relativamente novato en Java y estoy creando una aplicación para mi curso de programación donde los usuarios pueden ingresar, eliminar, buscar o editar una lista de Estudiantes (un objeto que consta de un número de ID entero, un apellido de Cadena y un doble GPA). Hasta ahora, he tenido éxito al permitir que el usuario ingrese, elimine o edite entradas. En este momento, la lista de más de 100 estudiantes está en una ArrayList (cada uno como un objeto de Estudiante con los tres parámetros).

Mi problema es que no conozco una manera eficiente de permitirle al usuario buscar un estudiante específico basado en el número de identificación, apellido o GPA (y posiblemente el rango de GPA en el futuro). He estado estudiando la notación Big-O y me gustaría utilizar una búsqueda binaria porque sería una gran práctica y una mejor opción si la lista de estudiantes sigue creciendo. Hasta el momento, para búsquedas binarias, estamos usando el método alto / bajo / medio con un ciclo while (si eso es una indicación de mi nivel de habilidad actual).

Ésta es mi pregunta:

¿Cuál es una forma eficiente de buscar un estudiante específico basado en este criterio? No estoy buscando código o respuestas a mi dilema. Realmente estoy buscando los nombres de las técnicas o trucos que los programadores de Java usan para hacer tal cosa, especialmente si esas técnicas se pueden usar con otros lenguajes de programación orientados a objetos.

Answer 1

Recomiendo buscar en la estructura de datos de HashMap . Le permite almacenar elementos en una colección asignada a una determinada clave, de modo que luego puedan ser recuperados por esa misma clave. En su ejemplo, podría tener diferentes mapas hash para buscar en diferentes campos. La clave del mapa hash sería el campo (es decir: ID, apellido o GPA), y el valor sería el alumno correspondiente. Para búsquedas que no distinguen entre mayúsculas y minúsculas, asegúrese de convertir la clave (apellido) en minúscula antes de guardar un objeto y antes de recuperar un objeto.

para almacenar identificadores:

Map<String, Student> idToStudent;

clave: "23213233", valor: "Some Student";

para tomar en cuenta nombres duplicados o gpa, luego use un mapa de tipo:

Map<String, List<Student>> lastNameToStudents;

clave: "smith", valor: ["John Smith", "Bob Smith", etc.]

Map<Double, List<Student>> gpaToStudents:

clave: "2.4", valor: ["Estudiante 1", "Estudiante 2", etc.];

Tenga en cuenta que estoy usando la representación de cadena del nombre de un alumno para abreviar, pero en realidad esas representan instancias de Student .

Answer 2

¿Necesita duplicados o un pedido arbitrario? Si no, piense en usar TreeSet o HashSet. Un TreeSet ofrece O (log (n)) acceso / inserción / eliminación y ordena automáticamente sus elementos (por lo que iterar sobre él obtiene los elementos en orden ordenado. Un HashSet proporciona acceso / inserción / eliminación amortizado O (1), pero la iteración ocurre en un orden aleatorio (sobre el que no tiene control). Uno de estos sonidos es la manera más fácil de lograr sus objetivos.

Si necesita buscar por miembro, probablemente quiera un HashMap / TreeMap, siempre y cuando no le importe obtener las coincidencias exactas. Si necesita buscar por varios miembros, es posible que desee varios mapas con un mapa por clave que desee buscar. Si tuviera que utilizar ArrayLists y deseara una búsqueda mejor que O (n), necesitaría varias listas de todos modos (1 lista por parámetro de búsqueda ordenado en ese parámetro).

Al final, la búsqueda de O (n) será de lejos la más fácil. Siempre que la lista no sea demasiado grande (piense en 10000 elementos en lugar de 100), el rendimiento estará bien, y este enfoque minimizará la sobrecarga de almacenamiento. No desea una optimización prematura: hasta que el rendimiento sea un problema, la mejor técnica es simplemente iterar en la lista.

Answer 3

Entonces veo tres problemas con un problema general. El problema general es que desea poder buscar en algunos criterios, siendo los tres problemas los casos específicos para cada uno. Por lo tanto, el único campo que se garantiza que será único sería el campo ID de estudiante. Esto nos permite anular los métodos equals + hashcode. Queremos que este sea el valor que utilizamos para determinar la igualdad (al menos en este ejemplo muy simple). Haciendo esto, habrá expuesto un mecanismo para búsquedas en una lista sin ordenar, a través de la siguiente llamada:

list.contains(Student);

Ahora, en términos del nombre, ya que no se garantiza que este valor sea único, querríamos hacer algo similar a esto:

 matchedStudents = new ArrayList<Student>();
for(Student currentStudent : studentList)
{
if(currentStudent.getName().equalsIgnoreCase(searchString)
{
matchedStudents.add(currentStudent);
}
}
return matchedStudents;

En términos del GPA, básicamente, deberíamos repetir el ciclo anterior simplemente llamando usando GPA == searchCriteria.

Dicho esto, debería ser posible escribir una función como esta:

function searchStudent(String searchString, String type)
{
//type is one of: GPA, name, ID
switch(type)
{
case gpa:
case id:
case name:
}
} 

eso debería hacerte comenzar.

Answer 4

Para la búsqueda binaria, necesitaría que la lista se clasifique según los criterios con los que está buscando.

Puede mantener tres listas diferentes, ordenadas por los tres criterios diferentes que necesita:

ArrayList<Student> sortedByName;
ArrayList<Student> sortedByGpa;
ArrayList<Student> sortedById;
public List<Student> getStudentByName(String name){
return binarySearchOnName(sortedByName, name);
}
public List<Student> getStudentByGpa(double gpa){
return binarySearchOnGpa(sortedByGpa, gpa);
}
...

Tenga en cuenta que cuando inserta un nuevo Estudiante en su ArrayList, también debe insertar ese Estudiante en el otro, ordena ArrayLists en el lugar correcto. (Puede usar la búsqueda binaria para hacer esto, por supuesto).