我已经编写了一个小型实用程序，用于识别iTunes中的重复曲目。 轨道的实际匹配需要很长时间，我想优化它。 我将轨道数据存储在NSMutableDictionary中，该数据存储单个轨道数据 由trackID键入的NSMutableDictionaries。这些单独的轨道字典有 至少以下键：（以毫秒为#### ####）匹配重复项的优化算法
- 的TrackID
- 名称
- 艺术家
- 时间
要确定是否有任何曲目相互匹配，我必须检查：
- 如果两个轨道的时间是彼此
- 名称的5秒内匹配
- 艺术家匹配
较慢的方式为我做的是使用两个for循环：
-(void)findDuplicateTracks {
NSArray *allTracks = [tracks allValues];
BOOL isMatch = NO;
int numMatches = 0;
// outer loop
NSMutableDictionary *track = nil;
NSMutableDictionary *otherTrack = nil;
for (int i = 0; i < [allTracks count]; i++) {
track = [allTracks objectAtIndex:i];
NSDictionary *summary = nil;
if (![claimedTracks containsObject:track]) {
NSAutoreleasePool *aPool = [[NSAutoreleasePool alloc] init];
NSUInteger duration1 = (NSUInteger) [track objectForKey:kTotalTime];
NSString *nName = [track objectForKey:knName];
NSString *nArtist = [track objectForKey:knArtist];
// inner loop - no need to check tracks that have
// already appeared in i
for (int j = i + 1; j < [allTracks count]; j++) {
otherTrack = [allTracks objectAtIndex:j];
if (![claimedTracks containsObject:otherTrack]) {
NSUInteger duration2 = (NSUInteger)[otherTrack objectForKey:kTotalTime];
// duration check
isMatch = (abs(duration1 - duration2) < kDurationThreshold);
// match name
if (isMatch) {
NSString *onName = [otherTrack objectForKey:knName];
isMatch = [nName isEqualToString:onName];
}
// match artist
if (isMatch) {
NSString *onArtist = [otherTrack objectForKey:knArtist];
isMatch = [nArtist isEqualToString:onArtist];
}
// save match data
if (isMatch) {
++numMatches;
// claim both tracks
[claimedTracks addObject:track];
[claimedTracks addObject:otherTrack];
if (![summary isMemberOfClass:[NSDictionary class]]) {
[track setObject:[NSNumber numberWithBool:NO] forKey:@"willDelete"];
summary = [self dictionarySummaryForTrack:track];
}
[otherTrack setObject:[NSNumber numberWithBool:NO] forKey:@"willDelete"];
[[summary objectForKey:kMatches]
addObject:otherTrack];
}
}
}
[aPool drain];
}
}
}
对于大型音乐库，这变得非常缓慢，并且仅使用1 处理器。一个推荐的优化是使用块并且处理批次（100个轨道）的轨道 。我试过了。如果我的代码 最初需要9个小时才能运行，现在需要两个小时才能完成四核。这仍然太慢。但是（在这里谈论我的薪酬等级） 也许有一种方法可以将我需要的所有值存储在“适合堆栈”的C结构中，然后我不必从较慢的内存中获取值。这对我来说似乎太低级了，但我愿意学习，如果我有一个例子。
顺便说一句，我在仪器中对此进行了描述，[NSCFSet member:]占用了CPU时间的86.6％的百分之 。
然后，我想我应该提取所有的持续时间到一个排序的数组，所以我不会有 查找字典中的持续时间值。我认为这是一个很好的想法，但是当我开始实施它时，我想知道如何确定 最佳批量大小。
如果我有以下持续时间：
2 2 3 4 5 6 6 16 17 38 59 Duration
0 1 2 3 4 5 6 7 8 9 10 Index
然后，只需通过遍历数组了，我知道，要找到在索引0匹配歌曲的 轨道，我只需要它比较对歌曲 直到指数6.这很好，我有我的第一批。但现在我必须 从索引1处重新开始才发现它的批次也应停止在 索引6并排除索引0.我假设我在这里浪费了大量的 处理周期，以确定批次应该是什么/持续时间 匹配。这看起来像是一个“集合”问题，但我在Intro to Algorithms类中并没有做太多的工作。
我的问题是：
1）什么是最有效的方法来识别匹配的轨道？它是 与上述内容类似吗？它是否使用略高于我的知识水平的不相交和[统一的]集操作？是否使用NSArray过滤数组？ ？是否有一个在线资源 描述这个问题和解决方案？
我愿意以任何方式重构轨道字典 （数据结构）最有效。我起初以为我需要 通过TrackID执行许多查找，但事实并非如此。
2）有没有更有效的方法来解决这个问题？摇滚明星如何从第1段转到优化的解决方案？
...我已经寻找答案，时间比我愿意承认，发现 这些有趣的，但无益答案：
Find all duplicates and missing values in a sorted array
感谢您的帮助，您可以提供， 兰斯
这些都是很好的建议约拿。我会在这个周末编写一些代码并在这里发布结果。 – Lance 2011-05-06 17:52:01