Проверьте, есть ли у объекта List узел, который соответствует заданному свойству этого объекта

Question

У меня есть объект List of Leave, свойствами Leave являются exitDate (java.util.Date), leftTime (int), leftType (String)Теперь, чтобы проверить, есть ли в этом списке узел, свойство которого leftDate совпадает с timeStamp, timeStamp является другим объектом Date, мы можем выполнить итерацию по этому списку.Есть ли другой способ сделать это?У меня также есть следующая проверка состояния:

if (Lambda.select(this.fullLeaves, Lambda.having(Lambda.on(Leave.class).getLeaveDate(), Matchers.equalTo(timeStamp))).size() == 0) {
           //some code 
}

Используется lambdaj .Спасибо.

Answer 1

Чтобы повысить производительность простого свойства iterate-and-test-the, вам необходимо создать структуру данных, которая будет действовать как вторичный индекс для объектов в списке, и преобразовать предикат выбора в запросы к этому индексу. ,

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

Обратите внимание, что здесь есть компромисс. Вторичный индекс даст вам более быстрый поиск по списку, но стоимость будет увеличена сложность, и медленнее добавление и удаление списка. Таким образом, такие средние размеры списков и шаблоны использования будут определять, даст ли вторичный индекс общее улучшение производительности.

---

Если тестируемое свойство изменчиво / может измениться, пока объект находится в списке, вам потребуется обновлять вторичный индекс каждый раз, когда изменяется свойство объекта в списке. Реализация этого правильно добавит значительные дополнительные затраты и сложность.

Answer 2

При поиске в Списке объектов вы не можете сделать лучше, чем перебирать объекты за O (n) раз.

Есть два других варианта, но они требуют, чтобы вы использовали другую структуру данных - либо вместо списка, либо в дополнение к нему:

1. Используйте массив объектов Leave и сохраняйте его отсортированным по отметке времени. Таким образом, вы можете найти правильный отпуск в O (log (n)) времени. Вы платите за это с большим временем вставки - так как вы должны вставить Leave в нужном месте и расширить размер массива по мере необходимости - со списком, вы можете просто добавить Leave в O (1).

2. Используйте карту, где ключом является метка времени. Таким образом, вы можете найти требуемый отпуск за O (1) раз.

Второй вариант проще реализовать. В любом случае выбор зависит от того, как вы используете структуру данных - каково соотношение вставки к поиску? Если вы делаете еще много вставок, то, возможно, лучше остаться со списком. Если вы выполняете еще много поисков, переходите к карте.

Это также зависит от того, насколько велик ваш типичный список. Если это просто сотни объектов, вы не почувствуете большой разницы в любом случае.

Наконец, лучше всего протестировать различные реализации в соответствии с вашей конкретной моделью использования.