:)) Боюсь тут уже пошла вкусовщина - одним проще и понятнее одно, другим другое.
Лично мне значительно проще заметить что: ", обойдясь 4 умножениями вместо 16." Но это работает только при . Дальше остаётся вспомнить что любое целое положительное n в двоичной системе и есть сумма чисел "например, десятичное число 11 в двоичном виде 0b1011, где 1 в нулевом, первом и третьем битах означают , а 0 во втором бите означает что в этой сумме нет (отсчёт битов начинается с нулевого бита, поэтому второй бит в 0b1011 визуально находится на третьей позиции)." А суммирование степеней при одинаковом основании эквивалентно перемножению, "например, . " И исходя из этой логики проверка очередного разряда как n & 1 и переход к следующему разряду n>>1 выглядят значительно логичнее чем n % 2 и n/2 хотя формально это одно и тоже. И никакого умножения в столбик я здесь не вижу.
А вот ваша версия:
надо сначала посчитать значение половинной степени, потом это возвести в квадрат и подправить, если четность не та.
звучит конечно короче, но у меня в голове укладывается плохо ;)
Как у вас из этого внезапно ДВА цикла появилось вообще не понимаю.
Просто возьмите Код 1.2. и Код 2.2. и пошагайте в них отладчиком и/или взгляните на приведённую в статье отладочную информацию которую выводит Код 1.4. и Код 2.4. и вы наглядно увидите что этот код ведёт себя именно как два цикла, выполняющиеся один за другим.
И да, статья как раз о том что появление этих двух (и более) циклов для читающего программу может оказаться внезапным и неочевидным.
Ваши же примеры совершенно точно начинают использовать кучу
Да, std::stack использует кучу, но он здесь исключительно для того чтобы проиллюстрировать логику поведения рекуррентного варианта, использующего стек неявно. Сделать варианты с контейнером без лишних обращений к куче не проблема. Просто это не имеет отношения к алгоритмической логике рассматриваемого кода, поэтому не стал усложнять этим примеры. В остальном вижу что мы говорим на разных языках. Если придумаю другие слова чтобы вам стало понятнее о чём я, то потом напишу дополнительно.
Ваш первый вариант полностью эквивалентен моему варианту Код 2.6. с поправкой на то что ваше n % 2 эквивалентно моему n & 1, а n/2 эквивалентно n>>1. И компилятор скорее всего скомпилирует на этих конструкциях одинаковый машинный код.
Второй вариант интереснее про него отвечу позже, возможно добавлю этот ответ в статью.
Вот когда вы пытаетесь циклы перевести в рекурсию, не понимая основного принципа деления пополам, вот там сложности в логике возникают, да.
На мой взгляд описанная мною логика основанная на двоичном представлении n и использовании сдвига вместо деления более точно и наглядно описывает процесс, но повторюсь - формально и с точки зрения машинного кода после оптимизирующего компилятора эти варианты эквивалентны, поэтому ваша логика равноправна с моей.
И всё это не отменяет моего последующего разбора этого варианта. Как его вывести из рекуррентной или цикловой логики это прелюдия - важнее как он потом реально работает.
Да, про числа Фибоначчи тоже будет, может кому-то это и баян, а по мне так яркий и наглядный пример.
Вся статья должна называться "Я не знаю, что такое хвостовая рекурсия".
Нет, это называется кто-то не заметил:
Компиляторы функциональных языков программирования умеют преобразовывать так называемую «хвостовую» рекурсию в цикл, убирая её негативные эффекты. Но «хвостовая» рекурсия позволяет реализовать лишь простейшие варианты рекурсии. В общем случае рекурсия эквивалентна нескольким псевдоциклам и анализ количества и функционала этих псевдоциклов нетривиален, а потому не подлежит оптимизации компилятором. По сути «хвостовая» рекурсия не более чем «заплатка» позволяющая вернуть в функциональные языки программирования опрометчиво удалённые из них циклы. Вред от мышления рекурсиями в программировании будет рассмотрен ниже на конкретных примерах.
И да, это вводная часть с простейшими примерами, дальше будут примеры невозможность оптимизации которых на уровне компилятора будет очевидна.
И переводится в код напрямую, сначала с двумя случаями четного/нечетного, а потом их можно объединить для краткости кода.
Да у меня там есть ссылка на эту логику с чётностью / не чётностью и комментарий к ней: "Однако с логикой там всё мутно и сложно - много букв и формул, а в конструкции усматривается сакральный смысл по преобразованию нечётных чисел в чётные, хотя на самом деле вычитание единицы из нечётного числа обнуляет младший двоичный разряд, а целочисленное деление на два этот младший разряд отбрасывает независимо от того был он предварительно обнулён вычитанием единицы или нет. "
почти любая работа с древовидными структурами данных в виде рекурсии получается читабельнее и понятнее.
Про древовидные структуры будет в следующих частях. Есть что сказать, но пока не буду спойлерить.
Но часто это тривиальная цена за более простой код,
Примеры с очень дорогой и главное неочевидной ценой тоже будут в продолжении. Причём цена там из серии когда в супермаркете выбрал товар по выгодной цене, а на кассе пробивают чек на цену х10 или х1000.
Я не понимаю, почему вы постоянно зовёте имлпментации без единого рекурсивного вызова рекурсиями.
В смысле без единого? - везде под "код x.2" идёт пример с рекурсией, а сопровождающие его два примера с циклами иллюстрируют как это нормально запрограммировать и что на самом деле делает рекурсия если посмотреть её под пошаговым отладчиком и/или через добавление отладочной информации.
Это не считая того что зачем-то ещё и стек впендюриваете, хотя он там нафиг не нужен ни в одном из вариантов.
Затем что рекурсия Всегда неявно использует стек процессора и в данных примерах делает это именно так как описано в статье, но если смотреть только на код рекурсии не пытаясь вникнуть в происходящее то этого не видно. Об этом и статья что "вы не видите суслика, а он есть!"
Ещё и циклы никак не ограничены.
При применении рекурсии всегда "автоматически" формируется как минимум два (может значительно больше) "псевдоцикла" и программист никак не может на это повлиять или оптимизировать. Точнее может если откажется от рекурсии.
правильная рекурсивная чистая функция отлично оптимизируется в цикле
Одиночный конкурс с небольшим количеством призёров хорошо, но хотелось бы побольше системности в поддержке Open Source. Хочу чтобы: - подобные конкурсы были регулярными и количество призёров за каждый конкурс больше; - а ещё лучше чтобы это были не отдельные конкурсы, а постоянно действующая программа, рассматривающая входящие завки по мере их поступления; - публикацию информационо образовательных материалов о том где и как начинающие разработчики Open Source могут получить материальную поддержку своих проектов.
Никакой свободой распространения там даже не пахнет.
Что значит не пахнет? Вы знаете примеры, когда к кому то были претензии за то что он "по пиратски" распространял GPL программы? В проприентарном мире "пиратское" использование и распространение это преступление, административно/уголовно/судебно наказуемое. В мире GPL это абсолютно законно поэтому и свобода.
и как в этой юрисдикции работают экспортные ограничения.
Вы видели новую версию GPL в которой прописаны экспортные ограничения или какие либо ещё - национальные, территориальные и т.п.? Если нет, то храбро берите GPL программы и используйте/распространяйте! Если для фактического скачивания таких программ есть какие-то экспортные/территориальные и т.п. технические ограничения, то обходить их и затем распространять GPL программу за пределами этих ограничений - законно! И если вдруг когда нибудь такая ограничивающая версия GPL появится, то она: - не будет совместима с существующими версиями, где такие запреты явно запрещены; - не будет иметь обратной силы - уже существующие свободные программы такими и останутся.
Потому-то вся эта история с т.н «свободным ПО» не идет во благо развитию индустрии.
Да с финансовой стороной тут есть серьёзные проблемы. Идея GPL отлично подошла бы к осознанному коммунистическому обществу, где никто не "тянет одеяло на себя". В таком обществе нет денег за их ненадобностью, потому что "каждому по потребностям - от каждого по способностям" и уклоняться от того чтобы вносить вклад в общее благо (по мере способностей и постоянно заниматься развитием этих способностей) - не принято, не прилично, стрёмно, себя не уважать. А с капитализмом, где про "урвать", "взломать систему", "дать поменьше - взять побольше", "торговаться до усрачки за каждую копейку", да, идея Свободного ПО плохо совмещается.
Но сходу возражать, даже не читая, про что был тред, это GPL тоже не запрещает :)
Читал, но потерял мысль в этом "многа букв". Теперь понял в чём суть спора. Разделяю мысль что IDE для программиста эквивалентна Блендеру для 3Dшника.
Бизнес-модель Гугла предполагает бесплатные и открытые средства доступа для весьма платных и очень даже закрытых сервисов Гугла, к слову.
Как бы возможно да, но не припомню когда я использовал свой телефон на андроиде в качестве средства доступа к платным сервисам Гугла и платил за это. Получается Андроид типа "благотворительный проект" который Гугл просто может себе позволить на уровне "хобби", зарабатывая на другом? Или всё таки они как то на нём зарабатывают?
Вы, желая опенсурс продвинуть, предлагаете сделать его неконкурентоспособным.
Не понимаю что здесь означает "вы предлагаете" если GNU GPL именно такой и была изначально? И сейчас есть и умирать вроде как не собирается. И крупный бизнес, как уже упомянутый мною Гугл, вполне с этим живёт и здравствует, а значит как то умеет на этом зарабатывать, несмотря на бесплатность и открытость того же Андроида.
По мне логично так: если разработчик использует инструментальные средства Open Source для создания с помощью их своего программного продукта, то он обязан этим продуктом соблюдать (наследовать) все лицензионные принципы этого сообщества, т.е. не превращать его в коммерческий продукт.
Согласен, и мне нравится идея Open Source, но возникает вопрос - а жить на что?
На что есть, оплачивать жильё, покупать инструменты (компьютер, платные программы и т.д.)?
Если бы мы жили про коммунизме - "каждому по потребностям, от каждого по способностям" где никто не тянет одеяло на себя, а все осознанно и старательно работают на общее благо и поэтому деньги отменены за ненадобностью, то всё было бы понятно. Там Open Source был бы естественной и гармоничной частью общего мироустройства, более того, там только он и был бы в программировании.
Да Open Source "не запрещено" продавать. Но при этом запрещено запрещать его бесплатное распространение. Поэтому если вы работаете индивидуально с небольшим количеством заказчиков и строите с ними личные доверительные отношения, то у вас есть шансы договориться с ними о нормальной оплате. Но если вы отпускаете ПО в свободное плавание большому количеству пользователей, то оно тут же автоматически становится бесплатным и там получать деньги уже просто не получится, несмотря на то что формально "не запрещено".
Зарабатывать на чём то другом, а Open Source заниматься на уровне хобби? Так это очень серьёзный удар по качеству программ (который мы частенько и видим в реальности).
Пожертвования? Мне действительно интересно насколько этот механизм реально работает?
Собственно читаю такие темы и задаю вопросы потому что мне близка идея Open Source и я хочу этим заниматься и двигаюсь в эту сторону. И очень хочу понять на чём держится их финансовая сторона? Где там эти самые "миллиарды" из заголовка статьи и как разработчику отщипнуть от них хотя бы на хлеб и воду?
При этом вижу что тот же Гугл не бедствует, хотя Андроид, Хром и т.д. опенсорц и бесплатны для пользователей. Статья в названии претендует на раскрытие их секрета, но в итоге ограничивается только общими словами ни о чём.
Да, по такой схеме обычно и работают. Но мне интересен такой нюанс. Например, я обнаружил баг в чужом GPL коде и опубликовал свой форк с исправлением этого бага. Никаких прав на это исправление я исходному разработчику не передавал. Собственно имею полное право и на форк и на сохранение своих прав на "заплатку" к чужому коду. Означает ли это что разработчик изначального кода должен будет придумать какой то другой, отличный от моего способ исправления этого бага? Ведь если он его исправит так же как это сделал я, то получается я имею право лишить его прав на двойное лицензирование его проекта?
Мне из статьи совершенно непонятно какой магией "липкая" GNU GPL лицензия превращается в коммерческий Open Source?
Да GPL не запрещает продавать программы, но она запрещает ограничивать распространение и использование программ. Т.е. купить одну копию программы и поставить её на 150 компьютеров, а ещё раздать друзьям и выложить в сеть абсолютно законно. И копии программы, скаченные с "пиратского" сайта, согласно GPL такие же законные как и купленные у производителя. Никаких дискриминаций "коммерческое / некоммерческое использование" в GPL тоже не предусмотрено.
Часто встречается мнение что для использования свободы GPL нужно обязательно самому компилировать исходники, а иногда ещё и переименовывать программу. Но нет - GPL явным образом разрешает неограниченное копирование и использование в том числе и бинарников без изменений и без разрешения разработчика.
И как в таких условия продавать что либо кроме техподдержки?
На мой взгляд под таким названием должен быть не столько исторический очерк, сколько описание сложностей коммерциализации такого ПО и способы преодоления этих сложностей придуманные теми кто научился на этом зарабатывать.
Двойное лицензирование здесь - попытка усидеть на двух стульях. Побыть одновременно и коммунистом и капиталистом. Естественно это выглядит очень странно и внутренне противоречиво, потому что сами идеи коммунизма и капитализма взаимоисключающие.
:)) Боюсь тут уже пошла вкусовщина - одним проще и понятнее одно, другим другое.
Лично мне значительно проще заметить что: "
, обойдясь 4 умножениями вместо 16." Но это работает только при 
. Дальше остаётся вспомнить что любое целое положительное 
"например, десятичное число 11 в двоичном виде 0b1011, где 1 в нулевом, первом и третьем битах означают 
, а 0 во втором бите означает что 
в этой сумме нет (отсчёт битов начинается с нулевого бита, поэтому второй бит в 0b1011 визуально находится на третьей позиции)." А суммирование степеней при одинаковом основании эквивалентно перемножению, "например, 
. " И исходя из этой логики проверка очередного разряда как
nв двоичной системе и есть сумма чиселn & 1и переход к следующему разрядуn>>1выглядят значительно логичнее чемn % 2иn/2хотя формально это одно и тоже.И никакого умножения в столбик я здесь не вижу.
А вот ваша версия:
звучит конечно короче, но у меня в голове укладывается плохо ;)
Просто возьмите Код 1.2. и Код 2.2. и пошагайте в них отладчиком и/или взгляните на приведённую в статье отладочную информацию которую выводит Код 1.4. и Код 2.4. и вы наглядно увидите что этот код ведёт себя именно как два цикла, выполняющиеся один за другим.
И да, статья как раз о том что появление этих двух (и более) циклов для читающего программу может оказаться внезапным и неочевидным.
Да,
std::stackиспользует кучу, но он здесь исключительно для того чтобы проиллюстрировать логику поведения рекуррентного варианта, использующего стек неявно.Сделать варианты с контейнером без лишних обращений к куче не проблема. Просто это не имеет отношения к алгоритмической логике рассматриваемого кода, поэтому не стал усложнять этим примеры.
В остальном вижу что мы говорим на разных языках. Если придумаю другие слова чтобы вам стало понятнее о чём я, то потом напишу дополнительно.
Ваш первый вариант полностью эквивалентен моему варианту Код 2.6. с поправкой на то что ваше
n % 2эквивалентно моемуn & 1, аn/2эквивалентноn>>1. И компилятор скорее всего скомпилирует на этих конструкциях одинаковый машинный код.Второй вариант интереснее про него отвечу позже, возможно добавлю этот ответ в статью.
На мой взгляд описанная мною логика основанная на двоичном представлении
nи использовании сдвига вместо деления более точно и наглядно описывает процесс, но повторюсь - формально и с точки зрения машинного кода после оптимизирующего компилятора эти варианты эквивалентны, поэтому ваша логика равноправна с моей.И всё это не отменяет моего последующего разбора этого варианта. Как его вывести из рекуррентной или цикловой логики это прелюдия - важнее как он потом реально работает.
Да, про числа Фибоначчи тоже будет, может кому-то это и баян, а по мне так яркий и наглядный пример.
Нет, это называется кто-то не заметил:
И да, это вводная часть с простейшими примерами, дальше будут примеры невозможность оптимизации которых на уровне компилятора будет очевидна.
Благодарю за примеры, обязательно разберу после того как опубликую уже запланированный материал.
Да у меня там есть ссылка на эту логику с чётностью / не чётностью и комментарий к ней: "Однако с логикой там всё мутно и сложно - много букв и формул, а в конструкции
усматривается сакральный смысл по преобразованию нечётных чисел в чётные, хотя на самом деле вычитание единицы из нечётного числа обнуляет младший двоичный разряд, а целочисленное деление на два этот младший разряд отбрасывает независимо от того был он предварительно обнулён вычитанием единицы или нет. "
Про древовидные структуры будет в следующих частях. Есть что сказать, но пока не буду спойлерить.
Примеры с очень дорогой и главное неочевидной ценой тоже будут в продолжении. Причём цена там из серии когда в супермаркете выбрал товар по выгодной цене, а на кассе пробивают чек на цену х10 или х1000.
В смысле без единого? - везде под "код x.2" идёт пример с рекурсией, а сопровождающие его два примера с циклами иллюстрируют как это нормально запрограммировать и что на самом деле делает рекурсия если посмотреть её под пошаговым отладчиком и/или через добавление отладочной информации.
Затем что рекурсия Всегда неявно использует стек процессора и в данных примерах делает это именно так как описано в статье, но если смотреть только на код рекурсии не пытаясь вникнуть в происходящее то этого не видно. Об этом и статья что "вы не видите суслика, а он есть!"
При применении рекурсии всегда "автоматически" формируется как минимум два (может значительно больше) "псевдоцикла" и программист никак не может на это повлиять или оптимизировать. Точнее может если откажется от рекурсии.
Можно пример такой "чистой" рекурсивной функции?
Да, планируется серия статей с постепенным усложнением примеров.
Одиночный конкурс с небольшим количеством призёров хорошо, но хотелось бы побольше системности в поддержке Open Source.
Хочу чтобы:
- подобные конкурсы были регулярными и количество призёров за каждый конкурс больше;
- а ещё лучше чтобы это были не отдельные конкурсы, а постоянно действующая программа, рассматривающая входящие завки по мере их поступления;
- публикацию информационо образовательных материалов о том где и как начинающие разработчики Open Source могут получить материальную поддержку своих проектов.
Что значит не пахнет? Вы знаете примеры, когда к кому то были претензии за то что он "по пиратски" распространял GPL программы?
В проприентарном мире "пиратское" использование и распространение это преступление, административно/уголовно/судебно наказуемое. В мире GPL это абсолютно законно поэтому и свобода.
Вы видели новую версию GPL в которой прописаны экспортные ограничения или какие либо ещё - национальные, территориальные и т.п.? Если нет, то храбро берите GPL программы и используйте/распространяйте! Если для фактического скачивания таких программ есть какие-то экспортные/территориальные и т.п. технические ограничения, то обходить их и затем распространять GPL программу за пределами этих ограничений - законно!
И если вдруг когда нибудь такая ограничивающая версия GPL появится, то она:
- не будет совместима с существующими версиями, где такие запреты явно запрещены;
- не будет иметь обратной силы - уже существующие свободные программы такими и останутся.
Да с финансовой стороной тут есть серьёзные проблемы. Идея GPL отлично подошла бы к осознанному коммунистическому обществу, где никто не "тянет одеяло на себя". В таком обществе нет денег за их ненадобностью, потому что "каждому по потребностям - от каждого по способностям" и уклоняться от того чтобы вносить вклад в общее благо (по мере способностей и постоянно заниматься развитием этих способностей) - не принято, не прилично, стрёмно, себя не уважать.
А с капитализмом, где про "урвать", "взломать систему", "дать поменьше - взять побольше", "торговаться до усрачки за каждую копейку", да, идея Свободного ПО плохо совмещается.
Читал, но потерял мысль в этом "многа букв". Теперь понял в чём суть спора. Разделяю мысль что IDE для программиста эквивалентна Блендеру для 3Dшника.
Как бы возможно да, но не припомню когда я использовал свой телефон на андроиде в качестве средства доступа к платным сервисам Гугла и платил за это. Получается Андроид типа "благотворительный проект" который Гугл просто может себе позволить на уровне "хобби", зарабатывая на другом? Или всё таки они как то на нём зарабатывают?
Не нашёл там этих ответов. Поэтому и написал.
Не понимаю что здесь означает "вы предлагаете" если GNU GPL именно такой и была изначально? И сейчас есть и умирать вроде как не собирается.
И крупный бизнес, как уже упомянутый мною Гугл, вполне с этим живёт и здравствует, а значит как то умеет на этом зарабатывать, несмотря на бесплатность и открытость того же Андроида.
Согласен, и мне нравится идея Open Source, но возникает вопрос - а жить на что?
На что есть, оплачивать жильё, покупать инструменты (компьютер, платные программы и т.д.)?
Если бы мы жили про коммунизме - "каждому по потребностям, от каждого по способностям" где никто не тянет одеяло на себя, а все осознанно и старательно работают на общее благо и поэтому деньги отменены за ненадобностью, то всё было бы понятно. Там Open Source был бы естественной и гармоничной частью общего мироустройства, более того, там только он и был бы в программировании.
Да Open Source "не запрещено" продавать. Но при этом запрещено запрещать его бесплатное распространение. Поэтому если вы работаете индивидуально с небольшим количеством заказчиков и строите с ними личные доверительные отношения, то у вас есть шансы договориться с ними о нормальной оплате. Но если вы отпускаете ПО в свободное плавание большому количеству пользователей, то оно тут же автоматически становится бесплатным и там получать деньги уже просто не получится, несмотря на то что формально "не запрещено".
Зарабатывать на чём то другом, а Open Source заниматься на уровне хобби? Так это очень серьёзный удар по качеству программ (который мы частенько и видим в реальности).
Пожертвования? Мне действительно интересно насколько этот механизм реально работает?
Собственно читаю такие темы и задаю вопросы потому что мне близка идея Open Source и я хочу этим заниматься и двигаюсь в эту сторону. И очень хочу понять на чём держится их финансовая сторона? Где там эти самые "миллиарды" из заголовка статьи и как разработчику отщипнуть от них хотя бы на хлеб и воду?
При этом вижу что тот же Гугл не бедствует, хотя Андроид, Хром и т.д. опенсорц и бесплатны для пользователей. Статья в названии претендует на раскрытие их секрета, но в итоге ограничивается только общими словами ни о чём.
Да, по такой схеме обычно и работают.
Но мне интересен такой нюанс. Например, я обнаружил баг в чужом GPL коде и опубликовал свой форк с исправлением этого бага. Никаких прав на это исправление я исходному разработчику не передавал. Собственно имею полное право и на форк и на сохранение своих прав на "заплатку" к чужому коду.
Означает ли это что разработчик изначального кода должен будет придумать какой то другой, отличный от моего способ исправления этого бага? Ведь если он его исправит так же как это сделал я, то получается я имею право лишить его прав на двойное лицензирование его проекта?
Да, читал Вашу статью, интересная. Но упомянутые здесь "почему корпорации зарабатывают миллиарды" явно не про этот способ.
Название громкое, раскрытие темы слабое.
Мне из статьи совершенно непонятно какой магией "липкая" GNU GPL лицензия превращается в коммерческий Open Source?
Да GPL не запрещает продавать программы, но она запрещает ограничивать распространение и использование программ. Т.е. купить одну копию программы и поставить её на 150 компьютеров, а ещё раздать друзьям и выложить в сеть абсолютно законно. И копии программы, скаченные с "пиратского" сайта, согласно GPL такие же законные как и купленные у производителя. Никаких дискриминаций "коммерческое / некоммерческое использование" в GPL тоже не предусмотрено.
Часто встречается мнение что для использования свободы GPL нужно обязательно самому компилировать исходники, а иногда ещё и переименовывать программу. Но нет - GPL явным образом разрешает неограниченное копирование и использование в том числе и бинарников без изменений и без разрешения разработчика.
И как в таких условия продавать что либо кроме техподдержки?
На мой взгляд под таким названием должен быть не столько исторический очерк, сколько описание сложностей коммерциализации такого ПО и способы преодоления этих сложностей придуманные теми кто научился на этом зарабатывать.
Это скорее вторичная попытка приспособить под капитализм то что изначально основано на
Двойное лицензирование здесь - попытка усидеть на двух стульях. Побыть одновременно и коммунистом и капиталистом. Естественно это выглядит очень странно и внутренне противоречиво, потому что сами идеи коммунизма и капитализма взаимоисключающие.