如何更快地计算这些列表的差异？

Question

我想要减去两个ArrayList，以便得到不在另一个列表中的元素。

我是这样做的：

removeIDs=(ArrayList<Integer>) storedIDs.clone();
removeIDs.removeAll(downloadedIDs);

downloadIDs=(ArrayList<Integer>) downloadedIDs.clone();
downloadIDs.removeAll(storedIDs);

问题在于两个列表都包含5000个子项，并且在我的安卓手机上几乎需要4秒钟的时间。

有没有更快的方法可以做到这一点？ 使用集合是否更快？（列表中没有重复的值）

我正在开发一个安卓应用程序。

- user1886411

Answer 1

除非你需要保留顺序，否则请使用HashSet代替ArrayList。

对于列表实现，删除元素需要扫描整个列表，而与之相比，HashSet只需要计算哈希码并识别目标桶。

- Chris Cooper

Answer 2

Sets应该更快。目前，它基本上是在做一个n^2的循环。它遍历每个removeIDs元素，并检查该id是否在downloadedIDs中，这需要搜索整个列表。如果downloadedIDs存储在更快的搜索器中，如HashSet，那么这将变得更快，并且成为O(n)而不是O(n^2)。Collections API中可能还有更快的东西，但我不知道它。

如果您需要保留排序，可以使用LinkedHashSet而不是普通的HashSet，但这会增加一些内存开销，并对插入/删除元素稍微影响性能。

- user2144429

Answer 3

我同意使用 HashSet 推荐，除非整数 ID 适合于相对较小的范围。在这种情况下，我建议使用 HashSet 和 BitSet 进行基准测试，并实际使用在您的环境中数据更快的那个。

- Patricia Shanahan

Answer 4

首先，我为回答太长而道歉。如果我有任何错误，您随时可以纠正我。在这里，我正在比较解决方案的一些选项

选项1 < ArrayList >：

在您的代码中，您使用了ArrayList.removeAll方法，让我们看看removeAll的代码

removeAll的源代码

public boolean removeAll(Collection<?> c) {
        return batchRemove(c, false);
    }

所以需要知道batchRemove方法中有什么。这里是链接。关键部分在于，如果您能看到

for (; r < size; r++)
         if (c.contains(elementData[r]) == complement)
                 elementData[w++] = elementData[r];

现在让我们看一下contains方法，它只是indexOf方法的一个包装器。链接。在indexOf方法中，有一个O(n)的操作。（这里只是部分内容）

 for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                    return i;

总体来说，这是一个

O(n^2)

在removeAll中的操作

选项2 < HashSet >：以前我在这里写了一些东西，但似乎在某个地方我是错误的，所以删除了它。最好向专家寻求关于哈希集的建议。我不确定在你的情况下是否哈希映射将是更好的解决方案。所以我提出另一种解决方案

选项3 < 我的建议 您可以尝试 >：

步骤1：如果您的数据已排序，则无需此步骤，否则对要减去的列表进行排序

步骤2：对于未排序列表的每个元素，在第二个列表中运行二进制搜索

步骤3：如果没有找到匹配，则存储在另一个结果列表中，但如果找到匹配，则不添加

步骤4：结果列表是您的最终答案

选项3的成本：

步骤1：如果未排序，需要O(nlogn)时间

步骤2：时间复杂度为O(nlogn)。

步骤3：空间复杂度为O(n)。

**

所以总体时间复杂度为O(nlogn)，空间复杂度为O(n)，保留HTML，不解释。

**

- stinepike

Answer 5

如果需要列表，您可以选择LinkedList。在您的情况下，正如@Chris所说，ArrayList实现将移动每个删除中的所有元素。

使用LinkedList，您将获得更好的随机添加/删除性能。请参见此post。

- Igor Rodriguez