多线程程序算法
我正在研究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的结果,但我的时间是大约一毫秒更快。
- 这是多线程方法吗?
- 如果是这样,我将如何实现它?
你真的想要加载文件作为时间的一部分吗?
此外,如果您想同时执行这些操作,则需要使用并发队列。您正在创建一个串行队列,因此所有的块将一个接一个地执行。
// 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框架。一个词。真棒。
'dispatch_apply()'是一个好主意,我没有想到这一点。在这个“线性流程”类型的程序中,还可以使用带有空块的同步屏障来等待完成:'dispatch_barrier_sync(processQueue,^ {})'。 – 2012-08-04 23:27:00
@MartinR是的,障碍同步在这里可能是一个更好的选择,因为它在程序结束时,以后没有别的事情可做。 – 2012-08-04 23:31:34
您将如何创建“等待所有先前块完成的障碍块”?另外,你可以提供'dispatch_apply()'的示例代码吗? – FeifanZ 2012-08-05 21:39:09
首先创建一个并发队列中,让你的块并行执行:
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
不是一个原子操作,所以你会得到错误的结果,当所有线程执行并行。您必须使用原子增量操作,或者让所有线程计算自己的分数,并在所有线程完成后添加所有线程的值。
在打印结果之前是否等待队列中的所有块完成? – 2012-08-04 22:16:59
错误...不...我怎么做(对不起,我刚进入GCD)? – FeifanZ 2012-08-04 22:35:42