java - 多次有效验证一个小 arrayList 的所有元素是否包含在另一个小 arrayList 中

Question

我有几个小的 arrayList(800~1500)，对于每一个，我必须在尽可能好的时间内验证它是否包含评估 arrayList 中的所有项目。目标 arrayList(假设为 tSet)和评估 arrayList (eSet) 都有 1 到 5 个元素。

我尝试了一系列简单循环(当前实现)，执行时间约为 10 秒，以及 containsAll()，执行时间不一致，范围从 8 秒到 16 秒(使用相同的 tSet)。这种不一致有原因吗？有更好的方法来执行此操作吗？

数组元素来自以下类:

public class ItemBD_Temp implements Comparable<ItemBD_Temp> {
private String sTabela;
private String sValor;
private String sNome;
...
}

它还有一个compareTo()方法:

public int compareTo(ItemBD_Temp o) {
    String concatThis;
    String concatOther;
    if(this.sTabela.equals("*AnyTable*") || o.sTabela.equals("*AnyTable*")){
        concatThis = "";
        concatOther = "";
    }
    else if(this.sNome.equals("*AnyAtrib*") || o.sNome.equals("*AnyAtrib*")){
        concatThis = this.sTabela;
        concatOther = o.sTabela;
    }
    else if(this.sValor.equals("*AnyValue*") || o.sValor.equals("*AnyValue*")){
        concatThis = this.sTabela + this.sNome;
        concatOther = o.sTabela + o.sNome;
    }
    else{
        concatThis = this.sTabela + this.sNome + this.sValor;
        concatOther = o.sTabela + o.sNome + o.sValor;
    }

    return concatThis.compareTo(concatOther);
}

这是我迄今为止所拥有的一个非常简化的版本:

for(int j = 0; j < eSet.itens.size() && tSetAllowed == true; j++){
    itemFound = false;
    //CURRENT ITEM TO BE SEARCHED
    eItem = new ItemBD_Temp(eSet.itens.get(j));

    //CHECK IF CURRENT ITEM IS ON THE CURRENT tSet. IF FOUND, STOPS AND CHECKS NEXT eItem
    for(int k = 0; k < tSet.size() && itemFound == false; k++){
        tItem = tSet.get(k);

        if(tItem.compareTo(eItem) == 0){
            itemFound = true;
        }
        else{
            itemFound = false;
        }
    }

    //IF tItem WASN'T FOUND, THEN tSet CAN BE DISCARTED
    if(itemFound==false){
        tSetAllowed = false;
    }
}

编辑1:为了使用 arrayList.containsAll() 我还必须重写 Equals 方法，如下所示:

@Override
public int hashCode() {
        int hash = 3;
        hash = 89 * hash + (this.sTabela != null ? this.sTabela.hashCode() : 0);
        hash = 89 * hash + (this.sValor != null ? this.sValor.hashCode() : 0);
        hash = 89 * hash + (this.sNome != null ? this.sNome.hashCode() : 0);
        return hash;
 }

@Override
public boolean equals(Object obj) {
        System.out.println("OVERRIDED EQUALS");
        if (getClass() == obj.getClass()) {
            if(this.sTabela.equals("*AnyTable*") || ((ItemBD_Temp)obj).sTabela.equals("*AnyTable*")){
                return true;
            }
            else if(this.sNome.equals("*AnyAtrib*") || ((ItemBD_Temp)obj).sNome.equals("*AnyAtrib*")){
                if(this.sTabela.equals(((ItemBD_Temp)obj).sTabela))
                    return true;
                else
                    return false;
            }
            else if(this.sValor.equals("*AnyValue*") || ((ItemBD_Temp)obj).sValor.equals("*AnyValue*")){
                if((this.sTabela+this.sNome).equals( (((ItemBD_Temp)obj).sTabela+((ItemBD_Temp)obj).sNome) ))
                    return true;
                else
                    return false;
            }
            else{
                if((this.sTabela+this.sNome+this.sValor).equals( (((ItemBD_Temp)obj).sTabela+((ItemBD_Temp)obj).sNome+((ItemBD_Temp)obj).sValor) ))
                    return true;
                else
                    return false;
            }
        }
        else{
            return (this == obj);
        }        
    }

这是必需的，因为不同的对象，如 obj1 = {sTabela = "1", sNome = "2", sValor="3"} 和 obj2 = {sTabela = "AnyTable ", sNome = "AnyAtrib", sValor="AnyValue"} 应被视为等效。

Answer 1

您正在使用ArrayList作为数据结构。它是一种不同步的数据结构。在你的问题中只有读取操作，所以应该不是问题。然而，总的来说，在您的程序中有如此多的不同步列表，请考虑线程安全。

<小时/>

对于ArrayList来说，通过迭代器或通过索引访问元素在速度方面几乎是相同的。然而，这不是官方基准。您也可以考虑使用迭代器尝试您的代码。

<小时/>

I have several small arrayLists (800~1500) and for each one of those I must verify if it contains all items from a evaluation arrayList in the best possible time. Both the target arrayList (let's say, tSet) and the evaluation arrayList (eSet) have 1 to 5 elements.

您有 800 到 1500 个数组列表。我想你“有义务”使用该数据结构。

您有 1 个评估数组列表。在这里我可能会考虑改变。我会使用哈希表/映射作为数据结构。平均而言，搜索速度更快。事实证明这是正确的。在哈希表/映射中插入/删除/搜索元素的平均时间复杂度是 O(1)。这意味着平均时间恒定。 (最坏的情况是 O(n)，但一般来说我们感兴趣的是平均值)。

“如果目标列表包含评估列表的所有项目”相当于“所有评估列表项目都在目标列表中”。在您的示例中，您循环遍历目标列表并进行比较，但您也可以循环遍历评估列表并进行比较。

Now assuming that you always want to test whether evaluation list is a sub set of target list. It is better to loop through evaluation list and do the comparison as it is expected to have less elements.

我稍后会检查你的代码。但有一点我觉得不太舒服:

The conditions in your loop! Are you sure your algorithm works as expected?