Objective Cの中に二つの合計ソリューションの変形が極端に遅い

Question

私は、アルゴリズムの設計と解析のコースを取っているし、2つの和問題の変種であるプログラミングの質問与えた：

を入力するの配列です正と負の100万の整数。 x + y = tを満たす入力ファイル内に別個の番号x、yが存在するように、区間[-10000,10000]（両端を含む）内の目標値tの数を計算します。

+ (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秒を少し超えるがかかることである：私は小さなテストケースのために正しく問題を解決客観Cでのソリューションを書かれている

処理には数時間かかることがあります。外側の変更）

1）入力をソートし、正と負のアレイに分割し、相補的加算

2を見つけるためにバイナリサーチを使用して：

は私のようないくつかの代替アプローチが試みforループは0〜10000の範囲をトラバースするだけで、正と負の合計値の加算値を同時に検索します

パフォーマンスを大幅に改善していません。これをサブ問題に分解したり、 tスレッド。

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に慣れていませんが、これはバイナリ検索を使用しており、速度を向上させるために入力配列のデータを利用していないと思います。私はPythonコードがObjective Cよりも高速に動作することを期待していますが、これらのソリューションの違いは非常に大きいです。

私の質問は次のとおりです。

1. は、私はパフォーマンスのように広大な違いを説明するだろうこれら二つのソリューションの違いについて欠けている何かがありますか？
2. Objective cでこれをかなりの時間（つまり1時間未満）実行させるためにできることについて、私は見落としていることがありますか？

（誰かがここで同じ質問をしました：Variant of the 2-sum algorithm with a range of sums）答えはありません。私は私の方がより具体的だと信じています。

多くのありがとうございます。

Answer 1

このような膨大なパフォーマンスの違いを説明するこれらの2つのソリューションの違いについて、私には分からないことがありますか？

問題を「後方に」解決しています。あなたはで始まり、で始まり、その合計を求めるペアを探します。2つの数値だけを含む極端な例を考えてみましょう.200001のテストを実行して、合計が[-100000、100000]の範囲の可能な値の1つであるかどうかを確認します。

ザPythonはデータによって製造することができる値が考慮されるようにのみ実際のトン、XとY選択することによって駆動されます。さらに、データをソートすることによって、解は、範囲内の値に合計するものだけを考慮することができる。x、yのペア。

Objective cでは、これをかなりの時間（つまり1時間未満）実行できるようにするために何ができるか見落としていますか？

はい、Pythonソリューションと同じアルゴリズムを実装するだけです。簡単なGoogleでは、bisect関数の仕様とPythonソースの両方を生成します。あなたは簡単に実装できる簡単なバイナリ検索であることがわかります。しかし、速度の面では、標準のObjective-Cメソッドを使用することをお勧めします。 NSArrayは...それはバイナリ検索を使用することができます

HTH