Verbesserung O (n^2) -Algorithmus

Question

Ich habe folgende Stück Code:

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); 

Er empfängt ein Array und filtert dann jedes dieser Elemente basierend darauf, ob oder nicht, haben sie bereits zuvor gesehen worden ist.

Allerdings läuft das ziemlich langsam, da es viele neue Elemente gibt, also würde ich es mögen, wenn mir jemand in die richtige Richtung bezüglich des besten Algorithmus in diesem Fall zeigen könnte.

Answer 1

Einfach beitreten wird die Arbeit machen - es nutzt Hashset zwischen Sammlungen zur Anpassung, die Ihnen O (1) für Suchoperation gibt:

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 

Um die Leistung weiter zu verbessern Sie identifier Extraktion direkt mit dem Schlüssel bewegen können Schaffung. Sie verzichten also auf die Einführung einer neuen Bereichsvariablen.

Answer 2

Ich empfehle die Verwendung Hashing, z.B. HashSet<T> oder Dictionary<T>. Vorausgesetzt, dass translation sowie LocalCombination_id vom Typ sind 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);