Готовимся к ЕГЭ по информатике

Что такое запросы LINQ?

    LINQ – это технология работы с доступом к данным, разработанная компанией Microsoft для своей среды .NET. Изначально она применялась для работы с базами данных и осуществления запросов к ним, однако позднее она была расширена до работы с объектами программного кода (LINQ to Objects).

    В PascalABC.NET на базе LINQ to Objects реализованы элементы функционального программирования с помощью запросов и применяемых в них лямбда-выражений. Запросы могут применяться к таким объектам, как динамические массивы, списки, словари, очереди, стеки – любые объекты, реализованные на основе последовательностей, а также к самим последовательностям. Последовательности являются неизменяемыми структурами данных, изменить последовательность можно только целиком, для этого идеально подходят запросы.

    В функциональном программировании существует несколько основных операций: проекция, фильтрация и сортировка. С их помощью решается широкий круг задач, причём решение получается компактным и понятным. Запросы этих групп возвращают новые последовательности с таким же типом данных элементов, однако размеры полученных структур могут отличаться от исходных как в большую, так и в меньшую сторону.

1. Поэлементные запросы

    Поэлементные запросы – первая группа запросов, которые возвращают единственное значение, в зависимости от типа данных исходных элементов. Так как последовательности являются универсальными перечислимыми структурами, то все запросы будут демонстрироваться на основе них. Основные поэлементные запросы продемонстрированы ниже.

First([pred: T->boolean]): T Last([pred: T->boolean]): T Single([pred: T->boolean]): T ElementAt(i: integer): T FirstOrDefault([pred: T->boolean]): T LastOrDefault([pred: T->boolean]): T SingleOrDefault([pred:T-> boolean]): T ElementAtOrDefault(index: integer): T

    Запросы First и Last возвращают соответственно первый и последний элементы последовательности, запрос Single – единственный элемент последовательности, а запрос ElementAt – элемент с индексом i. Если указывается предикат pred, то запросы обрабатывают только те элементы последовательности, которые удовлетворяют указанному предикату.

    Запросы, имеющие суффикс OrDefault, выполняются аналогично запросам без суффикса, однако при отсутствии требуемого элемента запросы с суффиксом OrDefault возвращают нулевое значение для типа T. Ниже представлено использование этих запросов.

## var pas:=(1..10); pas.First(e->e mod 4=2).Println;                   //2 pas.Last(e->e mod 4=3).Println;                   //7 pas.ElementAt(2).Println;                              //3 pas.FirstOrDefault(e->sqrt(e)>2).Println;      //5 pas.LastOrDefault(e->e*e div 4=3).Println;   //0  pas.ElementAtOrDefault(2).Println;              //3

2. Запросы-квантификаторы и математические запросы

    Далее рассмотрим запросы-квантификаторы (проверяют последовательность на удовлетворение условиям, заданным в предикатах) All, Any, Contains, SequenceEqual и запросы, позволяющие быстро считать количество элементов последовательности и их сумму, находить максимальный и минимальный элементы. Эти запросы представлены ниже.

All(pred: T -> boolean): boolean Any([pred: T -> boolean]): boolean Contains(value: T): boolean SequenceEqual(seq2: sequence of T): boolean Count([pred: T -> boolean]): integer Average([sel: T -> числовой_тип]): real Sum([sel: T -> числовой_тип]): числовой_тип Max([sel: T -> TKey]): TKey Min([sel: T -> TKey]): TKey

    Запрос All возвращает True, если все элементы последовательности удовлетворяют предикату pred (для пустой последовательности запрос All всегда возвращает True).

    Запрос Any возвращает True, если какие-либо элементы последовательности удовлетворяют предикату pred (для пустой последовательности запрос Any всегда возвращает False).

    Запрос Contains возвращает True, если в последовательности имеется хотя бы один элемент со значением value.

    Запрос SequenceEqual возвращает True, если вызвавшая его последовательность seq1 совпадает с последовательностью seq2 (последовательности считаются равными, если они содержат одни и те же элементы в том же самом порядке).

    Запрос Count возвращает размер последовательности (если указан предикат pred, то находит количество элементов, удовлетворяющих этому предикату).

    Запросы Average, Sum, Min и Max находят соответственно среднее арифметическое, сумму, минимум и максимум элементов последовательности или, при наличии лямбда-выражения sel, тех значений, в которые эти элементы преобразуются этим выражением. Если последовательность пустая, то запрос Sum возвращает нулевое значение, а Average, Min и Max выводят ошибку.

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

## var A:=(1..5);   //1 2 3 4 5 var B:=SeqGen(7,e->(-1)**(e*e)*e*e); //0 -1 4 -9 16 -25 B.All(e->e=(-1)*e).println; //False A.Contains(4).println;    //True B.Any(e->e=(-1)*e).println; //True var A:=(1..5);    //1 2 3 4 5 A.Average().Println;      //3 A.Average(e->2*e).Println;//4 A.Min.Println;            //1 A.Max(e->2*e).Println;    //10 A.Sum.Println;        //15 A.Sum(e->2*e).Println;    //30

3. Запросы фильтрации

    Запросы фильтрации – группа запросов, которые выбирают из исходной последовательности элементы по какому-то критерию и помещают их в новую последовательность. Полученная последовательность всегда не превосходит исходную по количеству элементов.

    Основные запросы этого типа следующие: Where(pred), TakeWhile(pred), SkipWhile(pred), Take(count), TakeLast(count), Skip(count), Distinct. Рассмотрим работу каждого запроса отдельно.

    Запрос Where(pred) возвращает последовательность, содержащую только те элементы исходной последовательности, которые удовлетворяют предикату pred.

    Запрос TakeWhile заносит в новую последовательность элементы исходной последовательности, пока указанный предикат возвращает значение true.

    Запрос SkipWhile, в отличие от TakeWhile, пропускает начальные элементы исходной последовательности, пока предикат возвращает значение true, после чего заносит в выходную последовательность все оставшиеся элементы.

    Запросы Take, TakeLast и Skip, подобно методам TakeWhile и SkipWhile, возвращают начальную или конечную часть исходной последовательности: Take возвращает первые count элементов, TakeLast – последние count элементов, а Skip пропускает первые count элементов и возвращает оставшиеся. Такой же результат можно получить и с помощью  срезов.

    Запрос Distinct возвращает последовательность без повторяющихся элементов, в последовательности оставляются только первые вхождения повторяющихся элементов.

    Функционал запросов фильтрации представлен ниже.

var a:=Arr(1,2,3,4,5,6); a.Where(x->x**2>4); // 3 4 5 6 a.Take(3).Println;  // 1 2 3 a.Skip(3).Println;  // 4 5 6 a.Skip(2).Take(3).Println;  // 3 4 5 a.TakeWhile(x->x<3).Println;  // 1 2 a.SkipWhile(x->x<5).Println;  // 5 6 var b:=Arr('aaa', 'bbb', 'ccc', 'aaa', 'ccc');

4. Запросы сортировки

    Запросы сортировки – группа запросов, которые сортируют исходную последовательность по какому-то принципу и возвращают новую отсортированную последовательность, однако некоторые запросы изменяют саму последовательность и ничего не возвращают. Главные запросы этого типа следующие: Sort, Sorted, OrderBy, ThenBy, Reverse, а также все эти запросы с суффиксом Descending.

    Запрос Sort осуществляет сортировку исходного массива по возрастанию. Новый массив не создаётся, только изменяется исходный. Если используется последовательность, то её нужно преобразовать в динамический массив методом ToArray.

    Запрос Sorted возвращает отсортированную в порядке возрастания последовательность, однако исходная последовательность не изменяется.

    Запрос OrderBy(keySelector: T->Key) осуществляет сортировку последовательности по указанному ключу в порядке возрастания, где ключ определяется лямбда-выражением.

    Запрос ThenBy используется для переупорядочивания (в порядке возрастания своего ключа) только тех элементов последовательности, у которых были одинаковые ключи на предыдущем этапе сортировки, например, запросом OrderBy.

    Запрос Reverse возвращает последовательность, элементы которой располагаются в обратном порядке по отношению к исходной последовательности, например:

 (1..9).Reverse.Print; // 9 8 7 6 5 4 3 2 1

    При добавлении к запросам суффикса Descending происходит та же сортировка, только в порядке убывания. Работа запросов представлена ниже.

## var F:=Seq(2,4,1,5,7,0).ToArray; var S:=F.Sorted; F.Sort; println(F,S); // [0,1,2,4,5,7] [0,1,2,4,5,7] var A:=Arr(('Петров',20),('Королёв',18),('Иванов',25), ('Аверин',28), ('Иванов',21)); A.OrderBy(t->t[1]).Println; // (Королёв,18) (Петров,20) (Иванов,21) (Иванов,25) (Аверин,28) A.OrderByDescending(t->t[1]).Println; // (Аверин,28) (Иванов,25) (Иванов,21) (Петров,20) (Королёв,18) A.OrderBy(t->t[0]).ThenBy(t->t[1]).Println; // (Аверин,28) (Иванов,21) (Иванов,25) (Королёв,18) (Петров,20)

5. Запросы проецирования

    Запросы проецирования – группа методов, применяемых к последовательностям, которые формируют новые последовательности с элементами одного типа из исходных последовательностей другого типа. Типы элементов входной и выходной последовательностей могут отличаться. Преобразование элементов происходит с помощью лямбда-выражений. Основные запросы проецирования изображены ниже.

Select(sel:(T[,integer])->TRes): sequence of TRes SelectMany(sel:(T[,integer])->sequence of TRes): sequence of TRes SelectMany(sel:(T[,integer])->sequence of TMid; finalSel:(T,TMid)->TRes): sequence of TRes

    Запрос Select изменяет каждый элемент исходной последовательности, применяя к нему лямбда-выражение, и помещает новое значение в результирующую последовательность.
    Таким образом, последовательность, полученная в результате применения запроса Select, всегда имеет тот же размер, что и исходная последовательность. Использование запроса Select вместе с динамическим массивом проиллюстрировано ниже.

## var Комплектующие:=|'Монитор', 'Мышка', 'Клавиатура', 'Колонки', 'Системный блок', 'Процессор'|; Комплектующие   .Select(word->(word,word.Length))   .Println   .Select(\(s,n)->$'Длина слова {s} равна {n}')   .PrintLines;
Вывод: (Монитор,7) (Мышка,5) (Клавиатура,10) (Колонки,7) (Системный блок,14) (Процессор,9) Длина слова Монитор равна 7 Длина слова Мышка равна 5 Длина слова Клавиатура равна 10 Длина слова Колонки равна 7 Длина слова Системный блок равна 14 Длина слова Процессор равна 9

    На рисунке выше создаётся массив слов «Комплектующие» типа string, для каждого элемента массива необходимо вывести на экран фразу «Длина слова S равна N», где S – очередное слово в массиве, N – длина этого слова.

    Во-первых, к массиву применим запрос Select с селектором word‑>(word,word.Length). Данный запрос выбирает очередное слово word из массива и формирует на его основе кортеж из двух элементов: самого слова и его длины (word,word.Length). После первого метода Select получится следующий массив:

 |(Монитор,7)(Мышка,5)(Клавиатура,10)(Колонки,7)(Системный блок,14)(Процессор,9)|

    Во-вторых, к полученному массиву из кортежей применим новый запрос Select, но с другим, более сложным селектором: \(s,n)->$'Длина слова {<span lang="EN-US">s</span>} равна {<span lang="EN-US">n</span>}'.
    Конструкция \(s,n) обозначает присваивание полей кортежа переменным s и n (распаковка кортежа в переменные). Лямбда-выражение распаковывает текущий кортеж в переменные и использует их для создания интерполированной строки, начинающейся со знака доллара - $. Такая запись позволяет компактно встраивать значения переменных или выражений в строки. В фигурных скобках {} указывается значение переменной или выражения.

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

    Запрос SelectMany выполняется более сложным образом. Его лямбда-выражение sel преобразует каждый элемент исходной последовательности в последовательность новых значений. В то время как операция Select возвращает один выходной элемент для каждого входного элемента, SelectMany вернет ноль или более выходных элементов для каждого входного. Рассмотрим работу запроса на примере.

## var Комплектующие:=|'Монитор', 'Мышка', 'Клавиатура', 'Колонки', 'Системный блок', 'Процессор'|; var Res:=Комплектующие.SelectMany(x->x.ToArray()); print(Res);
Вывод: [М,о,н,и,т,о,р,М,ы,ш,к,а,К,л,а,в,и,а,т,у,р,а,К,о,л,о,н,к,и,С,и,с,т,е,м,н,ы,й, ,б,л,о,к,П,р,о,ц,е,с,с,о,р]

    В примере выше лямбда-выражение запроса SelectMany преобразует каждый элемент исходного массива в массив символов с помощью функции ToArray(), и в конце формирует единую последовательность из всех полученных символов, к которым можно обращаться с помощью функций First, Last, ElementAt().

6. Запросы комбинирования, расщепления, объединения

    Запросы комбинирования, расщепления, объединения – группа методов последовательностей, которые применяются в ситуациях необходимости объединения или расщепления данных последовательностей по некоторым критериям. К таким запросам относятся запросы Concat, Union, Intersect, Except, Partition, SplitAt, Join, GroupJoin.

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

    Запросы Union, Intersect, Except реализуют теоретико-множественные операции, а именно объединение, пересечение и разность двух исходных последовательностей.
    Последовательность, полученная в результате выполнения любого из этих запросов, не содержит повторяющихся элементов. Порядок следования элементов определяется порядком их первых вхождений в первую исходную последовательность. Работа описанных выше запросов показана ниже.

##   var a1:=Seq(2,3,5);   var a2:=Seq(4,7,8);   a1.Concat(a2).Println;  // 2 3 4 5 7 8   var a:=Range(1,5);       //1 2 3 4 5   var b:=Range(3,7);       //3 4 5 6 7   a.Union(b).Println;     //1 2 3 4 5 6 7   a.Intersect(b).Println; // 3 4 5   a.Except(b).Println;    // 1 2

    В запросах Join и GroupJoin используются две последовательности: первая (внешняя), которая вызывает данные запросы, а вторая (внутренняя) указывается в качестве параметра. Типы элементов внешней и внутренней последовательностей могут различаться.

    Запрос Join выполняет внутреннее объединение двух последовательностей по ключу. Ключи определяются первыми двумя лямбда-выражениями – селекторами ключей keySel1 и keySel2; к каждой паре элементов внешней и внутренней последовательности, имеющих одинаковые ключи, применяется третье лямбда-выражение – финальный селектор finalSel, и его результат заносится в выходную последовательность.

   Метод GroupJoin тоже выполняет объединение двух последовательностей по ключу, однако результирующий элемент определяется по элементу внешней последовательности и всем элементам внутренней последовательности с тем же ключом. При таком объединении любой элемент из первой последовательности примет участие в формировании выходной последовательности, даже если для него не найдется «парных» элементов из второй последовательности.

    Для демонстрации работы запросов ниже разберём примеры их использования.

    Пусть исходные последовательности определены следующим образом:

 var a1 := Seq(10, 21, 33, 84);

 var a2 := Seq(40, 51, 52, 53, 60);

    Выполним внутреннее объединение этих последовательностей, используя в качестве ключа цифру, которой оканчивается число, и возвращая последовательность пар чисел (каждая пара представляется в виде кортежа); e1 проходит элементы внешней последовательности a1, e2 проходит элементы внутренней последовательности a2:

 var res:= a1.Join(a2, e1 -> e1 mod 10, e2 -> e2 mod 10, (e1, e2) -> (e1, e2));

 Write(res);
 [(10,40),(10,60),(21,51),(33,53)]

    Если мы заменим в предыдущем фрагменте имя запроса на GroupJoin, то мы также получим последовательность пар, но теперь вторым элементом каждой пары будет не единственный элемент, а последовательность всех элементов a2, имеющих одинаковый ключ с первым элементом этой же пары.

    В нашем случае запрос GroupJoin сформирует последовательность кортежей из двух элементов, на первом месте в которых будут числа из первой последовательности a1, а на втором будут последовательности из тех чисел второй последовательности a2, у которых совпадает последняя цифра с последней цифрой первого числа:

 var res := a1.GroupJoin(a2,e1->e1 mod 10,e2->e2 mod 10, (e1, e2) -> (e1, e2));

 Write(res);// [(10,[40,60]),(21,[51]),(33,[53]),(84,[])]

    Как видно, у элемента 84 рядом стоит пустая последовательность. Это случилось потому, что во внутренней последовательности a2 не нашлось ни одного элемента, у которого будет одинаковый ключ с элементом 84. По этой же причине при использовании запроса Join в ответе не выводится элемент 84.

    Часто при решении заданий ЕГЭ по информатике требуется работать с последовательностью, состоящей из всевозможных пар, в которых первый элемент берется из первой последовательности, а второй элемент – из второй. Такой набор пар называется декартовым произведением исходных последовательностей.

    Для эффективного формирования декартова произведения в PascalABC.NET включен запрос Cartesian, который применяется к первой последовательности a1 и принимает как параметр вторую последовательность a2, подобно рассмотренным ранее методам. Итогом работы запроса является формирование последовательности кортежей.
    Кроме стандартного применения, запрос Cartesian имеет два расширения. Использование расширений запроса приведено ниже.

##   var (a,b):=(Seq(1,2), Seq(4,5,6));   a.Cartesian(b).Println;   a.Cartesian(b,(x,y)->x*y).Println;   a.Cartesian(3).Println;
Вывод: (1,4) (1,5) (1,6) (2,4) (2,5) (2,6) 4 5 6 8 10 12 [1,1,1] [1,1,2] [1,2,1] [1,2,2] [2,1,1] [2,1,2] [2,2,1] [2,2,2]

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

    Второе расширение позволяет сформировать n-степень декартова произведения. Для этого в параметрах запроса указывается целое число n – степень произведения.