1

我编写了一个小型实用程序来识别 iTunes 中的重复曲目。曲目的实际匹配需要很长时间，我想对其进行优化。我将轨道数据存储在 NSMutableDictionary 中，该 NSMutableDictionary 将单个轨道数据存储在由 trackID 键入的 NSMutableDictionaries 中。这些单独的曲目词典至少具有以下键：

  • 跟踪ID
  • 姓名
  • 艺术家
  • 持续时间（以毫秒为单位####.####）

要确定是否有任何曲目相互匹配，我必须检查：

  • 如果两首曲目的时长在 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 结构中，然后我就不必从较慢的内存中获取值。这对我来说似乎太低级了，但如果我有一个例子，我愿意学习。

顺便说一句，我在 Instruments 中对此进行了分析，[NSCFSet member:]占用了 86.6% 的 CPU 时间。

然后我想我应该将所有持续时间提取到一个排序数组中，这样我就不必在字典中查找持续时间值。我认为这是一个好主意，但是当我开始实施它时，我想知道如何确定最佳批量大小。

如果我有以下持续时间：

    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 段到优化的解决方案？

我寻找答案的时间比我愿意承认的要长，并发现了这些有趣但无益的答案：

查找重复项

查找排序数组中的所有重复值和缺失值

感谢您提供的任何帮助，兰斯

4

2 回答 2

1

有几种方法可以做到这一点，但这是我的第一个天真的猜测：

有一个可变字典。这本词典中的键是歌曲的名称。每个键的值是另一个可变字典。这个辅助可变字典的键是艺术家。每个键的值是一个可变的歌曲数组。

你最终会得到这样的东西：

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];
}

这是最坏情况的 O(n 2 ) 算法（如果每首歌曲都有相同的名称、艺术家和持续时间）。这是一个最佳情况的 O(n) 算法（如果每首歌都有不同的名称/艺术家/持续时间），实际上最终会更接近 O(n) 而不是 O(n 2 )（很可能）。

于 2011-05-04T21:47:54.097 回答
1

我的第一个想法是将一些排序的集合作为索引保存到您的字典中，这样您就可以停止进行 O(n^2) 搜索，将每个轨道与其他轨道进行比较。

如果您有按持续时间排序的 TrackID 数组，那么对于任何轨道，您都可以进行更有效的 O(log n) 二进制搜索，以查找持续时间在 5 秒容差范围内的轨道。

对于艺术家和名称，您可以存储以艺术家或曲目名称为键的字典，其值为 TrackID 数组。然后，您只需要 O(1) 查找来获取特定艺术家的曲目集，这应该可以让您非常快速地确定是否有任何可能的重复。

最后，如果您已经为 TrackID 构建了那种标题字典，那么您可以遍历它的所有键，并且仅在有多个具有相同标题的曲目时才搜索重复项。仅当有多个具有相同标题的曲目时才进行进一步比较应该消除库的很大一部分并大大减少您的搜索时间（降低到 O(n) 来构建字典，另一个 O(n) 用于最坏的情况搜索重复项仍然使您处于 O(n) 而不是您现在拥有的 O(n^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.
于 2011-05-04T21:59:21.427 回答