MCP

вторник, 26 июня 2012 г.

Циклы. Нужны ли они?

Не стоит воспринимать данный текст слишком серьёзно. В нём присутствует некоторая доля бреда

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

Давайте подумаем, где в этом красивом стройном мире место циклам? А места на самом деле и нет! Не нужны циклы при повседневной работе. Они могут быть запрятаны где-то внутри библиотек или вообще быть только на уровне компилятора. Без них можно совершенно спокойно обойтись, всему есть красивые замены. Перечислим, для чего используют циклы:

Преобразование

Типичная задача: взять из списка объектов "Пользователь" только имя и работать с ним дальше. Есть вполне сформировавшиеся абстракции, например map в jQuery или Select в .NET. Согласитесь, что второй пример кода выглядит гораздо понятнее первого, т.к. отсутствует лишний вспомогательный код:

List<string> names = new List<string>(); 
foreach(var user in users) 
    names.Add(user.Name); 

var names = users.Select(x => x.Name);

Фильтрация

Тоже частая задача. Выбрать всех активных пользователей. Тут стандартные схемы filter и Where:
List<User> resUsers = new List<User>(); 
foreach(var user in users) 
    if(user.IsActive) 
        resUsers.Add(user); 

var resUsers = users.Where(x => x.IsActive);

Аггрегация 

Куда же без неё! Например, нам нужно посчитать количество пользователей (да, у нас сейчас нет встроенной функции):
var cnt = 0; 
foreach(var user in users) 
    cnt++; 
А в нормальном стиле (в общем виде) это можно сделать как-то так, через аккумулятор:
var cnt = users.Aggregate((e, acc) => acc + 1);

Обработка

В данном случае результат передаётся куда-то дальше, основной объект никак не трансформируется. Тут нам на помощь приходят each в jQuery и ForEach в .NET. Например, мы хотим вывести имена пользователей на консоль:
//names - List<int> из первого примера 
foreach(var name in names)  
    Console.WriteLine(name);  

names.ForEach(Console.WriteLine);

И всё вместе

И конечно же, циклы используются сразу для всех задач вместе, ещё больше запутывая код и подменяющие реализацию задачи ненужными деталями реализации (которые, действительно, никому никогда не нужны и только мешают дальнейшему чтению кода).
Итак, выбираем имена активных пользователей и находим самое длинное:
List<string> names = new List<string>();  
foreach(var user in users)  
    if(user.IsActive) 
        names.Add(user.Name);  

var maxName = ""; 
foreach(var name in names) 
    if(maxName.Length < name.length)  
        maxName = name; 

//-------------------- 
var maxName = users 
    .Where(x => x.IsActive) 
    .Select(x => x.Name) 
    .Aggregate("", (e, acc) => e.Length > acc.Length ? e : acc);

Согласитесь, второй вариант, гораздо понятнее и короче. Сразу по тексту видно что он делает (и это я ещё не воспользовался готовым методом Max). В первом же случае проще всего догадаться о том, что делает код по названию переменной, но это в данном простом тестовом примере. А в реальной жизни всё гораздо запутаннее, ведь обязательно набегут оптимизаторы и цикл превратится в более короткую и простую версию, которая понятнее (вроде бы), но в результате вся логика прибита гвоздями и её изменение становится уже более сложной задачей, связанной с практически полным переписыванием куска кода:
var maxName = ""; 
foreach(var user in users)  
    if(user.IsActive && user.Name.Length > maxName.Length) 
        maxName = name; 

Результат

Что мы получили: циклы всегда можно заменить на простую комбинацию простых конкретных операций, в результате код будет легче читаться, легче сопровождаться и будет содержать меньше ошибок. Кроме того, мы избавляемся от врождённой болезни циклов — побочных эффектов (что сильно мешает оптимизациям даже на уровне компиляторов). Так что у них остаётся единственное преимущество — производительность. Но и она постепенно нивелируется развитием комплияторов и библиотек, так что может стоит отказаться от циклов прямо сейчас, и не быть слоупоком?


Напоследок

Чтобы не останавливаться на элементарных примерах, я решил привести чуть более сложный. А именно, реализацию сортировки. Классический quicksort из учебника выглядит примерно так (только главная часть):
public void Sort(int start, int end) 
{ 
    if (end <= start) return; 
    if (end - start == 1) 
    { 
        if (_array[end] < _array[start]) Swap(start, end); 
        return; 
    } 
    int el = _array[(start + end)/2]; 
    int endIdx = end; 
    int startIdx = start; 
    while(startIdx <= endIdx) 
    { 
        if (_array[startIdx] < el) startIdx++; 
        else 
            if (_array[endIdx] <= el) 
            { 
                Swap(startIdx, endIdx); 
                endIdx--; 
                startIdx++; 
            } 
            else endIdx--; 
    } 
    Sort(start, endIdx); 
    Sort(endIdx + 1, end); 
}
Данный код, конечно можно подсократить, но это уже тонкости и детали реализации и оптимизации. Тем не менее, даже на такой пример я потратил достаточно времени, пока его реализовал и выловил все замеченные ошибки. И в теперь разобраться как сортирует алгоритм за всеми конструкциями весьма сложно. А теперь посмотрите, что я написал сходу на LINQ:

public IEnumerable<int> Sort(IEnumerable<int> arr) 
{ 
    if (arr.Count() <= 1) return arr; 
    int el = arr.First(); 
    return Sort(arr.Where(x => x < el))
           .Concat(arr.Where(x => x == el))
           .Concat(Sort(arr.Where(x => x > el))); 
}
Всего 5 строчек, и то разбитых для удобства! И смотрите как просто объяснить теперь алгоритм: берём первый попавшийся элемент, берём из массива все элементы меньше него, сортируем их данным же алгоритом, добавляем элементы равные данному, и большие, отсортированные тем же алгоритмом. Всё просто, банально и понятно.
Не хочем quicksort, хотим сортировку выбором? Нет ничего проще:
public IEnumerable<int> Sort(IEnumerable<int> arr) 
{ 
    if (arr.Count() <= 1) return arr; 
    int elMax = arr.Max(); 
    return Sort(arr.Where(x => x < elMax)).Concat(arr.Where(x => x == elMax)); 
}

Видите, вполне чёткая логика и понятность. Так зачем вам ещё циклы?

7 комментариев:

  1. а потом оказывается, что где-то у нас баг и вперед непонятно как отлаживать эти linq запросы ;)

    ОтветитьУдалить
    Ответы
    1. Да циклы-то тоже не шедеврально отлаживать, особенно какой-нить хитрый сумматор, который суммирует как-нибудь не так, из-за ошибки в данных на 100500-ом шаге :)

      Удалить
  2. Дэн, где-то у вас баг - это ты про Майкрософт? Т.е. в линке ошибка? :)

    ОтветитьУдалить
  3. Однако надо заметить, что quicksort на LINQ уже не совсем quicksort, а tree sort. Concat возвращает некий объект (пусть объект класса ConcatenatedEnumerable), содержащий ссылки на два IEnumerable. Функция Sort строит дерево поиска, которое представляется в виде дерева объектов ConcatenatedEnumerable. А затем в процессе итерации по этому объекту дерево линеаризуется. Конструктивное различие в том, что quicksort не требует дополнительной памяти для работы (O(1) не считается), а tree sort строит дерево, занимающее O(n) памяти.

    Еще менее очевидно, что получается с quicksort в подобной реализации на Haskell. Там в силу ленивости, полученное дерево не вычисляется полностью. Но вот отдельные ветки, видимо, вычисляются и занимают в среднем O(log n) памяти.

    Это достаточно интересный факт — то, что происходит с известными алгоритмами в условиях ленивых вычислений. Часто суть работы с точки зрения операций (на машине Тьюринга) меняется весьма неочевидным образом.

    ОтветитьУдалить
    Ответы
    1. Да, как-то не подумал, что ближе к tree sort получилось, хотя за основу брал quick sort.

      Удалить
  4. А ещё в foreach нельзя удалять элементы)Без цикла не обойтись

    ОтветитьУдалить
    Ответы
    1. Массовое удаление элементов, вообще нетривиальная операция, и если нет явного требования по занимаемой памяти, то это просто фильтрация и лучше вернуть новый, правильный массив, чем мучать в цикле коллекцию (что, кстати, очень нечитабельно впоследствии выглядит).

      Удалить