多線程程序算法

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不是一個原子操作，所以你會得到錯誤的結果，當所有線程執行並行。您必須使用原子增量操作，或者讓所有線程計算自己的分數，並在所有線程完成後添加所有線程的值。