多线程程序算法

Question

我正在研究Project Euler #22，并在9.6ms左右得到了我的解决方案。下面是我有：

#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，理论上我应该能够在单独的线程上处理四分之一的名称，然后从那里获得总数。这是我试过（更换上面的标记之间的代码）：

__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的结果，但我的时间是大约一毫秒更快。

• 这是多线程方法吗？
• 如果是这样，我将如何实现它？

Answer 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. 
}); 

然而，在这种情况下，我们使用一个队列（尽管是并发的，它将同时执行多个任务，但它会按照它们排队的顺序排队）。

可能最简单的事情是使用* 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框架。一个词。真棒。

Answer 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); 

最后：添加到totalScore不是一个原子操作，所以你会得到错误的结果，当所有线程执行并行。您必须使用原子增量操作，或者让所有线程计算自己的分数，并在所有线程完成后添加所有线程的值。