C# 相交字符串列表的最快方法

Question

我正在使用 hashet、linq Intersect() 和 Count() 来查找两个列表的交集字符串。

正在使用的代码

private HashSet<string> Words { get; }

public Sentence(IEnumerable<string> words)
{
    Words = words.ToHashSet();
}

public int GetSameWordCount(Sentence sentence)
{
    return Words.Intersect(sentence.Words).Count();
}

方法 GetSameWordCount 占用了 > 90% 的程序运行时间，因为有数百万个句子需要相互比较。

有没有更快的方法来做到这一点？

我正在使用 .net core 3.1.1/C# 8，因此可以使用任何最新功能。

More info:
Input data is coming from text file (e.g. book excerpt, articles from web). Sentences are then unaccented, lowercased and split to words by whitespace >regex. Short words (<3 length) are ignored.
I am creating groups of sentences which have N words in common and ordering >these groups by number of shared words.

Answer 1

下面的代码将利用 HashSet<T>.Contains性能更高的方法。 HashSet<T>.Contains 的时间复杂度是 O(1)。

public int GetSameWordCount(Sentence sentence)
{
    var count;
    foreach(var word in sentence.Words)
    {
         if(Words.Contains(word))
             count++;
    }
    return count;
}

注意

如果单词列表已排序，您可以使用以下方法。

        var enumerator1 = set1.GetEnumerator();
        var enumerator2 = set2.GetEnumerator();
        var count = 0;
        if (enumerator1.MoveNext() && enumerator2.MoveNext())
        {
            while (true)
            {
                var value = enumerator1.Current.CompareTo(enumerator2.Current);
                if (value == 0)
                {
                    count++;
                    if (!enumerator1.MoveNext() || !enumerator2.MoveNext())
                        break;
                }
                else if (value < 0)
                {
                    if (!enumerator1.MoveNext())
                        break;
                }
                else
                {
                    if (!enumerator2.MoveNext())
                        break;
                }
            }
        }