0

现在这个问题很难。我有一个如下方式的 linq 查询

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

现在lstAllWords是一个字符串列表变量，如下所示

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

我的问题是我应该如何保留 Words 数据以获得最佳 LINQ 选择性能。我的意思是目前我将其保留为字符串列表。但是我可以保持不同的方式并获得更好的性能吗？

dtWords是一个字典对象

C# C#-4.0 LINQ

4

2 回答 2

3

如果您只想有效地查找以给定子字符串开头或结尾的单词，那么使用SortedSet将帮助您在O(log(N))时间内完成此操作。

这个想法是将单词放在两个SortedSets中：

  • 一个用于原始单词和
  • 另一个用于颠倒的单词。

玩具实现：

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

    }

}

这打印：

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

如果您还必须搜索中缀，那么以上内容还不够——您需要一个后缀树或数组，但这并不是正确有效地实现的野餐。

顺便说一句，如果数据恰好在数据库中，您可以通过以下方式让 DBMS 做同样的事情：

  • 创建与原始单词列相反的计算列或虚拟列，
  • 索引原始单词列和反向单词列（或者，如果您的 DBMS 支持，则使用基于函数的索引）。
  • 查询前缀为：ORIGINAL_WORD_COLUMN LIKE 'pefix%'
  • 后缀为：REVERSED_WORD_COLUMN LIKE 'reversed_suffix%'.
于 2012-02-22T03:28:49.260 回答
0

字符串列表对于从中进行选择应该具有足够的性能，但是您通过选择并遍历 a 来添加一些装箱/拆箱操作var。您可以使用强类型List<string>作为 LINQ 查询结果的接收者来提高性能，但它可能只在非常大的数据集上才会引人注目。

于 2012-02-22T01:59:22.180 回答