python - Objective-C 中非常慢的两个和解决方案的变体

Question

我正在学习算法设计和分析类(class)，并给出了编程问题，这是两个和问题的变体:

输入是一个包含 100 万个正整数和负整数的数组。计算 [-10000,10000](含)区间内目标值 t 的个数，使得输入文件中存在满足 x+y=t 的不同数字 x,y。

我已经在 Objective-C 中编写了一个解决方案，它可以针对较小的测试用例正确解决问题:

+ (BOOL)pairExistsForSum:(NSInteger)t dictionary:(NSDictionary *)dictionary
{
    __block BOOL exists = NO;

    [dictionary enumerateKeysAndObjectsUsingBlock:^(NSString *key, NSNumber *x, BOOL *stop) {

        NSInteger y = t - x.integerValue;
        NSString *yKey = [NSString stringWithFormat:@"%li", y];

        if (y != x.integerValue && dictionary[yKey]) {
            exists = YES;
            *stop = YES;
        }
    }];

    return exists;
}

+ (NSInteger)twoSumProblem:(NSArray <NSNumber *> *)array interval:(NSInteger)min max:(NSInteger)max
{
    NSDictionary *dictionary = [self generateDictionaryOfValuesWithNumbersArray:array];
    NSInteger uniquePairs = 0;

    for (NSInteger i = min; i <= max; i++) {
        uniquePairs += [self pairExistsForSum:i dictionary:dictionary];
    }

    return uniquePairs;
}

问题是 pairExistsForSum 的每次迭代都需要 2 秒多一点的时间才能完成，这意味着整个过程将需要数小时才能完成。

我尝试了一些替代方法，例如:

1) 对输入进行排序并将其分为正负数组并使用二分查找查找补加数

2) 将外层for循环改为只遍历0-10000范围，然后同时搜索正负和值的加数

没有什么能足够显着地提高性能，甚至不能将其分解为子问题并在并发线程上运行每个子问题。

我终于找到了某人的 python 解决方案，如下所示:

import time
import bisect

a = []
with open('2sum.txt', 'r') as f:
    for line in f:
        a.append(int(line.strip()))
a.sort()

ret = set()
for x in a:
    lower = bisect.bisect_left(a, -10000 - x)
    upper = bisect.bisect_right(a, 10000 - x)
    for y in a[lower:upper]:
        if x != y and x + y not in ret:
            ret.add(x + y)
print len(ret)

此解决方案可在几秒钟或更短时间内运行。我不熟悉 Python，但我相信这是使用二进制搜索，而不是利用输入数组的数据来提高速度。虽然我希望 python 代码比 Objective C 运行得更快，但这些解决方案之间的差异是巨大的。

我的问题如下:

1. 关于这两种解决方案之间的差异，我是否遗漏了什么可以解释如此巨大的性能差异？
2. 就我可以做些什么来在相当长的时间内(即不到一小时)在 Objective c 中运行而言，我是否忽略了什么？

(有人在这里问了同样的问题:Variant of the 2-sum algorithm with a range of sums 但没有给出答案，我相信我的更具体)。

非常感谢。

Answer 1

Is there something I'm missing about the difference between these two solutions that would explain such a vast difference in performance?

您正在“倒退”地解决问题。您从 t 开始，然后搜索与其相加的一对。想想您的输入仅包含两个数字的极端示例，您将执行 200001 次测试以查看总和是否是 [-100000, 100000] 范围内的可能值之一。

Python 通过选择 x 和 y 来驱动，因此只考虑数据可以产生的实际 t 值。此外，通过对数据进行排序，该解决方案能够仅考虑总和为范围内值的那些 x、y 对。

Is there something I'm overlooking as far as what I can do to make this run in a respectable amount of time (i.e. under an hour) in Objective c?

是的，只需实现与 Python 解决方案相同的算法即可。快速 Google 会生成对分函数的规范及其 Python 源代码。您会发现它们是简单的二进制搜索，您可以轻松实现。但是，为了提高速度，您可能希望尝试使用标准的 Objective-C 方法。 NSArray 没有直接的等价物，但是看看 indexOfObject:inSortedRange:options:usingComparator: 并考虑一下“滥用”比较器对等值的定义...

HTH