So bewahren Sie Zeichenfolgendaten auf, um die beste Leistung bei der Auswahl einer Zeichenfolgenliste über LINQ durch StartsWith- und EndsWith-Abfragen zu erzielen

Question

Nun ist die Frage ziemlich schwierig.Ich habe eine Linq-Abfrage wie unten

var lstSimilars = from similarWords in lstAllWords

where similarWords.StartsWith(srWordLocal)

select similarWords;

foreach (string srVar in lstSimilars)
{
string srTempWord = srVar.Replace(srWordLocal, "");
if (dtWords.ContainsKey(srTempWord) == true)
{
csWords.updateSplitWord(srWordLocal + ";" + srTempWord, dtWords[srVar]);
}
}

lstSimilars = from similarWords in lstAllWords

where similarWords.EndsWith(srWordLocal)

select similarWords;

foreach (string srVar in lstSimilars)
{
string srTempWord = srVar.Replace(srWordLocal, "");
if (dtWords.ContainsKey(srTempWord) == true)
{
csWords.updateSplitWord(srWordLocal + ";" + srTempWord, dtWords[srVar]);
}
}

Jetzt lstAllWords ist eine String-Listenvariable, die wie folgt generiert wird

        List<string> lstAllWords = new List<string>();


        for (int i = 0; i < dsWordsSplit.Tables[0].Rows.Count; i++)
        {
            lstAllWords.Add(dsWordsSplit.Tables[0].Rows[i]["Word"].ToString());
        }

Meine Frage ist, wie ich diese Words-Daten aufbewahren soll, um die beste LINQ-Auswahlleistung zu erzielen.Ich meine, derzeit behalte ich es als String-Liste.Aber kann ich es anders halten und eine bessere Leistung erzielen?

dtWords ist ein Wörterbuchobjekt

C# C#-4.0 LINQ

Answer 1

Wenn Sie nur effizient Wörter suchen möchten, die mit einem bestimmten Teilstring beginnen oder enden, verwenden Sie SortedSet hilft Ihnen dabei, dies in O (log (N)) Zeit zu tun.

Die Idee ist, Wörter in zwei SortedSets einzufügen:

• eins für Originalwörter und
• das andere für umgekehrte Wörter.

  Spielzeugimplementierung:

  class WordSet {
  
      public WordSet(IEnumerable<string> words) {
          m_OriginalWords = new SortedSet<string>(words);
          m_ReverseWords = new SortedSet<string>(words.Select(ReverseString));
      }
  
      /// <summary>
      ///     Finds all words that start with given prefix.
      /// </summary>
      public IEnumerable<string> FindPrefix(string prefix) {
          return FindImp(m_OriginalWords, prefix);
      }
  
      /// <summary>
      ///     Finds all words that end with the given suffix.
      /// </summary>
      public IEnumerable<string> FindSuffix(string suffix) {
          return FindImp(m_ReverseWords, ReverseString(suffix)).Select(ReverseString);
      }
  
      static IEnumerable<string> FindImp(SortedSet<string> word_set, string s) {
          if (s.CompareTo(word_set.Max) <= 0) {
              foreach (string word in word_set.GetViewBetween(s, word_set.Max)) {
                  if (!word.StartsWith(s))
                      break;
                  yield return word;
              }
          }
      }
  
      static string ReverseString(string src) {
          return new string(src.Reverse().ToArray());
      }
  
      readonly SortedSet<string> m_OriginalWords;
      readonly SortedSet<string> m_ReverseWords;
  
  }
  
  class Program {
  
      static void TestImp(string s, IEnumerable<string> words) {
          Console.Write(s);
          foreach (var word in words) {
              Console.Write('\t');
              Console.Write(word);
          }
          Console.WriteLine();
      }
  
      static void TestPrefix(WordSet word_set, string prefix) {
          TestImp(prefix, word_set.FindPrefix(prefix));
      }
  
      static void TestSuffix(WordSet word_set, string suffix) {
          TestImp(suffix, word_set.FindSuffix(suffix));
      }
  
      static void Main(string[] args) {
  
          var word_set = new WordSet(
              new[] {
                  "a",
                  "b",
                  "ba",
                  "baa",
                  "bab",
                  "bba",
                  "bbb",
                  "bbc",
              }
          );
  
          Console.WriteLine("Prefixes:");
          TestPrefix(word_set, "a");
          TestPrefix(word_set, "b");
          TestPrefix(word_set, "ba");
          TestPrefix(word_set, "bb");
          TestPrefix(word_set, "bc");
  
          Console.WriteLine("\nSuffixes:");
          TestSuffix(word_set, "a");
          TestSuffix(word_set, "b");
          TestSuffix(word_set, "ba");
          TestSuffix(word_set, "bb");
          TestSuffix(word_set, "bc");
  
      }
  
  }
  

  Dies druckt:

  Prefixes:
  a       a
  b       b       ba      baa     bab     bba     bbb     bbc
  ba      ba      baa     bab
  bb      bba     bbb     bbc
  bc
  
  Suffixes:
  a       a       baa     ba      bba
  b       b       bab     bbb
  ba      ba      bba
  bb      bbb
  bc      bbc
  

  Wenn Sie auch nach Infixen suchen müssen, reicht das oben Genannte nicht aus - Sie benötigen einen Suffixbaum oder ein Array, aber dies ist kein Picknick, das und effizient implementiert wird.

  ---

  Übrigens, wenn sich die Daten zufällig in der Datenbank befinden, können Sie das DBMS im Wesentlichen dasselbe tun lassen, indem Sie:

  • Erstellen einer berechneten Spalte oder virtuelle Spalte , die umgekehrt zur ursprünglichen Wortspalte ist,
  • Indizieren sowohl der ursprünglichen Wortspalte als auch der umgekehrten Wortspalte (oder alternativ mit einem funktionsbasierter Index , wenn Ihr DBMS dies unterstützt.
  • Abfrage nach Präfix als: ORIGINAL_WORD_COLUMN LIKE 'pefix%'
  • und für das Suffix als: REVERSED_WORD_COLUMN LIKE 'reversed_suffix%'.

Answer 2

Eine Zeichenfolgenliste sollte für die Auswahl aus ausreichend leistungsfähig sein, aber Sie fügen einige Boxing-/Unboxing-Vorgänge hinzu, indem Sie eine auswählen und dann über a iterieren var.Sie können eine stark typisierte verwenden List<string> als Empfänger von LINQ-Abfrageergebnissen für eine Leistungssteigerung, die jedoch wahrscheinlich nur spürbar ist sehr große Datensätze.