Поиск объекта в ArrayList

Question

Я относительный новичок в Java и создаю приложение для моего курса программирования, где пользователи могут вводить, удалять, искать или редактировать список студентов (объект, который состоит из целочисленного идентификационного номера, фамилии String,и двойной средний балл).До сих пор я успешно разрешал пользователю вводить, удалять или редактировать записи.Прямо сейчас список из 100+ учеников находится в ArrayList (каждый в виде объекта Student с тремя параметрами).

Моя проблема в том, что я не знаю эффективного способа, позволяющего пользователю искатьконкретный студент на основе идентификационного номера, фамилии или GPA (и, возможно, диапазона GPA в будущем).Я изучал нотацию Big-O и хотел бы использовать бинарный поиск, потому что это будет отличной практикой, а также лучшим выбором, если список студентов будет продолжать расти.Пока что для бинарных поисков мы используем метод high / low / mid с циклом while (если это указывает на мой текущий уровень квалификации).

Итак, вот мой вопрос:

Какой эффективный способ поиска конкретного ученика основан на этих критериях?Я не ищу код или ответы на мою дилемму.Я действительно ищу названия методов или приемов, которые Java-программисты используют для таких целей, особенно если эти методы можно использовать с другими объектно-ориентированными языками программирования.

Answer 1

Я рекомендую изучить структуру данных HashMap . Он позволяет хранить элементы в коллекциях, сопоставленных с определенным ключом, чтобы впоследствии их можно было извлечь по тому же ключу. В вашем примере вы можете иметь разные хеш-карты для поиска по разным полям. Ключом хеш-карты будет поле (т. Е. ID, фамилия или GPA), а значением будет соответствующий студент. Для поиска без учета регистра убедитесь, что ключ (фамилия) преобразован в нижний регистр перед сохранением объекта и перед извлечением объекта.

для хранения идентификаторов:

Map<String, Student> idToStudent;

ключ: "23213233", значение: "Some Student";

, чтобы учесть дубликаты имен или gpa, затем используйте карту типа:

Map<String, List<Student>> lastNameToStudents;

ключ: «кузнец», значение: [«Джон Смит», «Боб Смит» и т. Д.]

Map<Double, List<Student>> gpaToStudents:

клавиша: «2.4», значение: [«Студент 1», «Студент 2» и т. Д.];

Обратите внимание, я для краткости использую строковое представление имени студента, но на самом деле они представляют Student экземпляров.

Answer 2

Для бинарного поиска необходимо, чтобы список сортировался по критериям, по которым вы ведете поиск.

Вы можете вести три разных списка, отсортированных по трем различным критериям, которые вам нужны:

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

Обратите внимание, что когда вы вставляете нового ученика в свой ArrayList, вы должны также вставить этого ученика в другие отсортированные списки ArrayList в правильном месте.(Конечно, для этого можно использовать бинарный поиск.)

Answer 3

Итак, я вижу три проблемы с одной общей проблемой. Общая проблема заключается в том, что вы хотите иметь возможность выполнять поиск по некоторым критериям, при этом три проблемы являются конкретными случаями для каждого. Таким образом, единственное поле, которое гарантированно будет уникальным, будет полем Student ID. Это позволяет нам переопределить методы equals + hashcode. Мы хотим, чтобы это было значением, которое мы используем для определения равенства (по крайней мере, в этом очень простом примере). Сделав это, вы раскроете механизм поиска в списке без сортировки с помощью следующего вызова:

list.contains(Student);

Теперь с точки зрения имени, поскольку это значение не гарантируется как уникальное, мы хотели бы сделать что-то похожее на это:

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

В терминах GPA мы, по сути, повторили бы описанный выше цикл, просто вызывая с помощью где GPA == searchCriteria.

при этом должно быть возможно написать такую ​​функцию:

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

это должно начать вас.

Answer 4

Вам нужны дубликаты или произвольный порядок? Если нет, подумайте об использовании TreeSet или HashSet. TreeSet предлагает O (log (n)) доступ / вставку / удаление и автоматически сортирует свои элементы (таким образом, перебирая его, получает элементы в отсортированном порядке. HashSet обеспечивает амортизированный O (1) доступ / вставка / удаление, но итерация происходит какой-то случайный порядок (который вы не можете контролировать). Один из них звучит как самый простой способ достижения ваших целей.

Если вам нужен поиск по члену, вы, вероятно, захотите HashMap / TreeMap, если вы не против только точных совпадений. Если вам нужно выполнить поиск по члену для нескольких участников, вам может потребоваться несколько карт с одной картой для каждого ключа, который вы хотите найти. Если бы вы использовали ArrayLists и хотели, чтобы поиск был лучше, чем O (n), вам все равно понадобилось бы несколько списков (по одному списку на параметр поиска, отсортированный по этому параметру).

В конце концов, поиск O (n) будет самым простым. До тех пор, пока список не станет слишком большим (например, 10000 элементов вместо 100), производительность будет хорошей, и такой подход минимизирует затраты на хранение. Вам не нужна преждевременная оптимизация - до тех пор, пока производительность не станет проблемой, лучший способ - просто перебирать весь список.