比较Java中常见元素的列表的更快方法？

Question

我有LinkedLists的图形（用矢量实现），我想连接不共享任何公共元素的LinkedLists。我认为我现在这样做的方式需要O（n^3）。我有一个for循环遍历Vector，然后嵌套for循环遍历Vector（以便我可以将每个List与其他每个List进行比较），然后在循环内部使用递归来比较列表。

在尝试这种方法之前，我尝试了在第二个for循环中循环遍历每个列表并使用二进制搜索来查看第二个列表是否包含每个元素，但我认为这需要相同数量的时间或更长。 这里是我的循环：

public void addEdges(){ 
    for(int i =0; i < size()-1; i++){ 
    for(int j = i+1; j < size(); j++){ 
    if(compatible(get(i),get(j),1,1)){ 
    get(i).linkTo(get(j)); 
    get(j).linkTo(get(i)); 
    } 
    } 
    } 
} 

，这里是我的递归：

public boolean compatible(Row a, Row b, int indexA, int indexB){ 
    if(a.get(indexA).getEnd() == b.get(indexB).getEnd()){ 
    return false; 
    } 
    else if(a.get(indexA).getEnd() == 0){ 
    return true; 
    } 
    else if(a.get(indexA).getEnd() > b.get(indexB).getEnd()){ 
    return compatible(a,b,indexA+1,indexB); 
    } 
    else{ 
    return compatible(b,a,indexB+1,indexA); 
    } 
} 

Answer 1

假设我正确地读这篇文章，你可以到Collections.disjoint静态方法的调用替换您的compatible方法。

编辑：代码示例：

public void addEdges(){ 
    for(int i =0; i < size()-1; i++){ 
    for(int j = i+1; j < size(); j++){ 
    if(Collections.disjoint(get(i),get(j))){ 
    get(i).linkTo(get(j)); 
    get(j).linkTo(get(i)); 
    } 
    } 
    } 
} 

Answer 2

我可能会尝试一个反向指标，element -> [IDs of containing lists]。遍历索引会告诉你哪些列表共享元素，因此无法连接。

• 步骤1：创建反向索引
• 步骤2：创建不相容索引，list ID -> [IDs of incompatible lists]
• 步骤3：迭代过incompatiblity地图加入列出了哪些是兼容的。

如果连接兼容列表有特定的规则，步骤3可能会更复杂，因为兼容性不是瞬态的。

---

一些伪Java的：为了我自己，我会假设数据结构是这样的（也许是我Bin是你，更多或更少）：

class Bin { 
    ID id; 
    LinkedList<Element> list; 
} 

的一组箱子，allBins是Collection<Bin>的类型。

步骤1：反向索引的类型为MultiValueMap<Element, ID>。也就是说，每个元素都映射到一组ID（包含该元素的bin）。

MultiValueMap<Element, ID> reverseIndex; 

for (Bin bin : allBins) { 
    for (Element e : bin) { 
     reverseIndex.put(e, bin.id); 
    } 
} 

步骤2：不相容指数是MultiValueMap<ID, ID>类型，其中每个箱ID被映射到该组不相容仓仓ID中的。

MultiValueMap<ID, ID> incompatibilityIndex; 

for (Element e : reverseIndex.keySet()) { 
    List<ID> binsWithE = reverseIndex.get(e); 
    for (ID id : binsWithE) { 
     incompatibilityIndex.putAll(id, binsWithE); // each bin is incompat with itself 
    } 
} 

第3步：现在我们可以加入任何两个不在彼此不兼容的地图。自从加入两个区间改变不兼容性，我们必须要棘手：

Set<Bin> binsRemainingToProcess; // == original allBins 
Set<Bin> binsProcessed; // == new allBins 

while (binsRemainingToProcess.size() > 0) { 
    Bin bin = // grab any bin to work on from binsRemainingToProcess 

    // grab any compatible bins 
    // could iterate until we find one, but I'm going to compute all compatible 
    List<ID> compatibleBinIDs = // all bin IDs in binsRemaining... 
    List<ID> incompatibleBinIDs = incompatibilityIndex.get(bin.id); 
    compatibleBinIDs.removeAll(incompatibleBinIDs); 

    if (compatibleBinIDs.size() > 0) { 
     Bin otherBin = // some bin with ID in compatibleBinIDs 

     // joining the two bins -- means joining the inner lists, 
     // but also joining the incompatibilities 
     joinDataStructures(bin, otherBin); 
     incompatibilityIndex.putAll(bin.id, incompatibilityIndex.get(otherBinID)); 

     // we don't need the other bin anymore, but we may be able to join 
     // the first bin to others 
     binsRemainingToProcess.remove(otherBin); 
    } else { 
     // couldn't join with anyone; we're done with this bin and can move on 
     binsRemainingToProcess.remove(bin); 
     binsProcessed.add(bin); 
    } 
} 

好的，那么最后一个结束了很多比我计划的更详细的...

Answer 3

我知道你正在寻找更快的方法来做到这一点，我觉得@迈克尔 - 布鲁尔 - 戴维斯 建议这样做的更好的办法，但有什么办法可以解决这个问题，然后再创建 名单？因此，当创建列表时，而不是比较已创建的列表，以便在列表创建时进行比较，这样您就不必如此残忍地递归？ （我的意思是可能是一个设计更改：比较不平等的元素一次，以便不相关的元素自然分组在一起，并可能避免递归）

Answer 4

我实际上想过一个更快的方式来比较我的列表。我列出了所有可能的元素，现在不是元素列表，而是使用long的每一位来表示它们是否包含可能元素列表中的相应元素。然后我用&运营商比较多头，看他们是否有任何共同的元素。