Я написал небольшую служебную программу, которая идентифицирует дубликаты треков в iTunes.Фактическое сопоставление треков занимает много времени, и я бы хотел его оптимизировать.Я храню данные трека в NSMutableDictionary, который хранит отдельные данные трека в NSMutableDictionaries с ключом trackID.Эти отдельные словари треков имеют по крайней мере следующие ключи:
- TrackID
- Имя
- Artist
- Продолжительность (в милли ####.####)
Чтобы определить, соответствуют ли какие-либо треки друг другу, я должен проверить:
- Если продолжительность двух треков не превышает 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 часов, то теперь на четырехъядерном процессоре это занимает около 2 часов.Это все еще слишком медленно.Но (говоря выше о моей плате), возможно, есть способ сохранить все значения, которые мне нужны, в структуре C, которая «помещается в стек», и тогда мне не придется извлекать значения из более медленной памяти.Это кажется мне слишком низким уровнем, но я хочу узнать, есть ли у меня пример.
Кстати, я профилировал это в инструментах, и [NSCFSet member:] занимает 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. Я предполагаю, что здесь я трачу много циклов обработки, определяя, какой пакет должен быть / продолжительностьМатчи.Это казалось «установленной» проблемой, но мы не делали этого в моем классе «Введение в алгоритмы».
Мои вопросы:
1) Какой самый эффективный способ определить совпадающие треки?Это что-то похожее на то, что выше?Используются ли несвязанные и [унифицированные] операции над множествами, которые немного выше моего уровня знаний?Это фильтрация массивов с помощью NSArray?Есть ли онлайн-ресурс, описывающий эту проблему и решение?
Я хочу реструктурировать словарь треков любым способом (структура данных), который наиболее эффективен.Сначала я подумал, что мне нужно выполнить много поисков по TrackID, но это уже не так.
2) Есть ли более эффективный способ решения этой проблемы?Как вы, рок-звезды, переходите от пункта 1 к оптимизированному решению?
Я искал ответ дольше, чем хотел бы признаться, и нашел следующие интересные, но бесполезные ответы:
найти дубликаты
Найти все дубликаты и пропущенные значения в отсортированном массиве
Спасибо за любую помощь, которую вы можете предоставить, Лэнс