目标C中二和解极慢的变量

Question

我正在上一门算法设计和分析课程，我得到了一个编程问题，它是两个和问题的一个变体：

输入是一个100万个整数的数组，包括正整数和负整数。 计算区间[-1000010000]（含）内的目标值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解决方案：

^{pr2}$

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

我的问题如下：

1. 这两种解决方案之间的巨大差异？在
2. 在目标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将生成bisect函数的规范和Python源代码。你会发现它们是很容易实现的简单的二进制搜索。不过，为了提高速度，您可能希望尝试使用标准的Objective-C方法。NSArray没有直接的等价物，但是看看{}并考虑一下“滥用”比较器的相等值定义。。。在

高温