提高爲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提取的關鍵創建。因此您將省略引入新的範圍變量。

Answer 2

我建議使用哈希，例如， HashSet<T>或Dictionary<T>。提供translation以及LocalCombination_id是string類型：

HashSet<Tuple<string, int>> keywordTranslations = 
    new HashSet<Tuple<string, string>>(keywordTranslationService 
     .GetKeywordTranslationsByClient(id) 
     .Select(t => new Tuple<string, int>(t.translation, t.LocalCombination_id))); 

    model.KeywordItems = keywordItems 
    .Where(e => !keywordTranslations.Contains(new Tuple<string, string>(
     e.Keyword, 
     e.CampaignName.Substring(e.CampaignName.LastIndexOf('_') + 1)))) 
    .OrderBy(e => e.Keyword);