c# - 改进 O(n^2) 算法

Question

我有以下代码:

var keywordItems = adwordsService
  .ParseReport(report)
  .Where(e => e.Keyword.IndexOf('+') == -1);

var keywordTranslations = keywordTranslationService
  .GetKeywordTranslationsByClient(id);

model.KeywordItems = keywordItems
    .Where(e =>
    {
        int lastUnderscore = e.CampaignName.LastIndexOf('_');
        var identifer = e.CampaignName.Substring(lastUnderscore + 1);

        var translation = keywordTranslations
          .FirstOrDefault(t => t.translation == e.Keyword && 
                               t.LocalCombination_id == identifer);

        return translation == null;
    })
    .OrderBy(e => e.Keyword);

它接收一个数组，然后根据这些元素是否已经出现过过滤这些元素中的每一个。

但是，这运行起来很慢，因为有很多新元素，所以我希望有人能指出我在这种情况下使用的最佳算法的正确方向。

Answer 1

简单的连接就可以完成这项工作 - 它使用 hashset 在集合之间进行匹配，这为您提供 O(1) 的搜索操作:

from k in keywordItems
let identifer = k.CampaignName.Substring(k.CampaignName.LastIndexOf('_') + 1)
join t in keywordTranslations on
    new { k.Keyword, Id = identifer } equals
    new { Keyword = t.translation, Id = t.LocalCombination_id } into g
where !g.Any()
orderby k.Keyword
select k

要进一步提高性能，您可以将 identifier 提取直接移至 key 创建。因此，您将省略引入新的范围变量。