C# Самый быстрый способ пересечения списков строк - PullRequest
Новая
       44

C# Самый быстрый способ пересечения списков строк

3 голосов
/ 13 февраля 2020

Я использую 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 , поэтому можно использовать любые последние функции.

Дополнительная информация:
Входные данные из текстового файла (например, отрывок из книги, статьи из Интернета). Предложения затем без акцента, в нижнем регистре и разделены на слова с помощью пробела> регулярное выражение. Короткие слова (длина <3) игнорируются. <br>Я создаю группы предложений, которые имеют N общих слов, и упорядочиваю> эти группы по количеству общих слов.

1 Ответ

2 голосов
/ 20 февраля 2020

В приведенном ниже коде будет использоваться метод 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;
                }
            }
        }
...