java - 時間の複雑さ O(n^2) を回避するには?

Question

次のコードがあります。

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()。

このネストされた反復を避け、より高速なコードを記述したいと考えています。どうやってやるの？

Answer 1

java.util.HashSetもちろん、セットが大きすぎないことを前提として、参照のセットの 1 つをキャッシュするために使用します。適切なハッシュ関数があれば、これで O(n) に戻るはずです。

Answer 2

記事/バスケットが多すぎず、参照が一意であると言う場合は、次のようなことができます。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()

ノート：

• IDハッシュセットの使用に注意してください。代わりに、参照に equals/hashcode を実装することをお勧めします (または、使用する型に既に実装されている可能性があります)。
• あなたのマップは記事が「流れていく」ように埋められるかもしれません。

Answer 3

シンプルbreakがあなたを救います。

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