2

定义：如果数组A(a1,a2,...,an)大小相等且>=对于每个从到B(b1,b2,...bn)a_i>=b_ii1n.

例如：

[1,2,3] >= [1,2,0]
[1,2,0] not comparable with [1,0,2]
[1,0,2] >= [1,0,0]

我有一个列表，其中包含大量此类数组（大约 10000，但可以更大）。数组的元素是正整数。我需要从这个列表中删除所有比至少一个其他数组大的数组。换句话说：如果存在这样B的，A >= B则删除A。

这是我目前的O(n^2)方法，非常慢。我只是将每个数组与所有其他数组进行比较，如果它更大，则将其删除。有什么方法可以加快速度。

import numpy as np
import time
import random

def filter_minimal(lst):
    n = len(lst)
    to_delete = set()
    for i in xrange(n-1):
        if i in to_delete:
            continue
        for j in xrange(i+1,n):
            if j in to_delete: continue
            if all(lst[i]>=lst[j]):
                to_delete.add(i)
                break
            elif all(lst[i]<=lst[j]):
                to_delete.add(j)
    return [lst[i] for i in xrange(len(lst)) if i not in to_delete]


def test(number_of_arrays,size):
    x = map(np.array,[[random.randrange(0,10) for _ in xrange(size)] for i in xrange(number_of_arrays)])
    return filter_minimal(x)

a = time.time()
result = test(400,10)
print time.time()-a
print len(result)

PS 我注意到使用numpy.all而不是内置 pythonall会大大减慢程序的速度。可能是什么原因？

4

2 回答 2

1

可能不完全符合您的要求，但这应该可以帮助您入门。

import numpy as np
import time
import random

def compare(x,y):
    #Reshape x to a higher dimensional array
    compare_array=x.reshape(-1,1,x.shape[-1])
    #You can now compare every x with every y element wise simultaneously
    mask=(y>=compare_array)
    #Create a mask that first ensures that all elements of y are greater then x and
    #then ensure that this is the case at least once.
    mask=np.any(np.all(mask,axis=-1),axis=-1)
    #Places this mask on x
    return x[mask]

def test(number_of_arrays,size,maxval):
    #Create arrays of size (number_of_arrays,size) with maximum value maxval.
    x = np.random.randint(maxval, size=(number_of_arrays,size))
    y=  np.random.randint(maxval, size=(number_of_arrays,size))
    return compare(x,y)

print test(50,10,20)
于 2013-02-20T15:07:21.870 回答
0

首先，我们需要仔细检查目标。我们是否删除了任何大于其他数组的任何数组，甚至是已删除的数组？例如，如果 A > B and C > A and B=C，那么我们需要只删除 A 还是同时删除 A 和 C？如果我们只需要删除 INCOMPATIBLE 数组，那么这是一个更难的问题。这是一个非常困难的问题，因为这组数组的不同分区可能是兼容的，因此您遇到了找到最大有效分区的问题。

假设问题很简单，定义问题的更好方法是您希望保留所有具有至少一个元素的数组<所有其他数组中的相应元素。（在hard问题中，是其他KEPT数组中对应的元素，这个我们不考虑。）

阶段1

为了解决这个问题，你要做的是将数组排列成列，然后对每一行进行排序，同时保持数组的键和每个数组行到位置的映射（位置列表）。例如，您可能会在第 1 阶段得到如下结果：

第 1 行：BCDAE
第 2 行：CAEBD
第 3 行：EDBCA

这意味着对于第一个元素（第 1 行），数组 B 的值 >= C、C >= D 等。

现在，对该矩阵的最后一列进行排序和迭代（示例中为 {EDA}）。对于每个项目，检查元素是否小于其行中的前一个元素。例如，在第 1 行中，您将检查是否 E < A。如果为真，则立即返回并保留结果。例如，如果 E_row1 < A_row1 那么您可以保留数组 E。只有当行中的值相等时，您才需要进行第 2 阶段测试（见下文）。

在显示的示例中，您将保留 E、D、A（只要它们通过了上述测试）。

第二阶段

剩下 B 和 C。对每个位置列表进行排序。例如，这会告诉你 B 的最小位置是第 2 行。现在直接比较 B 和它下面的最小行中的每个数组，这里是第 2 行。这里只有一个这样的数组 D。 B 和 D 之间的直接比较。这表明第 3 行中 B < D，因此 B 与 D 兼容。如果该项目与低于其最小位置的每个数组兼容，则保留它。我们保留 B。

现在我们对 C 做同样的事情。在 C 的情况下，我们只需要与 A 进行一次直接比较。C 支配 A，所以我们不保留 C。

请注意，除了测试最后一列中没有出现的项目之外，我们还需要测试阶段 1 中相等的项目。例如，假设第 1 行中的 D=A=E。在这种情况下，我们必须进行直接比较对于最后一列中涉及数组的每个等式。因此，在这种情况下，我们直接将 E 与 A 和 E 与 D 进行比较。这表明 E 支配 D，因此不保留 E。

最终结果是我们保留 A、B 和 D。C 和 E 被丢弃。

该算法的整体性能为阶段 1 的 n2*log n + { n 下限，n * log n - 上限 } 在阶段 2。因此，最大运行时间为 n2*log n + nlogn，最小运行时间为 n2logn + n。请注意，您的算法的运行时间是 n 立方 n3。由于您比较每个矩阵（n * n）并且每个比较是n个元素比较= n * n * n。

一般来说，这将比蛮力方法快得多。大部分时间将花费在对原始矩阵进行排序上，这是或多或少不可避免的任务。请注意，您可以通过使用优先级队列而不是排序来改进我的算法，但生成的算法会复杂得多。

于 2013-02-20T19:38:59.987 回答