目标C中两和解的变体极其缓慢

Question

我选了一门算法设计与分析的课程，题目是编程问题，这是两个和问题的变体:

输入是一个包含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中，是否有一些东西我忽略了，我可以做些什么来使这个运行在可观的时间量(即在一个小时内)?

(有人在这里问同样的问题:2和算法的变体，有一系列的和，但没有给出答案，我相信我的更具体)。

许多谢谢。

Answer 1

这两种解决方案之间的差异是否有什么我遗漏的东西，可以解释性能上的巨大差异?

你是在"倒过来"解决问题。从t开始，然后搜索和它相同的一对。考虑输入只包含两个数字的极端示例，您将执行200001测试，以查看总和是否为[-100000,100000]范围内可能的值之一。

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

在Objective c中，是否有一些东西我忽略了，我可以做些什么来使这个运行在可观的时间量(即在一个小时内)?

是的，只需实现与Python解决方案相同的算法。快速Google一下就能找到bisect函数的规范和它们的Python源代码。你会发现它们是很简单的二进制搜索，你可以很容易地实现。然而，为了提高速度，你可能希望尝试使用标准的Objective-C方法。NSArray没有直接的等价物，但看看indexOfObject:inSortedRange:options:usingComparator:，想想"滥用"比较器对等值的定义……

HTH