function drawByCurves(ctx, points) {
ctx.beginPath();
ctx.setLineDash([]);
ctx.moveTo(points[0].x, points[0].y);
var dl = 0;
for (var i = 0; i < points.length - 2; i++) {
var dr = (points[i+2].y - points[i].y) / 2;
var a3 = dl + dr + 2 * (points[i].y - points[i+1].y);
var a2 = points[i+1].y - a3 - dl - points[i].y;
for (var t = 0; t <= 1; t+=.05) {
var y = a3; y = y*t+a2; y = y*t+dl; y = y*t+points[i].y;
ctx.lineTo(points[i].x + t * 50, y);
}
dl = dr;
}
ctx.strokeStyle = 'blue';
ctx.stroke();
}
Когда на третьем курсе был придуман этот алгоритм, слово «интерполяция» вселяло в меня ужас, а гугление по запросу «сглаживание графиков» не давало посильных пониманию результатов. Но как-то я дошел до кривых Безье и уж очень они мне понравились. Рисует быстро, алгоритм интуитивно понятный… Что еще надо для счастья.
Собственные алгоритмы всегда интуитивно понятнее ). Но рискну предположить, что обычный Катмулл-Ром на порядок проще и понятнее. Найти можно много где, в т.ч. и здесь https://habrahabr.ru/post/282441/
Посмотрел, там приводится пример функции подобной ступеньке Хэвисайда, с крутым фронтом спада, и интерполяция ее глобальными кубическим и рациональным сплайнами по 10 точкам, с демонстрацией преимущества последнего. Конечно, аргумент в знаменателе дает больше гибкости.
А эта книга у меня есть, и даже неоднократно читана. Скорее всего о функции Рунге идет речь, вечером посмотрю. Но нет никаких проблем при ее интерполяции, если только не пытаться интерполировать ее одним единственным полиномом по многим точкам, а если использовать не глобальные, а локальные методы (все перечисленные в статье — локальны), тогда все хорошо.
Спасибо, попробую поискать ее в инете. Но может это спецлитература и не оцифрована. Может речь идет о функции Рунге, которая приводится во всех примерах, когда хотят показать осцилляции полиномов Лагранжа высоких порядков, и на основании этого делают вывод, что «полиномы высоких порядков непригодны для интерполяции», хотя это совсем не так.
Можно было бы попробовать и ленивую модель вычислений. В принципе, ничего не мешает поэкспериментировать даже с этими интерпретаторами. Просто строгая модель для первой реализации более интуитивно понятна и не приводит к разрастанию цепочек недовычисленных санок и вообще нормальный порядок редукции лямбда-термов (по крайней мере, его наивная реализация) приводит к дублированию вычисления одинаковых цепочек выражений по несколько раз, в отличие от аппликативного. Без дополнительной оптимизации будет медленнее и более затратно по памяти, хотя для пет-прожекта и проверки концепции, повторюсь, можно попробовать, идея интересная.
В свою очередь думаю, что по этой паре интерпретаторов можно написать не один десяток полноценных статей, каждая по своей отдельной тематике, где все расписывать уже в деталях. В личной переписке я просил вас (и здесь спрашиваю всех участников) — хотели бы вы видеть статьи, детальнее раскрывающие какие-либо отдельные вопросы, и если да — то какие? Насколько я понял, одно предложение уже есть — реализация TCO. Хорошо, попробую написать нескучно про это. Может кто что еще добавит (хотя обсуждаем тему только мы с вами, а после ухода статьи с первой страницы на второй день вряд-ли кто еще подключится).
Именно. Потому что хаскель сам отлично оптимизирует любые рекурсии, в том числе и хвостовые. А Java не оптимизирует даже хвостовые. И когда я перевел реализацию на Java, я сразу столкнулся с постоянными неприятными переполнениями стека при вычислениях — у меня же нет циклов (на самом деле есть, особая форма while, но это просто ради пробы, можно ее выпилить из языка), все делается через рекурсию, каждое вычисление идет в своем одном потоке, размер стека которого можно задать при старте приложения в параметре. Я потратил некоторое количество сил и времени для полного решения этого вопроса — вынос вычислений со стека в кучу, передача вычисления в дочерний поток и т.п. Но все эти варианты работали медленно и/или ненадежно, поэтому я остановился на общепринятой полумере — оптимизации только хвостовых вызовов, но автоматическом (программисту не надо явным образом указывать что это хвостовой вызов, как в некоторых других языках — интерпретатор определяет это сам). И в результате у меня библиотечная функция левой свертки списка foldl волшебным образом стала не переполнять стек на больших списках, а правая свертка foldr продолжает переполнять. Пришлось и некотороые другие (какие возможно) библиотечные функции переписать через хвостовую рекурсию. Как писал Норвиг в комментариях про lispy2:
there is a potential problem: if every recursive call grows the runtime stack, then the depth of recursion, and hence the ability to loop, will be limited. In some implementations the limit will be as small as a few hundred iterations. This limitation can be lifted by altering eval so that it does not grow the stack on all recursive calls--only when necessary.
http://norvig.com/lispy2.html
Вот и у меня — only when necessary, без лишних указаний со стороны программиста.
Но конечно есть задачи, которые трудно реализовать только через хвостовую рекурсию. В моих демо-примерах есть пример работы с бесконечными потоками (реализованными средствами исключительно самого языка, через макросы и мемоизацию), но они переполняют стек при относительно длинных запросах. Частичное решение — запускать интерпретатор с ключом — указанием размера стека потока побольше, при работе обычно используется максимум несколько потоков (в отдельных закладках), не считая потока событий GUI.
Я видел, что вы посмотрели на гитхабе и мой Haskell-проект реализации этого языка. В мелочах эти 2 реализации отличаются (автоматическое расширение чисел до типа double при арифметических операциях или разная арифметика для разных типов и т.п.), но в плане макросов они вроде эквивалентны. Можно конечно допилить Haskell-реализацию, если бы не лень (каламбурчик, внутренняя хаскельная лень как раз ничуть не мешает :)) Было бы интересно, если кто-нибудь ради забавы наваяет на Liscript решение какой-нибудь задачки, можно с блэкджеком и макросами :)
Спасибо, я читал начало. Судя по всему, имеет смысл прочитать полностью. А макросы я по своим кустарным представлениям сделал, это потом я уже увидел заметку про фёст-класс рантайм-макросы и узнал много нового о себе после употребления этого словосочетания на ЛОРе :) Но они работают, и синтаксис проще стандартных Лисповых макросов. Но не имея опыта с последними, я не могу сказать, мои Уже или шире по возможностям.
Вот как раз на продолжениях остановился. Есть мысль их сделать в перспективе. Изучив детальнее что это такое, для начала :) А вообще, можно развивать сахар (параметры функций по умолчанию и т.п.), фичи (те же продолжения, более полноценное interoperability с Java — создание экшенов по кнокпам или другим событиям) или что-то еще. Но продолжения в планах имеются, и с достаточным приоритетом.
Без Безье
Собственные алгоритмы всегда интуитивно понятнее ). Но рискну предположить, что обычный Катмулл-Ром на порядок проще и понятнее. Найти можно много где, в т.ч. и здесь https://habrahabr.ru/post/282441/
https://github.com/JeffBezanson/femtolisp
И вдогонку, для полноты картины, если вдруг кто интересуется, но еще не видел: https://github.com/kanaka/mal
Вот и у меня — only when necessary, без лишних указаний со стороны программиста.
Но конечно есть задачи, которые трудно реализовать только через хвостовую рекурсию. В моих демо-примерах есть пример работы с бесконечными потоками (реализованными средствами исключительно самого языка, через макросы и мемоизацию), но они переполняют стек при относительно длинных запросах. Частичное решение — запускать интерпретатор с ключом — указанием размера стека потока побольше, при работе обычно используется максимум несколько потоков (в отдельных закладках), не считая потока событий GUI.