Здравствуйте, Sinclair, Вы писали:
S>А вам обычно мультипликативный моноид и не нужен. Вам обычно нужно умение вызывать встроенный оператор *.
Всё верно, для многих алгоритмов нужна не абстракция «моноид», а только абстракция «замкнутая бинарная операция».
S>Ну, вот как в примере про умножение матриц — там нафиг не нужна единица, нужно собственно умножение, сложение, и zero, он же default.
Так вроде и zero не нужен? Когда у тебя коллекции непустые (здесь коллекции это строки и столбцы матрицы), то начальный элемент задавать не нужно (reduce вместо fold).
Q>А я объяснил, почему твоё объяснение некорректное. Про straw man не только к AlexRK относилось, но и к тебе в первую очередь; почитай, пожалуйста.
Корректное. Просто тебе не нравится сама мысль о том что кто-то может прекрасно знать M-words и при этом весьма скептически на них смотреть. Я в первом же утверждении написал "людям сначала нравится элегантность и единообразность монад, моноидов и этого всего". И продолжаю придерживаться этого тезиса. Для меня эти конструкции одинаково "заражают" код. Решают местечковую проблемку, но порождают другую, которая на дистанции только растёт.
_>>Сейчас ты решил что всё понял. Q>Да, я всё понял: ты слышал звон, но не знаешь, где он. M-word — эта сложна! Нипанятна!
Ну вот пруф. Ты решил что мне именно "сложна и нипанятна". Представить что кому-то кроме достоинств понятны и недостатки — пока никак.
Q>А, речь не про этот M-word?.. Всё равно от лукавого, буквы-то те же! Нафиг не нужон моноид ваш!
Это то что ты понял. А то что там было написано: "эти абстракции порождают похожие проблемы в большом проекте".
Q>>>Внезапно, код с моноидом в стиле как на видео будет быстрее, чем стандартная лапша с делегатами : ) Q>Хоть по этому вопросу возражений нет.
Ты пропустил замечание что для сложения и умножения чаще всего вообще не стоит лепить лапшу с делегатами.
Q>Если при использовании IMonoid<T> непременно такие сложности возникнут, то они же неизбежно должны возникнуть и при использовании интерфейса IEqualityComparer<T>? Сценарии использования у них ведь строго одинаковые.
Разные. Компаратор очень ограничен в возможностях. Предел комбинирования для компараторов — библиотечка OrderBy...ThenBy, и всё. Новые экземпляры T компаратор не порождает. Моноиды гибче и в терминальной стадии распространения могут заменять собой не то что IEqualityComparer, а даже просто IComparer.
Здравствуйте, hi_octane, Вы писали:
_>Ты пропустил замечание что для сложения и умножения чаще всего вообще не стоит лепить лапшу с делегатами.
Хорошо. Что тогда нужно лепить вместо моноида в этом алгоритме? Как его переписать без еретического моноида?
internal static T Reduce<T, TMonoid>(this IEnumerable<T> items, TMonoid monoid)
where TMonoid : IMonoid<T>
{
if (items is null)
throw new ArgumentNullException(nameof(items));
T result = monoid.Identity;
foreach (T item in items)
result = monoid.Combine(result, item);
return result;
}
Q>>Если при использовании IMonoid<T> непременно такие сложности возникнут, то они же неизбежно должны возникнуть и при использовании интерфейса IEqualityComparer<T>? Сценарии использования у них ведь строго одинаковые. _>Разные. Компаратор очень ограничен в возможностях. _>Новые экземпляры T компаратор не порождает.
Хорошо а IEnumerable<T> — это тоже харам? Он же порождает; ты его тоже избегаешь? Потому что на энумераторах можно много чего наворотить.
Здравствуйте, Sinclair, Вы писали:
Q>>Даже конструктор не нужен (его констрейнт и вызов), достаточно default(M) с констрейнтом struct. В той статье «Concept C#: Type Classes for the Masses» именно такой подход рассматривался. S>Тот же конструктор, вид в профиль — построен на автоматической доступности default constructor для структур.
Интуитивно кажется, что это не так, и «default(TMonoid)» должен быть эффективнее, чем «new TMonoid()» для создания экземпляров value-типов вроде decimal в generic-коде. Хотя бы из-за Activator.CreateInstance().
Но точно не знаю, так что побенчмаркал. В .NET Core < 3.0 действительно new TMonoid() заметно медленнее. Но в .NET Core 3.0+ уже разницы нет. Activator.CreateInstance() по-прежнему есть в IL, но, видимо, JIT как-то лучше оптимизирует.
Здравствуйте, Qbit86, Вы писали:
Q>Интуитивно кажется, что это не так, и «default(TMonoid)» должен быть эффективнее, чем «new TMonoid()» для создания экземпляров value-типов вроде decimal в generic-коде. Хотя бы из-за Activator.CreateInstance(). Q>Но точно не знаю, так что побенчмаркал. В .NET Core < 3.0 действительно new TMonoid() заметно медленнее. Но в .NET Core 3.0+ уже разницы нет. Activator.CreateInstance() по-прежнему есть в IL, но, видимо, JIT как-то лучше оптимизирует.
Здравствуйте, Qbit86, Вы писали:
Q>Здравствуйте, Sinclair, Вы писали:
S>>Надо не IEnumerable, а int[] items. Там 50% времени — это вызовы в GetNext.
Q>Эта уловка называется «moving the goalspots» [1][2]
Нет. Если внимательно посмотреть в мой ответ про перформанс, то окажется, что там приведён вот такой код:
public int AddIntegers(int[] ints)
{
int result=0;
foreach(var i in ints)
result+=i;
return result
}
Это вы всё время стараетесь искусственно замедлить забег Ахилла
Q>Алгоритмы-то всё-таки пишутся не только над массивами, а над произвольными структурами (деревья, графы общего вида, etc).
Это как раз понятно; но обычной проблемой обобщённых алгоритмов такого вида является то, что они работают плохо и на массивах.
Q>Но ладно! Начав писать бенчмарки, сложно остановиться.
Q>
internal static T Reduce<T, TMonoid>(this T[] items, TMonoid monoid)
Q> where TMonoid : IMonoid<T>
Q>{
Q> if (items is null)
Q> throw new ArgumentNullException(nameof(items));
Q> T result = monoid.Identity;
Q> for (int i = 0; i != items.Length; ++i)
Q> result = monoid.Combine(result, items[i]);
Q> return result;
Q>}
Q>internal static int ReduceInt32(this int[] items)
Q>{
Q> if (items is null)
Q> throw new ArgumentNullException(nameof(items));
Q> int result = 0;
Q> for (int i = 0; i != items.Length; ++i)
Q> result += items[i];
Q> return result;
Q>}
Во-первых, давайте замерим хотя бы на десятке тысяч интов. Для десяти целых почти любой способ будет приемлемым, даже если складывать их передавая в javascript.
Во-вторых, использование i != items.Length вместо i < items.Length добавляет range check к каждой итерации. Интересно, что для линейного массива он вроде бы не сказывается на быстродействии. Для 2d массивов замедление весьма существенное — может быть,
В-третьих, удивительно, но факт: JIT всё же порождает разный код для generic случая и для специализации. Если починить проблему с !=, то generic версия начинает работать вот так:
Здравствуйте, Serginio1, Вы писали:
S>Здравствуйте, Sinclair, Вы писали:
S>Берем QuikSort и ничего там переопределять вообще не нужно.
Да, только в C# не работает. S>И куча алгоритмов для арифметических типов переопределять не надо. Написал для инта проверил, и все остальное для всех алгеброических типов идет.
Коллега, вы сецчас пишете о чём-то своём. S>Суть то ролей в том, что бы ты использовал текущую перегрузку опрераторов. Не хочешь действуй как и раньше только вместо
Ничего подобного в ролях нету. S> В твоем примере можно использовать текущие перегрузки операторов.
Нельзя.
Мэдс же показал код — чтобы обобщённый код подхватил операторы типа +, нужно, чтобы либо генерик-параметр реализовал IMonoid<T> (ну, или там IRing<T>), либо руками выписывать роль, в которой IMonoid<int>.operator+ мапится на int.operator+.
Чтобы этот же код заработал не с int, а с Complex, надо опять руками выписывать роль ComplexAddMonoid и руками же скармливать её в генерик-параметр метода.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Qbit86, Вы писали:
Q>Всё верно, для многих алгоритмов нужна не абстракция «моноид», а только абстракция «замкнутая бинарная операция».
Ещё чаще нам нужно просто вызвать у типа operator +, а сделать это невозможно потому, что язык вплоть до нынешней версии устроен так, что это невозможно.
Трюк с instance monoid вы применяете не потому, что вам реально нужна возможность менять тип замкнутой операциии на лету, а чтобы обойти вот это ограничение, которое в С++ работает благодаря compile-time специализации.
То есть руками объясняете обобщённому коду, что плюс — это плюс, и он порождает почти такой же бинарь, как настоящий специализированный код.
S>>Ну, вот как в примере про умножение матриц — там нафиг не нужна единица, нужно собственно умножение, сложение, и zero, он же default.
Q>Так вроде и zero не нужен? Когда у тебя коллекции непустые (здесь коллекции это строки и столбцы матрицы), то начальный элемент задавать не нужно (reduce вместо fold).
Технически — да. С т.з. простоты кода удобнее писать с default/zero.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, Serginio1, Вы писали:
S>>Здравствуйте, Sinclair, Вы писали:
S>>Берем QuikSort и ничего там переопределять вообще не нужно. S>Да, только в C# не работает.
Ну так роли для этого и сделаны. S>>И куча алгоритмов для арифметических типов переопределять не надо. Написал для инта проверил, и все остальное для всех алгеброических типов идет. S>Коллега, вы сецчас пишете о чём-то своём. S>>Суть то ролей в том, что бы ты использовал текущую перегрузку опрераторов. Не хочешь действуй как и раньше только вместо S>Ничего подобного в ролях нету. S>> В твоем примере можно использовать текущие перегрузки операторов. S>Нельзя. S>Мэдс же показал код — чтобы обобщённый код подхватил операторы типа +, нужно, чтобы либо генерик-параметр реализовал IMonoid<T> (ну, или там IRing<T>), либо руками выписывать роль, в которой IMonoid<int>.operator+ мапится на int.operator+. S>Чтобы этот же код заработал не с int, а с Complex, надо опять руками выписывать роль ComplexAddMonoid и руками же скармливать её в генерик-параметр метода.
Там
public shape SGroup<T>
{
static T operator +(T t1, T t2);
static T Zero {get;}
}
This declaration says that a type can be an SGroup<T> if it implements a+ operator over T, and a Zero static property.
public extension IntGroup of int: SGroup<int>
{
public static int Zero => 0;
}
And the extension.
public static AddAll<T>(T[] ts) where T: SGroup<T> // shape used as constraint
{
var result = T.Zero; // Making use of the shape's Zero property foreach (var t in ts) { result += t; } // Making use of the shape's + operator return result;
}
И в примере Мэдс все тоже самое. Ты переопределяешь только
public static int Zero => 0;
И разница в том, что int[] нужно привести к IntGroup[]
В любом случае определить можно сделать один интерфейс для всех перегрузок операторов алгеброических типов и прописать для них роли
и использовать эти роли хоть откуда как Func<> Action итд.
и солнце б утром не вставало, когда бы не было меня
S>public int AddIntegers(int[] ints)
S>{
S> int result=0;
S> foreach(var i in ints)
S> result+=i;
S> return result
S>}
S>
. S>Я могу написать код, который делает обобщённый static T Reduce<T, TMonoid>(this IEnumerable<T> items, TMonoid monoid) быстрее, чем AddIntegers выше (без учёта времени прогрева), но это упраженение, которое я бы не стал заставлять делать каждого гражданского разработчика.
Будте добры, а то не верится что будет быстрее. Уж больно T Reduce<T, TMonoid>(this IEnumerable<T> items, TMonoid monoid) абстрактный, со всеми косвенностями.
Здравствуйте, Sinclair, Вы писали:
S>Нет. Если внимательно посмотреть в мой ответ про перформанс, то окажется, что там приведён вот такой код:
А если внимательно посмотреть родительский комментарий, то там приведён другой код.
S>Это вы всё время стараетесь искусственно замедлить забег Ахилла
А ты пытаешься навязать мне какую-то другую задачу. Хочешь итерироваться по массиву? Окей, тогда сначала материализуй исходный IEnumerable<T> в массив, и ходи по нему. Например, рёбра остовного дерева не в массиве приходят, а генерируются в процессе обхода графа.
Q>>Алгоритмы-то всё-таки пишутся не только над массивами, а над произвольными структурами (деревья, графы общего вида, etc).
Но даже если массивы. В обобщённом коде отстать от мономорфного всего на одну инструкцию промежуточного копирования — отличный результат, уже на порядок (десятичный) лучше протаскивания делегата в аналогичный Linq-метод.
S>обычной проблемой обобщённых алгоритмов такого вида является то, что они работают плохо и на массивах.
Насколько я вижу, отлично работают. Лучше, чем можно было бы ожидать. И компилятор в CIL, и JIT из CIL.
S>Во-первых, давайте замерим хотя бы на десятке тысяч интов.
Окей, исправил в бенчмарке на 10 тысяч. Хоть это и не так важно, имхо; если нужна большая точность и статистическая значимость, то можно просто RunMode.Short исправить на RunMode.Long.
S>Во-вторых, использование i != items.Length вместо i < items.Length добавляет range check к каждой итерации. Интересно, что для линейного массива он вроде бы не сказывается на быстродействии.
Окей, даже хоть и не сказывается, заменим на foreach, как в твоём варианте.
S>В-третьих, удивительно, но факт: JIT всё же порождает разный код для generic случая и для специализации. Если починить проблему с !=, то generic версия начинает работать вот так: S>
| Method | Mean | Error | StdDev | Median | Ratio | RatioSD | Code Size |
|----------------------- |-----------:|----------:|----------:|-----------:|------:|--------:|----------:|
| ReduceIntegersBaseline | 4.879 us | 0.0074 us | 0.0385 us | 4.879 us | 1.00 | 0.00 | 131 B |
| ReduceIntegers | 4.851 us | 0.0121 us | 0.0621 us | 4.876 us | 0.99 | 0.02 | 151 B |
| AggregateIntegers | 74.457 us | 0.1019 us | 0.5166 us | 74.364 us | 15.26 | 0.15 | 419 B |
Здравствуйте, Sinclair, Вы писали:
S>Ещё чаще нам нужно просто вызвать у типа operator +, а сделать это невозможно потому, что язык вплоть до нынешней версии устроен так, что это невозможно.
В C++ можно вызвать «operator +», да. А ещё позвать оператор %, оператор запятую и вообще любую дичь а-ля Perl, которую только сможет натопать по клавиатуре кот — компилятор-то шаблоны не проверяет. Нет constraint'ов как в C# и других языках здорового человека.
Здравствуйте, Qbit86, Вы писали:
Q>Интуитивно кажется, что это не так, и «default(TMonoid)» должен быть эффективнее, чем «new TMonoid()» для создания экземпляров value-типов вроде decimal в generic-коде.
Мы говорим об одной операции на вызов. Это дорого только в каких-то сценариях типа динамической композиции.
Если мы про массовую обработку, то можно себе позволить вообще на лету компилировать специализированный код всего цикла.
Вы больше теряете из-за того, что используете != вместо < при обходе массивов
Q>Но точно не знаю, так что побенчмаркал. В .NET Core < 3.0 действительно new TMonoid() заметно медленнее. Но в .NET Core 3.0+ уже разницы нет. Activator.CreateInstance() по-прежнему есть в IL, но, видимо, JIT как-то лучше оптимизирует.
Да, можно глянуть в финальный x86 — для тривиальных конструкторов там скорее всего не сильно хуже, чем тупо инкремент указателя кучи.
Но вы, конечно же, правы: если мы жмём такты, то interface over struct as generic parameter — то, что доктор прописал.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
S>public shape SGroup<T>
S>{
S> static T operator +(T t1, T t2);
S> static T Zero {get;}
S>}
S>
S>
S>This declaration says that a type can be an SGroup<T> if it implements a+ operator over T, and a Zero static property.
S>
S>public extension IntGroup of int: SGroup<int>
S>{
S> public static int Zero => 0;
S>}
S>
S>
S>And the extension.
S>
S>public static AddAll<T>(T[] ts) where T: SGroup<T> // shape used as constraint
S>{
S> var result = T.Zero; // Making use of the shape's Zero property
S> foreach (var t in ts) { result += t; } // Making use of the shape's + operator
S> return result;
S>}
S>
S>public extension IntGroup of int: SGroup<int>
S>
S>можно использовать
S>
S>role IntGroup extednds int
S>
S> И в примере Мэдс все тоже самое. Ты переопределяешь только S>
S>public static int Zero => 0;
S>
Да, точно, операторы таки подхватываются.
S>И разница в том, что int[] нужно привести к IntGroup[]
Вот именно. extension в этом смысле лучше, чем роли, т.к. работает автоматика приведения.
S>В любом случае определить можно сделать один интерфейс для всех перегрузок операторов алгеброических типов и прописать для них роли S>и использовать эти роли хоть откуда как Func<> Action итд.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Qbit86, Вы писали: Q>В C++ можно вызвать «operator +», да. А ещё позвать оператор %, оператор запятую и вообще любую дичь а-ля Perl, которую только сможет натопать по клавиатуре кот — компилятор-то шаблоны не проверяет. Нет constraint'ов как в C# и других языках здорового человека.
Об этом и речь. Собственно, с моей точки зрения нужно продолжать фокусироваться над проблемой "выразить наличие статических мемберов типа в ограничениях дженериков", и сопутствующей ей проблемой "как теперь сделать так, чтобы встроенные типы удовлетворяли этим ограничениям без переделки CLR".
extensions выглядят вполне вменяемым решением этой проблемы — я могу скомбинировать свой обобщённый алгоритм с набором екстеншнов для всех встроенных типов, и пользователи смогут им пользоваться без единой лишней строчки кода.
Роли выглядят решением какой-то другой проблемы. Вот ваш Reduce со struct моноидом уже вполне себе прекрасен. Введение ролей его никак не улучшит ни со стороны пользователя, ни со стороны автора — ну сможете вы заменить Combine на += — код от этого не станет более читаемым.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Qbit86, Вы писали:
Q>А ты пытаешься навязать мне какую-то другую задачу. Хочешь итерироваться по массиву? Окей, тогда сначала материализуй исходный IEnumerable<T> в массив, и ходи по нему. Например, рёбра остовного дерева не в массиве приходят, а генерируются в процессе обхода графа.
Q>Но даже если массивы. В обобщённом коде отстать от мономорфного всего на одну инструкцию промежуточного копирования — отличный результат, уже на порядок (десятичный) лучше протаскивания делегата в аналогичный Linq-метод.
Q>Окей, даже хоть и не сказывается, заменим на foreach, как в твоём варианте.
S>>В-третьих, удивительно, но факт: JIT всё же порождает разный код для generic случая и для специализации. Если починить проблему с !=, то generic версия начинает работать вот так: S>>
Q>| Method | Mean | Error | StdDev | Median | Ratio | RatioSD | Code Size |
Q>|----------------------- |-----------:|----------:|----------:|-----------:|------:|--------:|----------:|
Q>| ReduceIntegersBaseline | 4.879 us | 0.0074 us | 0.0385 us | 4.879 us | 1.00 | 0.00 | 131 B |
Q>| ReduceIntegers | 4.851 us | 0.0121 us | 0.0621 us | 4.876 us | 0.99 | 0.02 | 151 B |
Q>| AggregateIntegers | 74.457 us | 0.1019 us | 0.5166 us | 74.364 us | 15.26 | 0.15 | 419 B |
Q>
Ну что ж, поздравляю с отличным результатом!
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sharov, Вы писали:
S>Будте добры, а то не верится что будет быстрее. Уж больно T Reduce<T, TMonoid>(this IEnumerable<T> items, TMonoid monoid) абстрактный, со всеми косвенностями.
В управляемом мире ничего абстрактного нет. Удобнее, конечно, начинать не с TMonoid, а с Expression<Func<T, T, T>>, но в принципе ничего военного нет и при работе через интерфейс — вынимаем из него MSIL, и проверяем несколько типовых случаев. Если выполнены сразу все условия — items представляет собой T[]/Span<T>/ReadonlySpan<T>, и код Combine попадает в один из десятка паттернов — то мы переключаемся на SIMD. А если нет — то делаем fallback на обычный код, обработанный JIT-ом — как показал коллега QBit86, он совпадает по быстродействию с ручным кодом итерирования.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, varenikAA, Вы писали:
AA>Roles in C# 9. Нужно?
Признаться, я не очень понял, чем эти «роли» отличаются от того, что раньше питчилось под названием «шейпы», кроме синтаксиса. И не нахожу их особенно полезными. Тем не менее предприму ещё одну попытку раскрыть упомянутый ранее пример, где эти роли можно применить.
Предположительно, они были бы полезны в тех случаях, где обобщённые алгоритмы выражаются в терминах политик, а не стратегий. Что это всё такое и зачем это нужно?
Стратегии — это как стратегии в книжке «Gang of Four». Кондовый ООП джава-стайл. Например, IEqualityComparer<TKey> в конструкторе Dictionary<TKey, TValue> — это стратегия.
Политики — это примерно как политики в книжке Александреску про C++. Как стратегии, но времени компиляции. В случае словаря это была бы передача в конструктор и захват «TKeyComparer where TKeyComparer : IEqualityComparer<TKey>» вместо IEqualityComparer<TKey>.
Безотносительно ролей и шейпов, такой дизайн стандартной коллекции дал бы следующий профит.
Во-первых, перенос разрешения полиморфизма из времени выполнения во время компиляции позволяет оптимизировать вызовы, убрать лишнюю косвенность вплоть до инлайна, избежать боксинга.
Во-вторых, тип компаратора явно становится частью типа словаря вместо тобы, чтобы быть стёртым и спрятанным за ширмой интерфейса IEqualityComparer<TKey>. Это позволяет избежать класса ошибок вроде: мы мерджим два словаря на строках, но, оказывается, первый словарь использует внутри компаратор InvariantCulture, а второй IgnoreCase, а снаружи это никак не видно.
Если у нас такой стиль API, то внедрение шейпов/ролей теоретически могло бы немного снизить синтаксическую нагрузку. Но скорее даже не с пользователей API, а с автора. А автору это не так критично, кмк.
Здравствуйте, Qbit86, Вы писали:
Q>Здравствуйте, varenikAA, Вы писали:
AA>>Roles in C# 9. Нужно?
Q>Признаться, я не очень понял, чем эти «роли» отличаются от того, что раньше питчилось под названием «шейпы», кроме синтаксиса. И не нахожу их особенно полезными.
Все очень просто. В большей степени это нужно для алгеброических типов.
C++ шаблоны используют перегрузку методов напрополую. Правда там кодогенерация.
Для ролей же можно генерировать инлайн код из дженерика при Jit е
Не нужно генерировать для каждого типа реализацию интерфейса перегруженных операторов итд.
Из примеров наверное можно вспомнить System.Numerics. Там уже перегрузка операторов есть
Да и для большинства числовых дженериков подойдет.
Думаю в большинсте случаев это нужно для скорости, но и берешь кучу алгоритмов и используешь операторы, вместо интерфейсов, делегатов.
Удобно!
и солнце б утром не вставало, когда бы не было меня
_>>Ты пропустил замечание что для сложения и умножения чаще всего вообще не стоит лепить лапшу с делегатами. Q>Хорошо. Что тогда нужно лепить вместо моноида в этом алгоритме? Как его переписать без еретического моноида?
Алгоритма-то нету — сумматор на моноиде и всё. Если ничего сложнее в коде нет, то и не надо переписывать. Задуматься что "свернули не туда" надо если потребитель твоего кода вынужден описывать и передавать пяток моноидов для разных целей, или если они у тебя или у пользователя поштучно и группами кочуют из метода в метод.
Q>Хорошо а IEnumerable<T> — это тоже харам? Он же порождает; ты его тоже избегаешь? Потому что на энумераторах можно много чего наворотить.
IEnumerable уже часть языка, избегать не обязательно. Но с шаблоном "тут последовательность данных, значит IEnumerable" закопать проект вполне можно.
