2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Избегание циклов
Сообщение22.01.2023, 15:27 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Нехитрый способ решения несложных нестандартных школьных зад
Сообщение24.01.2023, 09:50 


10/03/16
4262
Aeroport
warlock66613 в сообщении #1578287 писал(а):
циклы — низкоуровневые конструкции сродни goto и не должны в норме появляться в коде


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

 Профиль  
                  
 
 Re: Нехитрый способ решения несложных нестандартных школьных зад
Сообщение24.01.2023, 13:46 
Заслуженный участник


02/08/11
6936
ozheredov в сообщении #1578524 писал(а):
Чё делать, если нужно применить операцию к массиву объектов, а операция не векторизуется? :shock:
Зависит от языка программирования и от того, что подразумевается под "применить операцию". Зачем её вообще применять? Объекты мутабельные или иммутабельные? Если мутабельные, то это уже подозрительно. Точно они должны быть мутабельными?

 Профиль  
                  
 
 Re: Избегание циклов
Сообщение24.01.2023, 19:55 


10/03/16
4262
Aeroport
warlock66613 в сообщении #1578573 писал(а):
Зачем её вообще применять


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

warlock66613 в сообщении #1578573 писал(а):
Объекты мутабельные или иммутабельные?


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

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

 Профиль  
                  
 
 Re: Избегание циклов
Сообщение24.01.2023, 22:00 
Заслуженный участник


02/08/11
6936
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 писал(а):
батч-обработка чего угодно
Не знаю что это.

 Профиль  
                  
 
 Re: Избегание циклов
Сообщение24.01.2023, 22:17 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Избегание циклов
Сообщение25.01.2023, 08:44 


10/03/16
4262
Aeroport
mihaild в сообщении #1578647 писал(а):
любой цикл можно преобразовать в рекурсивную функцию "состояние -> состояние на следующем шаге".


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

warlock66613

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

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

 Профиль  
                  
 
 Re: Избегание циклов
Сообщение25.01.2023, 11:24 
Заслуженный участник


02/08/11
6936
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) и ассемблерный код почти такой же как был бы для кода с циклом или вообще такой же.

 Профиль  
                  
 
 Re: Избегание циклов
Сообщение25.01.2023, 12:40 
Заслуженный участник
Аватара пользователя


16/07/14
8813
Цюрих
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 выкинуть промежуточные состояния (т.е. ни в какой момент не хранить весь список), или не сумеет.

 Профиль  
                  
 
 Re: Избегание циклов
Сообщение25.01.2023, 13:17 


18/09/21
1727
ozheredov в сообщении #1578684 писал(а):
А на стопиццотой итерации стек не переполнится?
Зависит от задачи.
Где-то глубина стэка растёт логарифмически (например обход сбалансированного дерева).
Где-то используется хвостовая рекурсия и продвинутые компиляторы заточенные на функциональное программирование (тот же Haskell) собирают это в код вообще без рекурсии, в тот же цикл.

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

 Профиль  
                  
 
 Re: Избегание циклов
Сообщение25.01.2023, 13:52 


10/03/16
4262
Aeroport
warlock66613 в сообщении #1578695 писал(а):
Это вы резко прямо тему поменяли


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

-- 25.01.2023, 13:54 --

zykov в сообщении #1578704 писал(а):
Зависит от задачи.
Где-то глубина стэка растёт логарифмически


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

 Профиль  
                  
 
 Re: Избегание циклов
Сообщение25.01.2023, 13:59 
Заслуженный участник


02/08/11
6936
ozheredov в сообщении #1578707 писал(а):
В смысле?
Ну вы вначале спросили "как?" и это довольно интересно обсудить, а потом резко перешли на "зачем?" и это, честно говоря, уже не очень интересно.

-- 25.01.2023, 15:05 --

ozheredov в сообщении #1578707 писал(а):
Например, есть куча изображений, которые надо улучшить одним и тем же алгоритмом (это и есть батч-обработка).
Если надо просто позвать один метод на куче объектов, то в том же Rust есть для этого функция for_each:
Код:
list.for_each(|x| x.process());
Для C# мы в своё время в команде, где я работал, тоже делали аналогичную штуку, но в общем конечно в этом случае разницы по сравнению с "честным" циклом почти нет.

 Профиль  
                  
 
 Re: Избегание циклов
Сообщение25.01.2023, 14:08 
Экс-модератор
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Избегание циклов
Сообщение25.01.2023, 14:08 


10/03/16
4262
Aeroport
warlock66613 в сообщении #1578695 писал(а):
Потому что они плохо выражают намерения программиста


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

Код:
for i=1:10
    do something;
end


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

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


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

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

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

-- 25.01.2023, 14:10 --

warlock66613 в сообщении #1578709 писал(а):
Ну вы вначале спросили "как?" и это довольно интересно обсудить, а потом резко перешли на "зачем?"

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

 Профиль  
                  
 
 Re: Избегание циклов
Сообщение25.01.2023, 14:14 
Заслуженный участник


02/08/11
6936
ozheredov в сообщении #1578711 писал(а):
Сделать одно и то же действие 10 раз:
Вопрос опять же в том, что за действие, зачем его делать и надо ли его делать именно 10 раз. Например, может так оказаться, что это надо делать в нескольких местах и с несколько отличающимися действиями. Тогда хорошим способом будет сделать свою особую функцию с осмысленным названием, принимающую функцию-действие, и вот в этой функции будет цикл, а в местах, где она используется, — не будет.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group