匹配重复项的优化算法
|
我已经编写了一个小型实用程序，用于识别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];
}
}
}
2 2 3 4 5 6 6 16 17 38 59 Duration
0 1 2 3 4 5 6 7 8 9 10 Index
没有找到相关结果
已邀请:
2 个回复
可扇胆
NSMutableArray *possibleDuplicates = [NSMutableArray array]; NSMutableDictionary *knownTitles = [NSMutableDictionary dictionary]; for (NSMutableDictionary *track in [tracks allKeys]) { if ([knownTitles objectForKey:[track objectForKey:@\"title\"]] != nil) { [possibleDuplicates addObject:track]; } else { [knownTitles addObject:[track objectForKey:@\"TrackID\"] forKey:[track objectForKey:@\"title\"]]; } } //check for duplicates of the tracks in possibleDuplicates only.犁攀富
NSArray *songs = ...; //your array of songs NSMutableDictionary *nameCache = [NSMutableDictionary dictionary]; for (Song *song in songs) { NSString *name = [song name]; NSMutableDictionary *artistCache = [nameCache objectForKey:name]; if (artistCache == nil) { artistCache = [NSMutableDictionary dictionary]; [nameCache setObject:artistCache forKey:name]; } NSString *artist = [song artist]; NSMutableArray *songCache = [artistCache objectForKey:artist]; if (songCache == nil) { songCache = [NSMutableArray array]; [artistCache setObject:songCache forKey:artist]; } for (Song *otherSong in songCache) { //these are songs that have the same name and artist NSTimeInterval myDuration = [song duration]; NSTimeInterval otherDuration = [otherSong duration]; if (fabs(myDuration - otherDuration) < 5.0f) { //name matches, artist matches, and their difference in duration is less than 5 seconds } } [songCache addObject:song]; }