Как избежать временной сложности O (n^2)?

У меня есть этот следующий фрагмент кода:Как избежать временной сложности O (n^2)?

for(ArticleBasketInBean basketBean : bean.getBasket()) { 
    for(ArticleDTO article : dto.getArticleList()) { 
     if(basketBean.getArticleReference().equals(article.getArticleReference())) { 
      article.setAddedToBasket(true); 
     } 
    } 
}

Очевидно, что временная сложность указанной выше операции является O (N^2). Для этого случая articleReference уникален. Таким образом, список, возвращаемый bean.getBasket(), не имеет дубликата articleReference, также это верно для списка, возвращаемого dto.getArticleList().

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

источник

2013-06-15 Tapas Bose

Вам понадобится какая-то структура индекса, например HashMap. Но действительно ли вложенная петля проблема? Сколько статей мы говорим? – Thilo

Простой трюк для сокращения итераций: 'break' из внутреннего цикла после первого совпадения. Тем не менее O (n^2). – Thilo

Вы можете немного улучшить это, но в худшем случае всегда будет O (n^2). – Maroun

Если у вас слишком много статей/корзин, и, как вы говорите, ссылки уникальны, вы можете сделать что-то подобное; давайте назовем R тип ссылки, A того типа изделий, B того типа корзин:

// since all references are unique we can use that, but see below 
Map<R, A> mappedArticles = new IdentityHashMap<>(); 

// inject articles based on references in the map, then 

A article; 

for (B basket: bean.getBasket()) 
    article = mappedArticles.get(basket.getArticleReferences()); 
    if (article != null) 
     article.setAddedToBasket(true); 

// Full list of articles is in the map's .values()

Примечания:

Примечание использование идентичности HashSet; вы можете захотеть реализовать equals/hashcode для ссылок (или, возможно, тип, который вы используете, уже реализовал для вас);
Ваша карта может быть заполнена как статьи «flow by», в этом случае вы можете создать ее только один раз (сделайте ее потокобезопасной, если да!).

источник

2013-06-15 08:13:51 fge

Благодарим вас за ответ. У меня есть hashcode и 'equals' для статьи. Два вопроса, которые у меня есть, я знаю, что 'IdentityHashMap' использует' == 'оператор для сравнения объектов, который равен' equals' в случае 'HashMap'. Какой дополнительный бонус производительности я могу достичь, используя 'IdentityHashMap' вместо' HashMap'?Я раньше не использовал 'IdentityHashMap', поэтому мне нужно переопределить метод' equals' как: 'this.getArticleReference() == this.getArticleReference();}' или 'this.getArticleReference(). Equals (что .getArticleReference() ' –

Если у вас hashCode и equals уже нет необходимости в' IdentityHashMap', они действительно существуют только для ссылочного равенства;) – fge

Простой break сэкономит вам.

for(ArticleBasketInBean basketBean : bean.getBasket()) { 
    for(ArticleDTO article : dto.getArticleList()) { 
     if(basketBean.getArticleReference(). 
            equals(article.getArticleReference())) { 
      article.setAddedToBasket(true); 
      break; 
     } 
    } 
}

источник

2013-06-15 08:00:44

Является ли это еще O (n^2)? – xqterry

Не меняет порядок, только делает его немного быстрее. – SJuan76

Использование java.util.HashSet кэшировать один из наборов ссылок, предполагая, что наборы не слишком большой, конечно. При хорошей хэш-функции это должно вернуть вас к O (n).

источник

2013-06-15 08:04:48

Как избежать временной сложности O (n^2)?

ответ

Смежные вопросы