Почему у меня возникают проблемы с производительностью при использовании List.IndexOf (List.Where ()) внутри цикла?

Question

Я работаю над решением для получения списка биграмм и количества каждой биграммы для заданного ввода.Производительность была плохой с большим вводом;Время выполнения заняло около 42 секунд для ввода 460 000 символов и 84 000 слов.Я изменил код, и теперь он работает нормально, но я не уверен, что именно вызвало проблему с производительностью.

В закомментированном коде была проблема.Я думал, что будет лучше, если я соберу биграмму и вхождения каждого биграма в 1 цикл, а не в два, но я ошибся.Получение индекса элемента в списке - при передаче параметра элемента через List.Where () - не представляется эффективным.Зачем?Оценивается ли предикат для каждого элемента в списке, даже при использовании FirstOrDefault () ?

Мое единственное мнение: даже если предикат не оценивается для каждого элемента в списке, я мог быпонять, почему использование List.IndexOf (List.Where ()) медленнее.Если в списке 84 000 элементов, FirstOrDefault () должен циклически проходить (я полагаю), пока не найдет первое совпадение, которое может быть с индексом 0 или 83 999, и это повторяется для каждого элемента всписок.

public class Bigram
{
    public string Phrase { get; set; }
    public int Count { get; set; }
}

public List<Bigram> GetSequence(string[] words)
{

  List<Bigram> bigrams = new List<Bigram>();
  List<string> bigramsTemp = new List<string>();

   for (int i = 0; i < words.Length - 1; i++)
    {
       if (string.IsNullOrWhiteSpace(words[i]) == false)
         {
            bigramsTemp.Add(words[i] + " " + words[i + 1]);

             //Bigram bigram = new Bigram()
              //{
                //  Phrase = words[i] + " " + words[i + 1]
               //};

                //bigrams.Add(bigram);

                //var matches = bigrams.Where(p => p.Phrase == bigram.Phrase).Count();

                //if (matches == 0)
                //{
                //    bigram.Count = 1;
                //    bigrams.Add(bigram);
                //}
                //else
                //{
                // int bigramToEdit = 
                //     bigrams.IndexOf(
                //       bigrams.Where(b => b.Phrase == bigram.Phrase).FirstOrDefault());
                //    bigrams[bigramToEdit].Count += 1;
                //}
            }
        }

        var sequences = bigramsTemp.GroupBy(i => i);

        foreach (var s in sequences)
        {
            bigrams.Add(
                new Bigram()
                {
                    Phrase = s.Key,
                    Count = s.Count()
                });
        }

        return bigrams;
    }

Answer 1

Из вашего исходного кода, который имеет около 4 циклов по всему массиву биграмм

var matches = bigrams.Where(p => p.Phrase == bigram.Phrase).Count();

if (matches == 0)
{
    bigram.Count = 1;
    bigrams.Add(bigram);
}
else
{
    int bigramToEdit = 
     bigrams.IndexOf(
       bigrams.Where(b => b.Phrase == bigram.Phrase).FirstOrDefault());
    bigrams[bigramToEdit].Count += 1;
}

Перейдите к следующему, который имеет только один цикл по всему массиву биграмм, сохраняя логику такой же

var match = bigrams.FirstOrDefault(b => b.Phrase == bigram.Phrase);
if (match == null)
{
    //match == null means that it does not exist in the array, which is equivalent with Count == 0
    bigram.Count = 1;
    bigrams.Add(bigram);
}
else
{
    //changing the value of match.Count is essentially the same as querying the match again using IndexOf and Where
    match.Count += 1;
}

Дайте мне знать, как идет производительность после перехода на этот

Answer 2

В качестве дополнения к ответам @ hans-keing и @mylee, переход к словарю поможет вашему коду еще больше:

IDictionary<string, int> bigramsDict = new Dictionary<string, int>();

for (int i = 0; i < words.Length - 1; i++)
{
    if (string.IsNullOrWhiteSpace(words[i]))
    {
        continue;
    }

    string key = words[i] + " " words[i + 1];
    if (!bigramsDict.ContainsKey(key))
        bigramsDict.Add(key, 1);
    else
        bigramsDict[key]++;    
}

Если вы не хотите изменять публичную подпись, вам нужновыполнить преобразование в список с помощью:

foreach (var item in bigramsDict) {
    bigrams.add(new Bigram {Phrase = item.Key, Count = item.Value});
} 

retrun bigrams;

---

Тест производительности

Результаты в миллисекундах:

1. Исходный код: 163835.0242.
2. mylee code: 75099.003.
3. Код словаря: 23,76.

    public static string[] CreateRandomWords(int count)
    {
        string[] result = new string[count];

        var chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
        var stringChars = new char[8];
        var random = new Random();

        for (int i = 0; i < count; i++)
        {
            for (int j = 0; j < stringChars.Length; j++)
            {
                stringChars[j] = chars[random.Next(chars.Length)];
            }

            var finalString = new String(stringChars);

            result[i] = finalString;
        }

        return result;
    }


    public class Bigram
    {
        public string Phrase { get; set; }
        public int Count { get; set; }
    }

    public static List<Bigram> GetSequenceA1(string[] words)
    {
        List<Bigram> bigrams = new List<Bigram>();

        for (int i = 0; i < words.Length - 1; i++)
        {
            if (string.IsNullOrWhiteSpace(words[i]) == false)
            {
                Bigram bigram = new Bigram()
                {
                    Phrase = words[i] + " " + words[i + 1]
                };

                bigrams.Add(bigram);

                var matches = bigrams.Where(p => p.Phrase == bigram.Phrase).Count();

                if (matches == 0)
                {
                    bigram.Count = 1;
                    bigrams.Add(bigram);
                }
                else
                {
                    int bigramToEdit =
                        bigrams.IndexOf(
                            bigrams.Where(b => b.Phrase == bigram.Phrase).FirstOrDefault());
                    bigrams[bigramToEdit].Count += 1;
                }
            }
        }

        return bigrams;
    }

    public static List<Bigram> GetSequenceA2(string[] words)
    {
        List<Bigram> bigrams = new List<Bigram>();

        for (int i = 0; i < words.Length - 1; i++)
        {
            if (string.IsNullOrWhiteSpace(words[i]) == false)
            {
                Bigram bigram = new Bigram()
                {
                    Phrase = words[i] + " " + words[i + 1]
                };

                bigrams.Add(bigram);

                var match = bigrams.FirstOrDefault(b => b.Phrase == bigram.Phrase);
                if (match == null)
                {                        
                    bigram.Count = 1;
                    bigrams.Add(bigram);
                }
                else
                {                        
                    match.Count += 1;
                }
            }
        }

        return bigrams;
    }

    public static List<Bigram> GetSequenceB(string[] words)
    {
        List<Bigram> bigrams = new List<Bigram>();

        IDictionary<string, int> bigramsDict = new Dictionary<string, int>();

        for (int i = 0; i < words.Length - 1; i++)
        {
            if (string.IsNullOrWhiteSpace(words[i]))
            {
                continue;
            }

            string key = words[i] + " " + words[i + 1];
            if (!bigramsDict.ContainsKey(key))
                bigramsDict.Add(key, 1);
            else
                bigramsDict[key]++;
        }

        foreach (var item in bigramsDict)
        {
            bigrams.Add(new Bigram { Phrase = item.Key, Count = item.Value });
        }

        return bigrams;
    }

    public static void Run()
    {
        string[] _wordsList = CreateRandomWords(85000);

        Stopwatch stopwatchA1 = new Stopwatch();
        stopwatchA1.Start();
        List<Bigram> SequenceA1 = GetSequenceA1(_wordsList);
        stopwatchA1.Stop();
        double durationA1 = stopwatchA1.Elapsed.TotalMilliseconds;
        Console.WriteLine("SequenceA1:" + durationA1);

        Stopwatch stopwatchA2 = new Stopwatch();
        stopwatchA2.Start();
        List<Bigram> SequenceA2 = GetSequenceA2(_wordsList);
        stopwatchA2.Stop();
        double durationA2 = stopwatchA2.Elapsed.TotalMilliseconds;
        Console.WriteLine("SequenceA2:" + durationA2);

        Stopwatch stopwatchB = new Stopwatch();
        stopwatchB.Start();
        List<Bigram> SequenceB = GetSequenceB(_wordsList);
        stopwatchB.Stop();
        double durationB = stopwatchB.Elapsed.TotalMilliseconds;
        Console.WriteLine("SequenceB:" + durationB);
    }

Answer 3

bigrams.Where().FirstOrDefault() просматривает список биграмм до тех пор, пока не будет найдено первое совпадение.

Затем bigrams.IndexOf() проходит по этому списку снова , чтобы найти индекс.

Это после этого bigrams.Where().Count() уже перебрал весь список.

И все это повторяется для каждого слова.

Некоторые способы ускорить это:

• Вы можете использовать тот факт, что FirstOrDefault возвращает null, когда нет совпадений, тогда вы можете пропустить Count.
• Существует перегрузка , где используется индекс, так что вы также можете пропустить дополнительный шаг IndexOf. Но вам не нужно это (как mylee saw ), поскольку у вас уже есть биграмма для обновления.