Now the question is pretty hard. I have a linq queries like the way below
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]);
}
}
Now lstAllWords is a string list variable generated like the way below
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());
}
My question is how should i keep that Words data for having best LINQ selection performance. I mean currently i am keeping it as a string list. But can i keep it different way and have better performance ?
dtWords is a dictionary object
C# C#-4.0 LINQ
If all you want is efficiently finding words that start or end with given substring, employing the SortedSet will help you do that in O(log(N)) time.
The idea is to put words in two SortedSets:
- one for original words and
- the other for reversed words.
Toy implementation:
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");
}
}
This prints:
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
If you have to search for infixes as well, then the above is not enough - you'll need a suffix tree or array, but this is no picnic implementing correctly and efficiently.
BTW, If the data happens to be in the database, you can let the DBMS do essentially the same thing by:
- creating a computed column or virtual column that is reverse of the original word column,
- indexing both original word column and the reversed word column (or, alternatively, using a function-based index if that's what your DBMS supports).
- querying for prefix as:
ORIGINAL_WORD_COLUMN LIKE 'pefix%'
- and for suffix as:
REVERSED_WORD_COLUMN LIKE 'reversed_suffix%'.
A string list should be sufficiently performant for selecting from, but you're adding some boxing/unboxing operations by selecting into and then iterating over a var. You can use a strongly-typed List<string> as your recipient of LINQ query results for a performance boost, but it'll likely only be noticeable for very large datasets.
