我已經編寫了一個小型實用程序，用於識別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