Избегание циклов

[warlock66613]

gevaraweb в сообщении #1576434 писал(а):

Стало раздражать писать в сто тыщ пятисотый раз циклы

Откройте для себя современный подход к программированию, где циклы — низкоуровневые конструкции сродни goto и не должны в норме появляться в коде. (Правда иногда всё же цикл удобен, но чтобы выработать чувство где использовать цикл, а где нет, надо некоторое время пописать вообще без циклов, пока это не станет привычкой.) Точка входа в это дело — программирование на Haskell, хоть и не обязательно глубоко и серьёзно.

[ozheredov]

warlock66613 в сообщении #1578287 писал(а):

циклы — низкоуровневые конструкции сродни goto и не должны в норме появляться в коде

Чё делать, если нужно применить операцию к массиву объектов, а операция не векторизуется?

[warlock66613]

ozheredov в сообщении #1578524 писал(а):

Чё делать, если нужно применить операцию к массиву объектов, а операция не векторизуется? :shock:

Зависит от языка программирования и от того, что подразумевается под "применить операцию". Зачем её вообще применять? Объекты мутабельные или иммутабельные? Если мутабельные, то это уже подозрительно. Точно они должны быть мутабельными?

[ozheredov]

warlock66613 в сообщении #1578573 писал(а):

Зачем её вообще применять

Пример 1: есть процедура поиска минимума функции. Стартует в рандомной точке, вычисляет значения целевой функции в некоторой конфигурации аргументов вокруг этой точки, после этого проверяет гипотезу о том, попала ли она в минимум или нужно двигаться дальше (и если да, то куда). После очередного прыжка процедура повторяется. Мы не знаем, что именно будем делать на 33-й итерации и вообще -- будет ли у нас эта итерация.

warlock66613 в сообщении #1578573 писал(а):

Объекты мутабельные или иммутабельные?

Кто именно мутабельный - точки конфигурационного пространства? Думаю, нет.

Пример 2: батч-обработка чего угодно (Вы скажете, что это скрипт, а не программа, но это может быть низкоуровневая обработка как часть более высокоуровневого алгоритма, поэтому оформлена она будет в виде функции). Объекты мутабельные.

[warlock66613]

ozheredov в сообщении #1578623 писал(а):

есть процедура поиска минимума функции. Стартует в рандомной точке, вычисляет значения целевой функции в некоторой конфигурации аргументов вокруг этой точки, после этого проверяет гипотезу о том, попала ли она в минимум или нужно двигаться дальше (и если да, то куда)

Если я правильно понял, вот накидал как это будет выглядеть на Rust (запустить):

use rand::random;
use std::iter::*;

fn f(x: i16) -> i32 { i32::from(x) * i32::from(x) }

fn near_points(x: i16) -> [i16; 2] { [x - 1, x + 1] }

fn main() {
    let result = successors(
        Some(random::<i16>()),
        |&x| near_points(x).into_iter().chain(once(x)).min_by_key(|&t| f(t)).filter(|&t| t != x)
    ).last().unwrap();
    println!("{result}");
}

В C# в стандартной библиотеке всё похуже с готовыми функциями типа successors и once, их придётся искать в библиотеках (но быстро я не нашёл) или написать самому. Также код пользуется тем, что тип Option (аналог в Хаскелл — Maybe) является монадой, поэтому его можно отфильтровать. В C# придётся либо опять же делать свой тип, либо найти готовый нестандартный (уж это только ленивый не делал), либо возможно подойдёт Option из F# (но F# библиотека довольно увесистая). В итоге аналогичная строчка, заменяющая цикл, будет выглядеть примерно так:

Iterate(
    random.Next(),
    x => NearPoints(x).Concat(x.Yield()).MinBy(F).Where(t => t != x)
).Last()

Здесь Iterate — это аналог successors, её сигнатура IEnumerable<T> Iterate<T>(T initial, Func<T, Maybe<T>> step), а Yield — это аналог once с сигнатурой IEnumerable<T> Yield<T>(this T item).

-- 24.01.2023, 23:12 --

ozheredov в сообщении #1578623 писал(а):

батч-обработка чего угодно

Не знаю что это.

[mihaild]

Понятно, что любой цикл можно преобразовать в рекурсивную функцию "состояние -> состояние на следующем шаге". Если сильно постараться и использовать эффективные иммутабельные структуры данных, то можно даже обойтись без копирования большей части не изменившегося. Но в случаях, когда разница в производительности в 2-3 раза важна, такой подход всё же не работает.

[ozheredov]

mihaild в сообщении #1578647 писал(а):

любой цикл можно преобразовать в рекурсивную функцию "состояние -> состояние на следующем шаге".

А на стопиццотой итерации стек не переполнится?

warlock66613

Давайте начнем не с листинга, а с "теоретического" вопроса:

Почему циклов следует избегать? Прыжки goto сильно запутывают поведение проги и поэтому усложняют отладку. Но цикл вроде -- нечто простое. Или я не прав?

[warlock66613]

ozheredov в сообщении #1578684 писал(а):

Почему циклов следует избегать?

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

-- 25.01.2023, 12:34 --

Вот как легко, почти как предложение обычного текста, читается строчка из примера выше: взяли текущую точку (|&x|); нашли окружающие точки (near_points(x).into_iter()); присоединили к ним саму нашу точку (.chain(once(x))); выбрали ту, где значение функции минимально (.min_by_key(|&t| f(t))); остановились, если это текущая точка(.filter(|&t| t != x)]). И всё это в одной короткой строке. Весь алгоритм видно одним взглядом.

-- 25.01.2023, 12:40 --

mihaild в сообщении #1578647 писал(а):

любой цикл можно преобразовать в рекурсивную функцию

О, я не заметил слово "рекурсивную". Преобразование цикла в рекурсию — это полезная техника, но не имеющая прямой связи с тем о чём я говорю. В примере выше нет никакой рекурсии, глобально цикл никуда не делся (он внутри функции last) и ассемблерный код почти такой же как был бы для кода с циклом или вообще такой же.

[mihaild]

ozheredov в сообщении #1578684 писал(а):

А на стопиццотой итерации стек не переполнится?

Ну когда память закончится - переполнится. Но в большинстве задач не закончится.

warlock66613 в сообщении #1578695 писал(а):

И всё это в одной короткой строке. Весь алгоритм видно одним взглядом

Используется синтаксис C++

while ((cur = std::min({prev, prev - 1, prev + 1}, [](int a, int b) {return f(a) < f(b);})) != prev) {
         prev = cur;
}

Я думаю в этой строке алгоритм видно примерно настолько же, насколько в Вашей.
ИМХО как раз мутабельное состояние интуитивно (посмотрите сколько в ПРР(М) идей менять множества, да и в диффгеме например очень любят изгибать поверхности), это математики больше привыкли к иммутабельным объектам.

warlock66613 в сообщении #1578695 писал(а):

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

Тут вопрос в том, сумеет ли оптимизация last выкинуть промежуточные состояния (т.е. ни в какой момент не хранить весь список), или не сумеет.

[zykov]

ozheredov в сообщении #1578684 писал(а):

А на стопиццотой итерации стек не переполнится?

Зависит от задачи.
Где-то глубина стэка растёт логарифмически (например обход сбалансированного дерева).
Где-то используется хвостовая рекурсия и продвинутые компиляторы заточенные на функциональное программирование (тот же Haskell) собирают это в код вообще без рекурсии, в тот же цикл.

Что до самой парадигмы функционального программирования, то там есть конечно свои плюсы. Но есть и минусы. В любом случае оне далеко не универсально удобна.
Тот же Lisp уже более 60 лет существует. И на то есть причины, почему он не стал мэйнстримом за это время.
Хотя кое-где с успехом используется. Например как скриптовый язык Maxima, Emacs, некоторые CAD (AutoCAD).

[ozheredov]

warlock66613 в сообщении #1578695 писал(а):

Это вы резко прямо тему поменяли

В смысле? Мне казалось, тема об том, что циклы = отстой. Хотя конечно начал я с того, что есть дескать в Matlab'e перегруженный оператор *, и перемножение матриц с ним работает быстрее, чем двойной цикл. В r есть функции sapply и lapply, то же самое. Т.е. по крайней мере в некоторых случаях циклы сильно проигрывают по быстроте, и потому они отстой. Но что делать, если к исходным массивам не применимы sapply и lapply? Например, есть куча изображений, которые надо улучшить одним и тем же алгоритмом (это и есть батч-обработка).

-- 25.01.2023, 13:54 --

zykov в сообщении #1578704 писал(а):

Зависит от задачи.
Где-то глубина стэка растёт логарифмически

Как-то не очень хочется каждый раз оценивать скорость роста глубины стека. Есть конечно задачи, где рекурсия просто напрашивается (да, тот же обход дерева).

[warlock66613]

ozheredov в сообщении #1578707 писал(а):

В смысле?

Ну вы вначале спросили "как?" и это довольно интересно обсудить, а потом резко перешли на "зачем?" и это, честно говоря, уже не очень интересно.

-- 25.01.2023, 15:05 --

ozheredov в сообщении #1578707 писал(а):

Например, есть куча изображений, которые надо улучшить одним и тем же алгоритмом (это и есть батч-обработка).

Если надо просто позвать один метод на куче объектов, то в том же Rust есть для этого функция for_each:

list.for_each(|x| x.process());

Для C# мы в своё время в команде, где я работал, тоже делали аналогичную штуку, но в общем конечно в этом случае разницы по сравнению с "честным" циклом почти нет.

[photon]

Мне кажется, что говорить, что циклы - зло (или добро) - это довольно однобокое суждение.

Общее требование, из которого следует и избегание циклов - писать короткие легкочитаемые функции. Если есть возможность что-то выделить как самостоятельную часть, выполняющую некое законченное действие, - делать это. Например, найти минимальное число в массиве - это цикл по элементам массива, цикл можно вынести в отдельную функцию min() (Или, во многих случаях, это уже сделано - использовать готовую). Кроме того, зачастую, такие штуки оптимизируют/векторизуют и они, если покопаться, будут написаны сложнее, чем просто цикл, но работают быстрее - очевидно, сортировка пузырьком из двух циклов во многих случаях проиграет более продвинутым методам сортировки, но в коде разработчика вызов sort(), за которым скрыта более громоздкая чем два цикла функция, будет при этом компактее и понятнее, чем реализация пузырька in-place.

Читаемость кода важна и с точки зрения его поддержки и с точки зрения вероятности баг в нем, но могут быть и другие требования: потребление памяти, энергии, быстродействие, что иногда идет в противоречие с разбиением на отдельные удобочитаемые фрагменты. Правда, соглашусь, разработчик в узких местах в таких случаях должен например объединять несколько функций в один цикл осознано, понимая, что он выигрывает, теряя читаемость, то есть сначала написать "красиво", а уже потом, если есть острая необходимость, ломать красоту.

[ozheredov]

warlock66613 в сообщении #1578695 писал(а):

Потому что они плохо выражают намерения программиста

Сделать одно и то же действие 10 раз:

for i=1:10
    do something;
end

Что здесь плохо выражает?

warlock66613 в сообщении #1578695 писал(а):

Поиск элемента, сумма, или итерации как вот в примере выше и много всего ещё — всё это выражается через примерно одинаково выглядящий цикл.

Потому что действия по сути одни и те же. Представьте, что стоят фонари вдоль забора. Мы можем хотеть:

А) смотать проволоку со всех фонарей (это сумма)
В) заменить лампу каждого фонаря на диодную (итерации)
С) пометить фонарь с наименьшей яркостью (поиск)

Во всех случаях мы вдоль шеренги фонарей, останавливаясь возле каждого и совершая с ним однотипные действия. Нет)

-- 25.01.2023, 14:10 --

warlock66613 в сообщении #1578709 писал(а):

Ну вы вначале спросили "как?" и это довольно интересно обсудить, а потом резко перешли на "зачем?"

Ок, понял, прошу прощения.

[warlock66613]

ozheredov в сообщении #1578711 писал(а):

Сделать одно и то же действие 10 раз:

Вопрос опять же в том, что за действие, зачем его делать и надо ли его делать именно 10 раз. Например, может так оказаться, что это надо делать в нескольких местах и с несколько отличающимися действиями. Тогда хорошим способом будет сделать свою особую функцию с осмысленным названием, принимающую функцию-действие, и вот в этой функции будет цикл, а в местах, где она используется, — не будет.