Java通过两个数组搜索

我有2个ArrayList。 ArrayList A具有8.1k个元素，而ArrayList B具有81k个元素。Java通过两个数组搜索

我需要遍历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分钟的运行时间太多了。

来源

2017-03-16 Richard

使用索引，卢克！ –

我会从删除System.out.print和println调用开始。这很可能是大部分时间需要的。你还应该告诉b.equalsB（a）做了什么（即发布代码）：你可以使用HashMap，并将复杂度降低到O（m）而不是O（m * n）。并删除it.set（b），它自己替换b，因此是不必要的。另外，由于每个匹配的a代替了B中由前一个匹配的A设置的ID，因此可以向后迭代，并在找到匹配后立即停止循环。 –

@JBNizet我确实发布了b.equalsB（a）的代码。它正好在第一种方法的下面。 B需要设置，因为我们正在更改id，然后将其放回列表中 – Richard

我很乐意看到一个很好和彻底的解决方案，同时我可以提出两个想法（或者可能是两个转念之一）。

第一个是加速搜索类型A中的所有对象类型B的一个对象。因此，Rabin-Karp算法似乎适用和简单到足以快速实现，并且Aho-Corasick可能会给出更好的结果，而不是当然好多了。

另一种选择是限制B类型的对象的数量，对于A的每个对象应该完全处理这些对象，例如，建立一个逆N-gram索引：对于每个fullUrl，你取所有长度为N的子字符串（“N-grams”），并且你从每个这样的N-gram到一组B中具有这种N-gram的B的地图。当搜索一个对象A时，你取所有的N-gram，为每个这样的N-gram找到一组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-gram，从而减少内存占用和N-gram密钥比较的必要性。

来源

2017-03-17 22:34:49 starikoff

Java通过两个数组搜索

回答

相关问题