2

我有两组数字，每组都在我的 Python 脚本的列表中。对于第一个列表中的每个数字，我需要查看第二个列表中的任何数字是否大于它。我只需要 n2 大于 n1 的次数。（例如，如果numset1is[7,2]和numset2is [6,9]，我只需要 3）现在我正在这样做 - 遍历每个 n1 并检查每个 n2 是否大于它：

possibilities = [(n1<n2) for n1 in numset1 for n2 in numset2]
numPossibilities = sum(possibilities)

目前这是我脚本中最慢的部分，尤其是在处理较大的数据集（包含数千个数字的 numset1 和 numset2 ）时。我确信有一些方法可以提高效率，我只是不确定如何。

4

3 回答 3

3

排序numset2然后迭代，numset1但使用二进制搜索numset2，例如使用 bisect 模块：http ://docs.python.org/2/library/bisect.html

import bisect
# your code here
numset2.sort()
L = len(numset2)
numPossibilities = sum([bisect.bisect_right(numset2,n1) < L for n1 in numset1])

另请注意，您的原始代码不会计算您在第二句中要求的内容 - 对于 中的每个元素numset1，它总结了中有多少元素numset2大于该元素，而不是是否存在与标准匹配的元素。

要匹配您的原始代码，请执行以下操作：

numPossibilities = sum([L - bisect.bisect_right(numset2,n1) for n1 in numset1])
于 2012-12-07T00:51:02.510 回答
2

您的问题是您必须遍历 的每个组合(n1, n2)，并且存在组合，当并且仅相当大len(numset1) * len(numset2)时，它们变得非常大。numset1numset2

换句话说，你的算法的运行时间是 O(n^2) （如果len(numset1)大约等于len(numset2)。让我们让运行时间更快。:-)

如果我们对列表进行排序，这将变得容易得多。所以让我们排序numset1和numset2。

>>> numset1.sort()
>>> numset2.sort()

现在，比较numset1(call it) 的最小元素和 (call it )n1的最小元素。如果较小，那么我们知道有比它大的元素。如果更小，我们知道其中没有任何元素比它小。numset2n2n1len(numset2)numset2n2numset1

现在，我们不想实际删除列表开头的元素，因为这是对 Python 列表的 O(n) 操作。因此，让我们跟踪我们在每个列表中的位置并迭代。

>>> n1_idx, n2_idx, accumulator = 0, 0, 0
>>> while n1_idx < len(numset1) and n2_idx < len(numset2):
        if numset1[n1_idx] < numset2[n2_idx]:
            accumulator += len(numset2) - n2_idx
            n1_idx += 1
        else:
            n2_idx += 1

在此操作结束时，我们花费了 O(nlog(n)) 时间对列表进行排序，并花费了 O(n) 时间进行迭代，因此我们的整体运行时复杂度为 O(nlog(n))。

那，并且accumulator有对的数量(n1, n2)where n1 < n2。

于 2012-12-07T01:03:26.477 回答
0

这应该是一个非常有效的实现：

def get_possibilities(numset1, numset2):
    sortset1 = sorted(numset1)
    sortset2 = sorted(numset2)
    total = 0
    i2 = 0
    for i1, n1 in enumerate(sortset1, 1):
        while sortset2[i2] <= n1:
            i2 += 1
            if i2 >= len(sortset2):
                # reached end of i2, so just return total now
                return total
            # current from sortset2 is greater than from sortset1 so far
            total += i1
    # all remaining elements of sortset2 greater than all elements of sortset1
    total += (len(sortset2) - i2 - 1) * len(sortset1)
    return total

这仅对每个集合进行一次迭代，它通过在运行之前对集合进行排序来完成。这允许一些改进的逻辑，因为如果sortset2at indexi2中的元素大于sortset1at index 的元素i1，那么它也大于sortset1at 早期索引中的所有元素。

于 2012-12-07T01:17:17.607 回答