0

我有 2 个大整数数组。我必须得到这些数组的区别（即第二个数组中的元素，而不是第一个数组中的元素，反之亦然）。我正在实现线性搜索并将差异存储在数组中。有什么方法可以让我做得更快（线性时间）？

4

6 回答 6

2

如果将一个数组放入一个散列集，然后遍历另一个数组，探测散列集，则很容易获得 O(n+m) 时间。当然，如果您的数组已排序，那么您可以直接使用 O(n+m)。

于 2012-07-23T21:09:07.820 回答
0

我会说可能，这取决于您的过度需求。您可以将列表分解为小集合，并使用线程处理每个集合，将结果组合回一个集中的池中。

虽然不是太困难，但您需要进行一些管理，以便将结果组织回正确的顺序（因为线程 2 可能在线程 1 之前完成）以及监视进程以了解它何时完成。

您可以查看执行器教程以获取更多信息

于 2012-07-23T21:11:06.760 回答
0

哈希很好，但是集合数据结构呢？

stromberg@aw50 ~ $ /usr/local/pypy-1.9/bin/pypy
Python 2.7.2 (341e1e3821ff, Jun 07 2012, 15:38:48)
[PyPy 1.9.0 with GCC 4.4.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
And now for something completely different: ``<arigato> the AI state is indeed
close''
>>>> s1 = set(range(10))
>>>> s2 = set(range(5,15))
>>>> s1
set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
>>>> s2
set([5, 6, 7, 8, 9, 10, 11, 12, 13, 14])
>>>> s1 - s2
set([0, 1, 2, 3, 4])
>>>> s2 - s1
set([10, 11, 12, 13, 14])
>>>> s1 & s2
set([8, 9, 5, 6, 7])
>>>> s1 | s2
set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14])
>>>>

我想这是一种方便的方式，并且对于同时适合内存的列表来说速度很快。

还有诸如磁盘 BTree 或布隆过滤器之类的东西。

使用 BTree，您不必将所有内容都放入内存中，并且可以像合并排序的合并步骤一样进行差分。它们基本上是一个有序的数据库表。

对于布隆过滤器，如果您需要过滤掉需要考虑的事情的数量，它们非常适合；他们是概率性的，并且可以给出诸如“这绝对不在集合中”和“这几乎可以肯定在集合中”之类的答案。布隆过滤器的主要好处是它们需要很少的内存（有时每个元素只需一位）。好的实现将允许您指定最大允许错误概率。EG，检测 *ix 硬链接几乎是布隆过滤器非常适合的集合成员资格问题 - 它们为您提供了一个简短的可能硬链接列表，之后可以快速使其 100% 准确，因为硬链接的数量往往很小，即使实际文件的数量很大。

于 2012-07-23T21:42:32.857 回答
0

你不需要任何花哨的东西。如果您的数组已排序，那么通过每个数组一次就足以获得差异。只需在每个数组中保留一个索引，如果索引指向相同的元素，则增加两个索引，否则将较低的元素添加到返回数组并增加其索引。

这是在 Go 中执行此操作的代码：http ://play.golang.org/p/VZgGWmu-aO

这个解决方案需要 O(n+m) 时间和 O(n+m) 空间，你真的不能做得比这更好。它也没有涉及哈希表的解决方案所具有的开销。

于 2012-07-23T22:00:54.070 回答
0

这是实现目标的一种直截了当的方法：

public static Set<Integer> foundInFirstButNotSecond(int[] first,
        int[] second) {
    Set<Integer> secondSet = new HashSet<Integer>(second.length);
    for (Integer i :
            second) {
        secondSet.add(i);
    }
    Set<Integer> resultSet = new HashSet<Integer>(first.length);
    for (Integer j :
            first) {
        if (!secondSet.contains(j)) {
            // Current integer from first not found in second
            resultSet.add(j);
        }
    }
    return resultSet;
}

请注意，它返回的是 Set 而不是数组，但如果更适合您，您可以轻松修改此代码以生成数组。

例如，如果您调用此代码：

public static void main(String[] args) {
    int[] first = new int[]{1, 2, 3, 4, 5, 6};
    int[] second = new int[]{5, 6, 7, 8};
    System.out.println("In first but not second: " + ArrayCompare.
            foundInFirstButNotSecond(first, second));
}

你会得到一个内容为 [1, 2, 3, 4] 的 Set。（注意 HashSet 不保证任何特定的顺序，所以你也可以得到一个无序的变化。）

于 2012-07-23T22:04:53.750 回答
0

假设这两个数组是排序的，你可以使用两个slinding指针来查找差异。时间复杂度为O(n+m)，空间O(max(n,m))。

    void set_difference(std::vector<int> & array1,std::vector<int> & array2,std::vector<int> & output ) 
{
    auto index1 =  0 ;
    auto index2 = 0 ;
    while (index1 != array1.size() & index2 != array2.size()) 
    {       //since the arrays are sorted, we can stop looking right when we find a number bigger
        while ((array1[index1] < array2[index2]) & index2 != array2.size() )  
            index2++ ;
        if (array1[index1] != array2[index2]) //array1[index1] is not array2
            output.push_back(array1[index1]);
        index1++ ;
    }
}
于 2012-07-23T23:29:46.253 回答