воскресенье, 29 января 2012 г.

О многообразии вариантов решения задачи выборки

Итак, сегодня попробую сравнить решения задачи выборки данных удовлетворяющих некоторому условию из массива.
Задача следующая:
Есть N объектов в виде коллекции. Необходимо выбрать в новый список все элементы у которых одно из строковых полей равно заданному значению.
В процессе будут сравниваться методы перебора, выборки LINQ, PLINQ.

Для экспериментов будем пользоваться коллекцией классов вида:
class Item
{
  public string Field { get; set; }
}
Для генерации тестовой коллекции будем использовать вот такой метод:
  
static List GetTestCollection(int p_n, string p_text)
{
    List result = new List();
    Random rnd = new Random();
    string randomString = "tmjrnehgbkljhbsxhkjer wpivhjqb wzc qqvjhqsdb vcklsamadcc";
    int itemCount = 0;
    for (int i = 0; i < p_n; i++)
    {
        if (rnd.Next(p_n) < 100)
        {
            result.Add(new Item() { Field = p_text });
            itemCount++;
        }
        else
        {
            result.Add(new Item() { Field = randomString.Substring(rnd.Next(20), rnd.Next(10)) });
        }
    }
    if (itemCount == 0)
    {
        result[rnd.Next(p_n)].Field = p_text;
    }
    return result;
}

Как видим, хоть один элемент удовлетворяющий условию у нас будет.
Итак первый метод, цикл перебирающий всю коллекцию и записывающий элементы удовлетворяющие нашему условию в выходной список.
static List<Item> SimpleSearch(List<Item> p_list, string p_text)
{
    List<Item> result = new List<Item>();
    foreach (var item in p_list)
     {
                if (item.Field == p_text)
       {
            result.Add(item);
       }
    }
    return result;
}
Второй метод решат аналогичную задачу при помощи LINQ:
static List<Item> LinqSearch(List<Item> p_list, string p_text)
{
    List<Item> result = p_list.Where(item => item.Field == p_text).ToList();
  return result;
}
Третий метод тоже LINQ, только с прейиксом P:
static List<Item> PlinqSearch(List<Item> p_list, string p_text)
{
    List<Item> result = p_list.AsParallel().Where(item => item.Field == p_text).ToList();
  return result;
}
В зависимости от длинны массива получаем вот такую интересную картинку:
По оси x, отложены миллионы записей в коллекции. Как видим, для маленьких коллекций решение "в лоб" оказалось даже эффективнее LINQ, причем PLINQ оказался даже хуже чем не параллельная модификация. А вот на больших коллекциях PLINQ вырывается вперед, причем, на 10 миллионах записей, опережает простое решение в полтора раза.
Кстати, если в простом поиске заменить foreach на for, то тогда алгоритм будет работать чуть быстрее. На большой коллекции выигрышь достигает 10-12%.

Собственно вводы:
1. Если скорость неважна или коллекция маленькая, то использовать LINQ (т.к. писать меньше кода).
2. На больших коллекциях в многоядерных системах (у меня i7 второго поколения с 4 физическими и 8 логическими ядрами), правильнее PLINQ.

В следующий раз попробуем поиграться с выборками в упорядоченныз коллекциях.

Комментариев нет:

Отправить комментарий