Сортировка и фильтрация списка объектов
У меня есть внешняя служба, откуда я получаю сведения обо всех сотрудниках организации, как показано ниже. Я использую java8 и весенний клиент симуляции облака для использования службы
[
{
"employee": {
"empId": "empId123",
"name": "Emp1",
"houseNumber": "5",
"firstName": "firstName1",
"lastName": "lastName1",
"city": "city1",
"band": "A"
},
"type": "ABC"
},
{
"employee": {
"empId": "empId456",
"name": "Emp2",
"houseNumber": "7",
"firstName": "firstName2",
"lastName": "lastName2",
"city": "city2",
"band": "B"
},
"type": "ABC"
}
:
:
]
Служба информации о сотрудниках насчитывает около 10000+ данных о сотрудниках.
У меня есть требование создать еще две службы
- Сортировка по город и номер дома и возврат всех сотрудников
- Сервис для фильтрации сотрудников по определенным атрибутам, таким как город, группа, empId и т. д.
В настоящее время я использую службу сортировки, как показано ниже.
final List<Employees> employeesList = employeeService.getAllEmployees().stream()
.sorted((emp1, emp2) -> p1.getAddress().getCity().compareTo(emp2.getAddress().getCity()))
.sorted((emp1, emp2) -> p1.getAddress().getHouseNumber().compareTo(emp2.getAddress().getHouseNumber()))
.collect(Collectors.toList());
Для фильтрации я использую приведенный ниже код
String cityName = "some city name"...
final List<Employees> employeesfilteredList = employeeService.getAllEmployees()
.stream()
.filter(employee -> employee.getAddress().getCity().equalsIgnoreCase(cityName == null ? "" : cityName))
.collect(Collectors.toList());
но мой клиент, который является техническим специалистом, говорит, что у этого есть проблемы с производительностью, и попросил принести что-то, что требует меньше времени (лучше всего О (1)) для получения результата
Может ли кто-нибудь сказать мне, в чем проблема с текущим подходом, который я использую, и есть ли способ, которым я могу импровизировать его любым другим способом или подходом?
Шутки в сторону? Номер дома имеет приоритет над городом? А как насчет улицы? Кроме того, вы можете избежать многократной сортировки, вы можете избежать выполнения избыточной проверки null при каждой оценке предиката, но вы не можете изменить временную сложность. Линейный список - это линейный список. Когда базовая услуга не предоставляет ничего лучшего, вы ничего не можете изменить в этом. Да, и Employees - плохое имя для класса, который моделирует одного сотрудника на экземпляр ...
Спасибо JBNizet и Holget за ответ. Просто мысль, не уверен, прав ли я или нет, как поддерживать его в хеш-таблице, имеет O (1) при вставке, поиске и удалении (i.stack.imgur.com/l56sp.png)
@AlexMan Вы в основном смотрите на временные сложности Get, Insert и Delete. В то время как то, что вы собираетесь делать в своей службе, - это Сортировка, Фильтр и т. д. Есть разница.
Если вы можете позволить себе один раз вызвать внешнюю систему, затем сохранить результаты в HashMap и использовать эту HashMap для всех последующих запросов, не получая свежие значения из внешней системы, тогда не используйте HashMap. Используйте базу данных с соответствующими индексами и используйте ее для фильтрации и сортировки результатов.
Ответы 1
Одна вещь, о которой я мог подумать, что вы, безусловно, можете импровизировать, - это двойной вызов sorted, который может быть выполнен только один раз:
// replacing with 'employees' for 'employeeService.getAllEmployees()'
Comparator<Employees> compareBasedOnCity =
Comparator.comparing(emp -> emp.getAddress().getCity());
Comparator<Employees> compareBasedOnHouse =
Comparator.comparing(emp -> emp.getAddress().getHouseNumber());
employees.sort(compareBasedOnCity.thenComparing(compareBasedOnHouse));
и другой во время фильтрации, чтобы не рассматривать строку null и "" как одну и ту же:
List<Employees> finalList = employees.stream()
.filter(employee -> employee.getAddress().getCity().equalsIgnoreCase(cityName))
// don't consider empty city name same as null (think of " " otherwise)
.collect(Collectors.toList());
Но, как уже указывалось в Хольгер и JB Низет, ничто из этого не снижает сложность, скажем, от O(nlogn) до O(1), как вы ожидаете.
Его дальнейшее сравнение с такими операциями, как доступ, вставка и удаление, также не эквивалентно. Поскольку выполняемые операции у них тоже разные.
... и если вы хотите обработать строку поиска null как "", вам нужно сделать это только один раз, перед операцией потока, String searchTerm = cityName == null ? "" : cityName; List<Employees> finalList = employees.stream() .filter(employee -> employee.getAddress().getCity() .equalsIgnoreCase(searchTerm)) .collect(Collectors.toList());
@nullpointer, спасибо за ответ .... из любопытства, не могли бы вы сказать мне, как этот тип employees.sort(compareBasedOnCity.thenComparing(compareBasedOnHouse)); работает лучше, чем то, что я использовал ...
@AlexMan второй компаратор запрашивается только для пар элементов, которые первый компаратор считает равными. Напротив, две операции сортировки всегда являются двумя операциями сортировки. В худшем случае вся первая операция сортировки устаревает.
1. У вас неправильная сортировка: выполняется сортировка по городу, а затем все элементы снова сортируются по номеру дома. 2. Нет возможности отсортировать или отфильтровать список в O (1). Сортировка - O (n * log (n)), а фильтрация - O (n). Лучшим подходом было бы позволить внешней службе выполнять эту фильтрацию и сортировку, делегируя эту задачу своей базе данных, а не загружать все в память, отправлять все по сети, десериализовать все и фильтровать большинство из них.