11

我想减去两个 ArrayList，这样我就可以拥有不在另一个列表中的孩子。

我这样做：

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

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

问题是这两个列表都包含 5000childs 并且在我的 androidphone 上需要将近 4 秒。

有没有快速的方法来做到这一点？使用集合更快吗？（我在列表中没有重复值）

我开发了一个安卓应用

4

5 回答 5

7

除非您需要保持顺序，否则请使用 HashSet 而不是 ArrayList。

删除一个元素需要扫描完整的 List 以获取列表实现，相比之下，HashSet 只是计算哈希码，然后识别目标桶。

于 2013-03-12T20:36:17.833 回答
1

套装应该更快。现在，它基本上是在做一个 n^2 循环。它遍历 removeIDs 中的每个元素并检查该 id 是否在下载的IDs 中，这需要搜索整个列表。如果将下载的 ID 存储在更快的搜索中，比如 HashSet，这会更快，并且变成 O(n) 而不是 O(n^2)。Collections API 中可能还有更快的速度，但我不知道。

如果您需要保留排序，您可以使用 LinkedHashSet 而不是普通的 HashSet，但它会增加一些偷听的内存和插入/删除元素的一些性能损失。

于 2013-03-12T20:37:53.480 回答
1

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

于 2013-03-12T20:39:43.930 回答
1

首先，我为冗长的回答道歉。如果我在任何时候错了，随时欢迎您纠正我。在这里，我比较了解决解决方案的一些选项

选项 1 < 数组列表 >：

在您的代码中，您使用了该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 >： 以前我在这里写过一些东西，但似乎我在某些时候错了，所以删除它。最好听取专家关于 Hashset 的建议。我不确定在你的情况下 hashmap 是否会是一个更好的解决方案。所以我提出另一种解决方案

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

第 1 步：如果您的数据已排序，则不需要此步骤，否则对要减去的列表进行排序（第二个列表）

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

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

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

选项 3 的成本：

第1步：如果没有排序O(nlogn)时间

第二步： O(nlogn)时间

第三步： O(n)空间

**

所以总体 O(nlogn) 时间和 O(n) 空间

**

于 2013-03-13T04:09:31.407 回答
0

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

使用 LinkedList，您将获得更好的随机添加/删除性能。看到这个帖子。

于 2013-03-12T21:13:20.437 回答