0

私はプロジェクトオイラー＃22に取り組んでおり、約9.6ミリ秒でソリューションを取得しました。これが私が持っているものです：

#import <Foundation/Foundation.h>

NSUInteger valueOfName(NSString *name) {
    NSUInteger sum = 0;
    for (int i = 0; i < [name length]; i++) {
        unichar character = [name characterAtIndex:i];
        sum += (character - 64);
    }
    return sum;
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        CFAbsoluteTime currentTime = CFAbsoluteTimeGetCurrent();
        NSMutableString *names = [NSMutableString stringWithContentsOfFile:[@"~/Documents/Developer/Project Euler/Problem22/names.txt" stringByExpandingTildeInPath] encoding:NSASCIIStringEncoding error:nil];
        CFAbsoluteTime diskIOTime = CFAbsoluteTimeGetCurrent();
        [names replaceOccurrencesOfString:@"\"" withString:@"" options:NSLiteralSearch range:NSMakeRange(0, [names length])];
        NSArray *namesArray = [names componentsSeparatedByString:@","];
        namesArray = [namesArray sortedArrayUsingSelector:@selector(compare:)];
        // Marker 1
            int totalScore = 0;
        for (int i = 0; i < [namesArray count]; i++) {
            NSString *name = namesArray[i];
            NSUInteger sum = valueOfName(name);
            NSUInteger position = i + 1;
            totalScore += (sum * position);
        }
        // Marker 2
        CFAbsoluteTime endTime = CFAbsoluteTimeGetCurrent();
        double timeDiff = (endTime - currentTime) * 1000;
        printf("Total score: %d\n", totalScore);
        printf("Disk IO Time: %fms\tTime: %fms\n", ((diskIOTime - currentTime) * 1000), timeDiff);
    }
    return 0;
}

良い時期ですが、複数のスレッドを使用して高速化する方法を考え始めました。クアッドコアCPUを使用すると、理論的には、名前の4分の1を別々のスレッドで処理し、そこから合計を取得できるはずです。これが私が試したことです（上記のマーカー間のコードを置き換えます）：

__block int totalScore = 0;
        int quarterArray = [namesArray count] /4 ;
        typedef void(^WordScoreBlock)(void);
        WordScoreBlock block1 = ^{
            for (int i = 0; i < quarterArray; i++) {
                NSString *name = namesArray[i];
                NSUInteger sum = valueOfName(name);
                NSUInteger position = i + 1;
                totalScore += (sum * position);
            }
            printf("Total score block 1: %d\n", totalScore);
        };
        WordScoreBlock block2 = ^{
            for (int i = quarterArray; i < (quarterArray * 2); i++) {
                NSString *name = namesArray[i];
                NSUInteger sum = valueOfName(name);
                NSUInteger position = i + 1;
                totalScore += (sum * position);
            }
        };
        WordScoreBlock block3 = ^{
            for (int i = (quarterArray * 2); i < (quarterArray * 3); i++) {
                NSString *name = namesArray[i];
                NSUInteger sum = valueOfName(name);
                NSUInteger position = i + 1;
                totalScore += (sum * position);
            }
        };
        WordScoreBlock block4 = ^{
            for (int i = (quarterArray * 3); i < [namesArray count]; i++) {
                NSString *name = namesArray[i];
                NSUInteger sum = valueOfName(name);
                NSUInteger position = i + 1;
                totalScore += (sum * position);
            }
        };
        dispatch_queue_t processQueue = dispatch_queue_create("Euler22", NULL);
        dispatch_async(processQueue, block1);
        dispatch_async(processQueue, block2);
        dispatch_async(processQueue, block3);
        dispatch_async(processQueue, block4);

ただし、結果は0になりますが、時間は約1ミリ秒速くなります。

  • このマルチスレッドアプローチは可能ですか？
  • もしそうなら、私はそれをどのように実装しますか？
4

2 に答える 2

2

最初に並行キューを作成して、ブロックが並行して実行されるようにします。

dispatch_queue_t processQueue = dispatch_queue_create("Euler22", DISPATCH_QUEUE_CONCURRENT);

次に、ディスパッチグループを作成し、そのグループにすべてのブロックを追加して、グループが終了するのを待ちます。

dispatch_group_t group = dispatch_group_create();
dispatch_group_async(group, processQueue, block1);
dispatch_group_async(group, processQueue, block2);
dispatch_group_async(group, processQueue, block3);
dispatch_group_async(group, processQueue, block4);
dispatch_group_wait(group, DISPATCH_TIME_FOREVER);

最後に、toの追加totalScoreは不可分操作ではないため、すべてのスレッドが並列実行されると間違った結果が得られます。アトミックインクリメント操作を使用するか、すべてのスレッドに独自のスコアを計算させ、終了後にすべてのスレッドから値を追加する必要があります。

于 2012-08-04T22:48:58.360 に答える
1

タイミングの一部としてファイルをロードしますか？

また、それらを同時に実行したい場合は、並行キューを使用する必要があります。シリアルキューを作成しているので、すべてのブロックが次々に実行されます。

// Create a concurrent queue
dispatch_queue_t processQueue = dispatch_queue_create("Euler22", DISPATCH_QUEUE_CONCURRENT);

または、* dispatch_get_global_queue *を呼び出して、並行キューを要求することもできます。

これで、タスクを追加すると、GCDはそれらを使用可能なワーカースレッドにファームアウトします。

タスクが実行されたので、タスクが完了するのを待つ必要があります。これはいくつかの方法で達成できます。複数のキューを使用している場合は、ディスパッチグループがおそらく最善のアプローチです。

ただし、同じキューを使用して、すべての* dispatch_sync *（）呼び出しの後で、前のすべてのブロックが完了するまで待機してから実行するバリアブロックを配置できます...

dispatch_barrier_async(processQueue, ^{
    // We know that all previously enqueued blocks have finished, even if running
    // concurrently.  So, we can process the final results of those computations.
});

ただし、この場合、1つのキューを使用しています（同時ではありますが、同時に複数のタスクを実行します...キューに入れられた順序でキューからプルします）。

おそらく最も簡単なのは、* dispatch_apply *を使用することです。これは、まさにこの目的のために設計されているためです。同じブロックを複数回呼び出し、インデックスを渡します。ブロックはインデックスを取得し、それを使用してデータ配列を分割できます。

編集

OK、あなたの特定の問題に適用を使用する試み（例としてあなたのブロックコードを使用して...私はそれがあなたが望むことをすることを仮定します）。注意してください、私はそれを入力しただけなので（ここでも構文は強調表示されていません）、コンパイルするために少し試してみる必要があるかもしれません...しかしそれはあなたに一般的な考えを与えるはずです）。

// You need to separate both source and destination data.
size_t const numChunks = 4; // number of concurrent chunks to execute
__block int scores[numChunks];
size_t dataLen = [namesArray count];
size_t chunkSize = dataLen / numChunks; // amount of data to process in each chunk
dispatch_queue_t queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0);
dispatch_apply(numChunks, queue, ^(size_t index) {
    // GCD will schedule these tasks concurrently as best as possible.
    // You know the current iteration index from the parameter.
    size_t beginIndex = index * chunkSize; // beginning of chunk
    size_t endIndex = beginIndex + chunkSize; // one past end of chunk
    if (endIndex > dataLen) endIndex = dataLen;
    int score = 0;
    for (size_t i = beginIndex; i < endIndex; ++i) {
        NSString *name = namesArray[i];
        NSUInteger sum = valueOfName(name);
        NSUInteger position = i + 1;
        score += (sum * position);
    }
    scores[index] = score;
});

// Since dispatch_apply waits for all bucks to complete, by the time you
// get here you know that all the blocks are done.  If your result is just
// a sum of all the individual answers, sum them up now.
int totalScore = 0;
for (size_t i = 0; i < numChunks; ++i) {
    totalScore += scores[i];
}

うまくいけば、それは理にかなっています。動作するようになったら教えてください。

さて、本当に数学のパフォーマンスが必要な状況に陥った場合は、Accelerateフレームワークを調べる必要があります。一言。素晴らしい。

于 2012-08-04T22:58:46.217 に答える