Java 2つの配列で検索する

Question

2つのArrayListがあります。 ArrayList Aには8.1k要素があり、ArrayList Bには81k要素があります。

Bを繰り返し、Aでその特定のアイテムを検索し、リストBの一致する要素のフィールドを変更する必要があります。

は、ここに私のコードです：

private void mapAtoB(List<A> aList, ListIterator<B> it) { 
    AtomicInteger i = new AtomicInteger(-1); 
    while(it.hasNext()) { 
     System.out.print(i.incrementAndGet() + ", "); 
     B b = it.next(); 
     aList.stream().filter(a -> b.equalsB(a)).forEach(a -> { 
      b.setId(String.valueOf(a.getRedirectId())); 
      it.set(b); 
     }); 
    } 
    System.out.println(); 
} 

public class B { 
    public boolean equalsB(A a) { 
     if (a == null) return false; 

     if (this.getFullURL().contains(a.getFirstName())) return true; 

     return false; 
    } 
} 

しかし、これは永遠に取っています。この方法を終了するには、15分近くかかります。これを最適化する方法はありますか？ 15分の実行時間はあまりにも多くです。

Answer 1

私は良いと徹底的な解決策を見て、私は2つのアイデアを提案することができます（または多分2つの生まれ変わり）。

タイプAのすべてのオブジェクトをタイプBの1つのオブジェクトで検索する速度を上げることです。そのためにはRabin-Karpアルゴリズムが適用可能であり、迅速に実装するには十分に簡単であると思われますが、Aho-Corasickは難しくなりますが、どれくらい良いか確かめてください。

もう1つの方法は、Aの各オブジェクトに対して完全に処理されるべきB型のオブジェクトの数を制限することです。それぞれのfullUrlに対して、長さNのすべての部分文字列（ "N-grams"）を取り、そのようなNグラムからfullUrlにそのようなNグラムを持つBのセットを作成します。オブジェクトAを検索するときには、Nグラムをすべて取り、そのようなNグラムごとにBのセットを見つけ、これらのセットすべてと交差させます。交差点には、すべて処理する必要があるすべてのBが含まれます。私はこのアプローチをすばやく実装しました。これは、指定したサイズがN = 4の場合に6〜7倍のスピードアップを提供するためです。 Nが大きくなるにつれて検索は速くなりますが、索引の作成が遅くなります（再利用できる場合は、Nを大きくする方が良いでしょう）。このインデックスは、指定したサイズで約200 Mbを要します。したがって、このアプローチでは、Bのコレクションの成長に伴い、これまでのスケーリングだけが行われます。すべての文字列がNGRAM_LENGTHより長いと仮定すると、ここにグアバのSetMultimap、HashMultimapを使用してインデックスを構築するための迅速かつ汚いコードです：

SetMultimap<String, B> idx = HashMultimap.create(); 
    for (B b : bList) { 
     for (int i = 0; i < b.getFullURL().length() - NGRAM_LENGTH + 1; i++) { 
      idx.put(b.getFullURL().substring(i, i + NGRAM_LENGTH), b); 
     } 
    } 

と検索用：

private void mapAtoB(List<A> aList, SetMultimap<String, B> mmap) { 
    for (A a : aList) { 
     Collection<B> possible = null; 
     for (int i = 0; i < a.getFirstName().length() - NGRAM_LENGTH + 1; i++) { 
      String ngram = a.getFirstName().substring(i, i + NGRAM_LENGTH); 
      Set<B> forNgram = mmap.get(ngram); 
      if (possible == null) { 
       possible = new ArrayList<>(forNgram); 
      } else { 
       possible.retainAll(forNgram); 
      } 
      if (possible.size() < 20) { // it's ok to scan through 20 
       break; 
      } 
     } 
     for (B b : possible) { 
      if (b.equalsB(a)) { 
       b.setId(a.getRedirectId()); 
      } 
     } 
    } 
} 

最適化のための可能な方向が考え完全なNグラムの代わりにハッシュを使用することによって、メモリのフットプリントを減らし、Nグラムのキー比較の必要性を減らすことができます。