Эти линии показывают триангуляцию Делоне — разбиение формы (набора точек и текстуры между ними) на треугольники, каждый из которых затем покусочным аффинным преобразованием транслируется в новые координаты
примерно так
Имеет два изображения одного объекта с небольшим интервалом:
триангулируем их:
и деформируем каждый отдельный треугольник, чтобы он приобрёл форму своего товарища из другой картинки:
Пиксели за пределами формы не входят в триангуляцию и поэтому не переносятся.
Смысл сего действия в итеративной подгонке формы под новое изображение, для чего используется diff между реальным и деформированным изрбражением, преобразованный алгоритм Лукаса-Канаде и много всего интересного, но главное, что AAM хорошо так опирается на именно триангуляцию, так что вполне логично, что она используется и для визуализации :)
Ну вот print — вроде грязная функция? А В Хаскеле можно передавать :)
Кто ж виноват, что в Haskell нет `foreach` :D
Это не «стиль», это пример, показывающий, что в императивном языке такая замена неэквивалентна, а потому она не является оптимизацией, она является деталью реализации, о которой программисты должны знать, чтобы не совать в map грязные функции.
Хм, вы имеете ввиду оптимизацию на уровне компилятора? Тогда я не очень понимаю её суть — насколько я понимаю, композитная функция `(f. g)` всё равно транслируется в машинный код как последовательное применение двух функций к каждому элементу. Или здесь можно ещё что-то соптимизировать?
Единственный раз, когда я видел полезность композиции функций для производительности, был в PySpark, где выражение (`rdd`, грубо говоря, — это большой-большой ленивый список, загружаемый с диска):
rdd.map(g).map(f)
транслировалось в
rdd.map(compose(f, g))
Но там это сделано из-за того, что каждый вызов к `.map` означает передачу данных между процессами Java и Python через диск, так что композиция функций уменьшает количество IO операций ровно вдвое. Это оптимизация на уровне PySpark, которая может произойти, а может по определённым причинам и не произойти. Но, опять же, от программиста ожидается, что он не будет стрелять себе в ногу и передавать в `.map` грязные функции, от порядка вызова которых может измениться результат.
Обратите внимание, что в этом случае ни Java (Scala), ни Python чистыми языками не являются.
Да, ленивые вычисления могут выполняться в любом порядке.
Это не совсем так. Ленивый, он же нормальный порядок вычислений определён абсолютно строго, просто иначе, чем аппликативный. Например, при аппликативном порядке выражение `f(g(x))` будет вычисляться строго слева направо (сначала `x`, потом `g()`, потом `f()`), а при нормальном — сначала слева направо (вызовы функций), а потом слева направо («закрытие» функций). Но этот порядок всегда строго определён и вполне поддаётся анализу.
У вас ужасный, ужасный, ужасный стиль программирования на Python. Как я уже говорил, если кто-то применяет функции с побочными эффектами в функциях типа `map`, то ему нужно отрывать руки с корнем, вне зависимости от языка.
Эээ, это вы с учётом того, что приведённый кусок — это готовый к исполнению код, а конкретно ваш пример:
foo = take n
bar = filter f
baz = map g
quux = foo . bar . baz
транслируется в
foo = partial(itake, n)
bar = partial(ifilter, f)
baz = partial(imap, g)
quux = compose(foo, bar, baz)
Так что да, я бы сказал, что именно чуть-чуть.
Вот здесь дерево ленивое — две строки.
Нуу, тут хоть и две строчки, но специальных фич Haskell-а целая куча — и ленивые вычисления, и рекурсия через фиксированную точку, и развитая система типов. Я даже не буду пытаться повторить это на императивном динамически-типизированном Python. Но просто, чтобы показать, что всё возможно и на нём, вот вам простая реализация рекурсивного дерева:
class Tree(object):
def __init__(self, n):
self.n = n
def __getattr__(self, name):
if name == 'left':
return Tree(self.n + 1)
elif name == 'right':
return Tree(self.n + 2)
else:
raise AttributeError("No such attribute: %s" % (name))
def __repr__(self):
return "Tree(%s)" % (self.n,)
И пример использования:
In [30]: t = Tree(1)
In [31]: t
Out[31]: Tree(1)
In [32]: t.right
Out[32]: Tree(3)
In [33]: t.right.right
Out[33]: Tree(5)
In [34]: t.right.left
Out[34]: Tree(4)
В общем и целом, мы с вами вроде во всём согласны, а этот code golf начинает отнимать время, поэтому если критических возражений нет, предлагаю на этой оптимистической ноте и закончить.
Уж лучше идиоматично через list comprehensions, а то так и нечитаемее, и тормознее. А если идиоматично, то уже bar оттуда не вычленить так просто, композиционность страдает.
Ну так и язык не функциональный, понятно, что сложные функциональные штуки типа каррирования и композиции функции в нём будут хотя бы чуть-чуть, но сложнее синтаксически :D
Как же это не обладает, когда _может_ обладать (у меня там недаром f и g — произвольные функции), а это для оптимизатора весьма важно.
А, вы про `f` и `g`. Ну, тут есть 2 момента. Во-первых, Python по-умолчанию считает своих разработчиков достаточно вменяемыми, чтобы не передавать в `filter` и `map` функции с побочными эффектами. Если кто-то всё-таки передаёт, то тут уж извините, отстрелить себе ногу, как известно, можно в любой ситуации. Во-вторых, Python — это как раз тот язык, в котором про оптимизацию особо не думают. Если хотите, могу переписать всё это на высокопроизводительной Julia ;)
Можно даже бесконечные деревья (как и списки) строить. Необязательно последовательно. Те же самые filter, map, что-либо ещё.
Ну так ради б-га, кто ж мешает. Python здесь ничем не отличается от Haskell (или Java, или C++): выбираете абстрактную функцию с поведением (например, `map`), задаёте требуемый интерфейс (например, `get_next`), реализуете интерфейс для своего класса и вуа-ля!
Итератор ходит вперёд. По дереву я могу своей функцией идти в том направлении, в котором мне надо. Это уже другой тип итератора совсем. Ходить вперёд — частый, хотя и распространённый, случай.
Не очень понял, о какой функции, которая может ходить в разных направлениях, идёт речь, но опять же, не вижу причин, почему нельзя то же самое сделать на любом другом языке.
Да. При этом в чистом языке можно подряд идущие filter f. map g сворачивать в использование одной функции (Rewrite rules), потому что ни f, ни g не производят побочных эффектов.
Я ничего не знаю про Rewrite rules, но ни одна из перечисленных функций не обладает побочными эффектами.
А что если у нас не списки, а деревья? Как сделать всё то же, но для своего типа данных?
По деревьям вы тоже итерируете последовательно? Тогда добавьте интерфейс итератора к вашему объекту (переопределите некоторые специальные функции) и сможете итерировать по ним.
Я там выше упоминал take n. filter f. map g, как это переписать на императивный?
А вас какая часть этого выражения интересует? Функции работы со списками, каррирование или композиция функций? В доброй половине императивных языков, с которыми я имею дело, все эти вещи либо есть из коробки, либо добавляются в несколько строк кода. Например, если нужно просто прогнать список `a` через эти 3 функции, то идеоматичный код на Python будет выглядеть так:
[g(x) for x in a if f(x)][:n]
Если вам больше по душе вид с функциями, то можно ещё и так:
from itertools import *
islice(ifilter(f, imap(g, a)), n)
Хотя, конечно, более кашерный подход с точки зрения Python будет вынлядеть так:
from itertools import *
r = imap(g, a)
r = ifilter(f, r)
r = islice(r, n)
Префикс `i`, кстати, говорит о том, что мы работаем с итераторами, т.е. теми же самыми ленивыми списками.
Только сложно убедить того, кто не пользовался этим.
Если вы это про меня, то на функциональных языках я пишу года этак с 2008, причём года 3 писал продакшен системы на Лиспе, про который говорит в своей статье Грэм. Только нужно понимать, что любая фича любого языка появилась не просто так, и функциональные языки дают прирост скорости разработки только в своей небольшой области. Так же, как и императивные языки дают серьёзный выигрыш в своей области. А в большинстве задач вообще всё равно, какую парадигму использовать.
мутабельность и прочие плюшки тоже не бесплатны — увеличивают «стоимость» разработки.
Ну это тоже спорное утверждение: сравните, например, Haskell и Python — те, кто пробовал писать продакшн системы на обоих, говорят, что на Питоне таки быстрее ;)
По поводу выделения гигабайта или 100 Мб — как поступают в реализации std::vector?
Я не пишу на C++ и не знаю, как там это реализовано, но в Java аналогичная структура — ArrayList — хранит массив с запасом, а при достижении границы переаллоцирует весь массив. К менеджерам памяти (или, если хотите, мендежеру буферов) такая схема неприменима, хотя бы потому что любое удаление элемента (т.е. освобождение памяти) требовало бы полного переписывания массива/преаллоцированного куска памяти.
То же и про кольцевой буфер.
Действительно, то же и про кольцевой буфер.
Про бесплатный сыр никто не говорил и не ожидал.
Нет, вы говорили про сыр, стоимостью которого можно пренебречь. Когда я показал, что стоимость велика, вы начали доказывать, что где-то есть сыр дешевле.
Уж не напоминаю, что в самой статье тема производительности тоже затрагивалась, причём с однозначным ответом на этот вопрос.
Это ветка ответа на мой первый комментарий началась с ответа beeruser относительно производительности, про тругие юз кейсы для модификации переменных и смены типа я ответил дальше (параграф про `eval()`).
Внутри MemoryManager.GetMat может быть, например, кольцевой буфер.
Который при достижении лимита либо начнёт перезаписывать старые значения, либо вообще откажется выделять новые объекты. Шикарный вариант.
Или дерево с ссылками на свободные chunkи памяти.
И повторить урезанную функциональность malloc-а. Действительно, давайте изобретём велосипед.
Или что угодно, что может оперировать с _предвыделенными_ областями памяти.
malloc и garbage collector могут работать с предвыделенными областями памяти. Иногда могут запрашивать у операционной системы дополнительную память, но большинство аллокаций происходит в предвыделенной области. Внезапно.
Единственная задача — предоставить абстракцию, чтобы в этот логический блок памяти записывались данные только для матрицы dst, и не записывались никакие другие.
Вы считаете, что для вас эту абстракцию уже кто-то предоставит, причём реализованную суперэффективно, так что она не будет снижать производительность. Так вот, не предоставит — уже 60 лет люди с этой задачей борятся, пока не решили.
Принципиальная реализация не важна.
Если мы говорим про производительность, а мы уже выяснили, что в этом треде мы говорим про неё, то важен даже порядок записи в кеш процессора, а аллоцирование памяти — вообще один из первых пунктов оптимизации.
Вы лучше скажите почему «выделение» — это всегда выделение.
Быстрое выделение памяти
Быстрое освобождение памяти
Общий случай
Выберете 2 из 3. Если вы хотите быстро выделять память (например, просто увеличить указатель в куче в системах со сборщиком мусора), то придётся потретить время на её освобождение (сборка мусора). Если вы хотите быстро освобождать (пометить кусок памяти как свободный), то придётся потратить время на поиск подходящего куска в следущий раз (как это делает malloc). В некоторых специальных случаях можно получить и (1) и (2) (например, стек и выделяется, и уничтожается простым изменением указателя), но это налагает серьёзные ограничения (стек может либо расти, либо раскручиваться, сохранение и разрушение произвольных фреймов невозможно). Как я уже говорил, найдёте способ — пишите кандидатскую.
И ещё было бы интересно понять почему ни один из описанных аллокаторов не решает задачу.
Начнём с того, что каждый из этих аллокаторов требует предварительного выделения некоторого объёма памяти, какого именно ни создатели библиотеки, ни чаще всего даже пользователи библиотеки не знают. Вы можете выделить 1Gb и использовать 256К, а можете выделить 100Мб и через 3 минуты свалиться с нехваткой памяти.
Кроме того:
Linear Allocator вообще не умеет освобождать буферы по одному, только очищать всю выделенную память сразу. Мне вообще сложно придумать, где он применим
Stack Allocator, как и обычный стек, не позволяет произвольного выделения памяти. Т.е. буфер изображения #3 мы сможем уничтожить не раньше, чем уничтожим буфер изображения #4
FreeList Allocator — по сути, тот же malloc, но без системных вызовов и в маленьком куске памяти. Результаты абсолютно бессмысленны: во-первых, используется метод first-fit вместе оптимального best-fit, во-вторых, сначала делается N аллокаций (константная операция, учитывая first-fit), а затем N деаллокаций (опять же, константная операция). Если попробовать выделять и освобождать память вперемешку и на большем объёме памяти, результаты будут как раз как у malloc
Pool Allocator работает только с буферами фиксированного размера. Так в документации и напишем: накладываем фильтры на изображение, но только если оно размера 96x96.
Так что бесплатного сыра не бывает, пора бы это уже осознать.
Я начинаю подозревать, что вы меня троллите. Мы 16-й комментарий обсуждаем стратегии выделения памяти, а вы всю суть вопроса снова сводите к какому-то абстрактному классу. А что должно находиться внутри `MemoryManager.GetMat`?
Я могу подробно описать, почему ни один из описанных аллокаторов не решает задачу и почему «выделение» — это всегда выделение. Но как бы подробно я это ни описал, найдётся деталь или ветвь размышления, которую я не покрыл, и мне опять и опять придётся писать большие тексты. Поэтому давайте сделаем проще: вместо того, чтобы я доказывал, что это невозможно, вы докажите, что это сделать можно. Т.е. с помощью кастомных аллокаторов (или чего угодно ещё) трансформируйте функцию
Можно вручную, а можно предусмотреть и автоматическую сборку мусора (которая, можно сказать, из FP родом).
Т.е. мы снова приходим просто к менеджеру памяти без использования буферов вообще.
А я говорю, что скорость выделения может быть очень высока и этим можно пренебречь.
Пример на Julia:
# импортируем BLAS
julia> using Base.LinAlg.BLAS
# создаём два исходных массива A и B плюс один буфер C
julia> A = rand(10000, 100); B = rand(100, 10000); C = zeros(10000, 10000);
# перемножение матриц с выделением памяти
julia> @time for i=1:10 C = gemm('N', 'N', 1.0, A, B) end
8.822950 seconds (13.02 k allocations: 7.451 GB, 6.15% gc time)
# перемножение матриц с использованием преаллоцированного буфера
julia> @time for i=1:10 gemm!('N', 'N', 1.0, A, B, 0.0, C) end
4.607092 seconds
Не знаю как вы, но я бы не стал пренебрегать оптимизацией алгоритма на 92%.
Вы опять всё сводите к какому-то абстрактному пулу предвыделенных буферов. Ну пусть будет у нас пул из 1000 буферов, пусть даже каждый буфер уже будет нужного размера — что угодно. Мы вызываем нашу функцию, результат записываем в буфер #1, затем в буфер #2, затем в буфер #3 и т.д. В конце концов буферы у нас заканчиваются, что будем делать в этом случае?
О каких заранее выделенных областях внутри функции идёт речь? О преаллоцированной статической переменной (в смысле C++) внутри фукнции? Автор функции не может знать, матрицу какого размера ему передадут. О «бесконечном пуле буферов»? Это то же самое, что просто доступ в RAM, и в RAM-е использованную память (свободные буферы) нужно когда-то освобождать.
Приведите, пожалуйста, пример кода функции преобразования массива, которая не принимает выходной буфер как параметр (т.е. не модифицирует переданные в неё параметры), и не выделяет новую память при каждом вызове.
Давайте ближе к телу. Возьмём функцию `filter2D` из OpenCV, которая, грубо говоря, имеет сигнатуру:
void filter2D(Mat src, Mat dst);
Где `src` — исходная картинка, а `dst` — выходная матрица, в которую записывается результат (destination). Возможно ли переписать эту функцию в функциональном стиле, чтобы она не модифицировала `dst` и при этом не требовала выделения новой памяти? При этом не забываем, что функция библиотечная, так что вызываемые и вызывающий код компилируются в разное время и разными компиляторами.
триангулируем их:
и деформируем каждый отдельный треугольник, чтобы он приобрёл форму своего товарища из другой картинки:
Пиксели за пределами формы не входят в триангуляцию и поэтому не переносятся.
Смысл сего действия в итеративной подгонке формы под новое изображение, для чего используется diff между реальным и деформированным изрбражением, преобразованный алгоритм Лукаса-Канаде и много всего интересного, но главное, что AAM хорошо так опирается на именно триангуляцию, так что вполне логично, что она используется и для визуализации :)
Кто ж виноват, что в Haskell нет `foreach` :D
Хм, вы имеете ввиду оптимизацию на уровне компилятора? Тогда я не очень понимаю её суть — насколько я понимаю, композитная функция `(f. g)` всё равно транслируется в машинный код как последовательное применение двух функций к каждому элементу. Или здесь можно ещё что-то соптимизировать?
Единственный раз, когда я видел полезность композиции функций для производительности, был в PySpark, где выражение (`rdd`, грубо говоря, — это большой-большой ленивый список, загружаемый с диска):
транслировалось в
Но там это сделано из-за того, что каждый вызов к `.map` означает передачу данных между процессами Java и Python через диск, так что композиция функций уменьшает количество IO операций ровно вдвое. Это оптимизация на уровне PySpark, которая может произойти, а может по определённым причинам и не произойти. Но, опять же, от программиста ожидается, что он не будет стрелять себе в ногу и передавать в `.map` грязные функции, от порядка вызова которых может измениться результат.
Обратите внимание, что в этом случае ни Java (Scala), ни Python чистыми языками не являются.
Это не совсем так. Ленивый, он же нормальный порядок вычислений определён абсолютно строго, просто иначе, чем аппликативный. Например, при аппликативном порядке выражение `f(g(x))` будет вычисляться строго слева направо (сначала `x`, потом `g()`, потом `f()`), а при нормальном — сначала слева направо (вызовы функций), а потом слева направо («закрытие» функций). Но этот порядок всегда строго определён и вполне поддаётся анализу.
Эээ, это вы с учётом того, что приведённый кусок — это готовый к исполнению код, а конкретно ваш пример:
транслируется в
Так что да, я бы сказал, что именно чуть-чуть.
Нуу, тут хоть и две строчки, но специальных фич Haskell-а целая куча — и ленивые вычисления, и рекурсия через фиксированную точку, и развитая система типов. Я даже не буду пытаться повторить это на императивном динамически-типизированном Python. Но просто, чтобы показать, что всё возможно и на нём, вот вам простая реализация рекурсивного дерева:
И пример использования:
В общем и целом, мы с вами вроде во всём согласны, а этот code golf начинает отнимать время, поэтому если критических возражений нет, предлагаю на этой оптимистической ноте и закончить.
Ну так и язык не функциональный, понятно, что сложные функциональные штуки типа каррирования и композиции функции в нём будут хотя бы чуть-чуть, но сложнее синтаксически :D
А, вы про `f` и `g`. Ну, тут есть 2 момента. Во-первых, Python по-умолчанию считает своих разработчиков достаточно вменяемыми, чтобы не передавать в `filter` и `map` функции с побочными эффектами. Если кто-то всё-таки передаёт, то тут уж извините, отстрелить себе ногу, как известно, можно в любой ситуации. Во-вторых, Python — это как раз тот язык, в котором про оптимизацию особо не думают. Если хотите, могу переписать всё это на высокопроизводительной Julia ;)
Ну так ради б-га, кто ж мешает. Python здесь ничем не отличается от Haskell (или Java, или C++): выбираете абстрактную функцию с поведением (например, `map`), задаёте требуемый интерфейс (например, `get_next`), реализуете интерфейс для своего класса и вуа-ля!
Не очень понял, о какой функции, которая может ходить в разных направлениях, идёт речь, но опять же, не вижу причин, почему нельзя то же самое сделать на любом другом языке.
Я ничего не знаю про Rewrite rules, но ни одна из перечисленных функций не обладает побочными эффектами.
По деревьям вы тоже итерируете последовательно? Тогда добавьте интерфейс итератора к вашему объекту (переопределите некоторые специальные функции) и сможете итерировать по ним.
А вас какая часть этого выражения интересует? Функции работы со списками, каррирование или композиция функций? В доброй половине императивных языков, с которыми я имею дело, все эти вещи либо есть из коробки, либо добавляются в несколько строк кода. Например, если нужно просто прогнать список `a` через эти 3 функции, то идеоматичный код на Python будет выглядеть так:
Если вам больше по душе вид с функциями, то можно ещё и так:
Хотя, конечно, более кашерный подход с точки зрения Python будет вынлядеть так:
Префикс `i`, кстати, говорит о том, что мы работаем с итераторами, т.е. теми же самыми ленивыми списками.
Если вы это про меня, то на функциональных языках я пишу года этак с 2008, причём года 3 писал продакшен системы на Лиспе, про который говорит в своей статье Грэм. Только нужно понимать, что любая фича любого языка появилась не просто так, и функциональные языки дают прирост скорости разработки только в своей небольшой области. Так же, как и императивные языки дают серьёзный выигрыш в своей области. А в большинстве задач вообще всё равно, какую парадигму использовать.
Ну это тоже спорное утверждение: сравните, например, Haskell и Python — те, кто пробовал писать продакшн системы на обоих, говорят, что на Питоне таки быстрее ;)
Я не пишу на C++ и не знаю, как там это реализовано, но в Java аналогичная структура — ArrayList — хранит массив с запасом, а при достижении границы переаллоцирует весь массив. К менеджерам памяти (или, если хотите, мендежеру буферов) такая схема неприменима, хотя бы потому что любое удаление элемента (т.е. освобождение памяти) требовало бы полного переписывания массива/преаллоцированного куска памяти.
Действительно, то же и про кольцевой буфер.
Нет, вы говорили про сыр, стоимостью которого можно пренебречь. Когда я показал, что стоимость велика, вы начали доказывать, что где-то есть сыр дешевле.
Это ветка ответа на мой первый комментарий началась с ответа beeruser относительно производительности, про тругие юз кейсы для модификации переменных и смены типа я ответил дальше (параграф про `eval()`).
Который при достижении лимита либо начнёт перезаписывать старые значения, либо вообще откажется выделять новые объекты. Шикарный вариант.
И повторить урезанную функциональность malloc-а. Действительно, давайте изобретём велосипед.
malloc и garbage collector могут работать с предвыделенными областями памяти. Иногда могут запрашивать у операционной системы дополнительную память, но большинство аллокаций происходит в предвыделенной области. Внезапно.
Вы считаете, что для вас эту абстракцию уже кто-то предоставит, причём реализованную суперэффективно, так что она не будет снижать производительность. Так вот, не предоставит — уже 60 лет люди с этой задачей борятся, пока не решили.
Если мы говорим про производительность, а мы уже выяснили, что в этом треде мы говорим про неё, то важен даже порядок записи в кеш процессора, а аллоцирование памяти — вообще один из первых пунктов оптимизации.
Выберете 2 из 3. Если вы хотите быстро выделять память (например, просто увеличить указатель в куче в системах со сборщиком мусора), то придётся потретить время на её освобождение (сборка мусора). Если вы хотите быстро освобождать (пометить кусок памяти как свободный), то придётся потратить время на поиск подходящего куска в следущий раз (как это делает malloc). В некоторых специальных случаях можно получить и (1) и (2) (например, стек и выделяется, и уничтожается простым изменением указателя), но это налагает серьёзные ограничения (стек может либо расти, либо раскручиваться, сохранение и разрушение произвольных фреймов невозможно). Как я уже говорил, найдёте способ — пишите кандидатскую.
Начнём с того, что каждый из этих аллокаторов требует предварительного выделения некоторого объёма памяти, какого именно ни создатели библиотеки, ни чаще всего даже пользователи библиотеки не знают. Вы можете выделить 1Gb и использовать 256К, а можете выделить 100Мб и через 3 минуты свалиться с нехваткой памяти.
Кроме того:
Так что бесплатного сыра не бывает, пора бы это уже осознать.
в функцию
без необходимости динамически выделять память.
Т.е. мы снова приходим просто к менеджеру памяти без использования буферов вообще.
Пример на Julia:
Не знаю как вы, но я бы не стал пренебрегать оптимизацией алгоритма на 92%.
Приведите, пожалуйста, пример кода функции преобразования массива, которая не принимает выходной буфер как параметр (т.е. не модифицирует переданные в неё параметры), и не выделяет новую память при каждом вызове.
Где `src` — исходная картинка, а `dst` — выходная матрица, в которую записывается результат (destination). Возможно ли переписать эту функцию в функциональном стиле, чтобы она не модифицировала `dst` и при этом не требовала выделения новой памяти? При этом не забываем, что функция библиотечная, так что вызываемые и вызывающий код компилируются в разное время и разными компиляторами.