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

Question

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

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

我在 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 更快，但这些解决方案之间的差异是巨大的。

我的问题如下：

关于这两种解决方案之间的差异，我是否遗漏了什么可以解释如此巨大的性能差异？
我能做些什么来在 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?

您正在解决问题 "backwards"。您从 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: 并稍微考虑一下 "abusing" 比较器对等值的定义...

HTH

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

Variant Of Two Sum Solution Extremely Slow in Objective C

python

objective-c

algorithm

hashtable

big-o