Как сохранить строковые данные для лучшей производительности при выборе списка строк через LINQ по запросам StartsWith и EndsWith - PullRequest
Новая
       11

Как сохранить строковые данные для лучшей производительности при выборе списка строк через LINQ по запросам StartsWith и EndsWith

0 голосов
/ 22 февраля 2012

Теперь вопрос довольно сложный. У меня есть запросы 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());
        }

Мой вопрос заключается в том, как сохранить эти данные Слова для обеспечения наилучшей производительности при выборе LINQ. Я имею в виду в настоящее время я держу его в виде списка строк. Но могу ли я сохранить это по-другому и иметь лучшую производительность?

dtWords - объект словаря

C # C # -4.0 LINQ

Ответы [ 2 ]

3 голосов
/ 22 февраля 2012

Если все, что вам нужно, это эффективно поиск слов, которые начинаются или заканчиваются заданной подстрокой, использование SortedSet поможет вам сделать это в O (log (N)) время.

Идея состоит в том, чтобы поместить слова в два SortedSet s:

  • один для исходных слов и
  • другой для обращенных слов.

Реализация игрушек: 

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

Если вам также нужно искать инфиксы, то вышеприведенного недостаточно -Вам понадобится суффиксное дерево или массив, но это не то, что пикник правильно реализует и .

Кстати, если данные находятся в базе данных, вы можете разрешитьСУБД, по сути, делает то же самое:

  • , создавая вычисляемый столбец или виртуальный столбец , обратный столбцу исходного слова,
  • индексирование и столбец исходного слова и столбец обратного слова (или, альтернативно, использование на основе функцииindex , если это то, что поддерживает ваша СУБД).
  • запрос префикса как: ORIGINAL_WORD_COLUMN LIKE 'pefix%'
  • и суффикса как: REVERSED_WORD_COLUMN LIKE 'reversed_suffix%'.
0 голосов
/ 22 февраля 2012

Строковый список должен быть достаточно производительным для выбора, но вы добавляете некоторые операции упаковки / распаковки, выбирая и затем повторяя по var.Вы можете использовать строго типизированный List<string> в качестве получателя результатов запроса LINQ для повышения производительности, но это, вероятно, будет заметно только для очень больших наборов данных.

...