Время обработки Linq-to-objects удваивается за x итераций - PullRequest
Новая
       9

Время обработки Linq-to-objects удваивается за x итераций

0 голосов
/ 18 сентября 2009

У меня есть список объектов, который содержит ~ 137000 записей, которые я перебираю Затем мне нужно линк к списку дополнительных параметров Tuple, который содержит ~ 150000

Почему это занимает больше времени, чем больше итераций? Вот из секундомера Найдено: 136770 товаров, соответствующих критериям.

10 000 обработанных элементов. Время: 5473Это: 0,0912166666666667 минут.

20 000 обработанных предметов. EllapsedTime: 15307Что: 0,255116666666667 минут.

30 000 обработанных предметов. EllapsedTime: 30065Таким образом: 0,501083333333333 минут.

50 000 обработанных предметов. Время: 74507, то есть: 1,24178333333333 минуты.

75 000 обработанных предметов. Время: 157836Что: 2,6306 минуты.

100 000 обработанных предметов. EllapsedTime: 272495Что: 4,54158333333333 минут.

Время истечения: 499663, то есть: 8.32771666666667 минут.

Есть ли способ оптимизировать это? 

 List<Entites> alMatched 
List<Tuple<int, double, int, int>> lsItems = new List<Tuple<int, double, int, int>>();
IEnumerable<Tuple<int, double, int, int>> enumThingy = lsItems;

 for (int z = 0; z <= alMatched.Count() - 1;z++ )
            {
               Entity a = alMatched[z];
               var newRepl = enumThingy.Where(d => d.First == a.ID).First();
               if (newRepl != null)
               {

               }

                switch (z)
                {
                    case 10000:
                        Debug.Print("10,000 items processed " + ElapsedTime(sw.ElapsedMilliseconds));
                        break;
                    case 20000:
                        Debug.Print("20,000 items processed " + ElapsedTime(sw.ElapsedMilliseconds));
                        break;
                    case 30000:
                        Debug.Print("30,000 items processed " + ElapsedTime(sw.ElapsedMilliseconds));
                        break;
                    case 50000:
                        Debug.Print("50,000 items processed " + ElapsedTime(sw.ElapsedMilliseconds));
                        break;
                    case 75000:
                        Debug.Print("75,000 items processed " + ElapsedTime(sw.ElapsedMilliseconds));
                        break;
                    case 100000:
                        Debug.Print("100,000 items processed " + ElapsedTime(sw.ElapsedMilliseconds));
                        break;
                }

            }

Привет

_Eric

Ответы [ 3 ]

2 голосов
/ 18 сентября 2009

Посмотрите на этот код: 

for (int z = 0; z <= alMatched.Count() - 1;z++ )
{
    Entity a = alMatched[z];
    var newRepl = enumThingy.Where(d => d.First == a.ID).First();

В этом случае (и я подозреваю, что ваш «реальный» случай), перечисляемые значения enumThingy и alMatched находятся в одном и том же порядке.

Из-за этого, когда вы находитесь в случае 1, вызов enumThingy.Where возвращается на первой итерации. В случае 100 требуется 100 итераций, чтобы соответствовать вашему условию, и выйти. В случае 10000 требуется 10000 итераций.

По сути, чем дальше, тем хуже становится. Ваш алгоритм O (N ^ 2), но LINQ является кратчайшим, потому что вы используете тот же список, а упорядочение помогает вам быстро сокращаться.

1 голос
/ 18 сентября 2009

Конечно. Попробуйте словарь вместо списка 

    List<Tuple<int, double, int, int>> lsItems = new List<Tuple<int, double, int, int>>();

//should be 

var lsItems = new Dictionary<int, Tuple<int, double, int, int>>();

/ ссылаться на элементы с:

var newRepl = lsItems [a.ID];

0 голосов
/ 18 сентября 2009

Здесь вы можете использовать различные подходы для увеличения скорости.

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

Другим вариантом будет сортировка enumthingee, а также сортировка alMatched, а затем использование «скользящего подхода», чтобы найти все нужные вам элементы.

В настоящее время вы работаете с перечислением, и он должен проверить все элементы, чтобы найти тот, который вам нужен, поэтому потребуется больше и больше времени, пока в конце цепочки ваш элемент находится (или полностью отсутствует)

...