Re[4]: offtop: сортировщики гномиков
От: Sinclair Россия https://github.com/evilguest/
Дата: 20.07.22 08:49
Оценка:
Здравствуйте, syrompe, Вы писали:
S>С интами будет переполнение в аккумуляторе. Можно аккумулятор long сделать это в принципе решит проблему, но не ложится на эти абстракции.
Не будет. Вы не можете параметризовать приведённый метод StandardDeviation интами, т.к. ни int ни long не реализуют IFloatingPointIeee754<T>.
А для Average всё прекрасно ложится — делаете Average<int, long>(t).

S>С float при суммировании будут складываться числа разных размерностей со всеми вытекающими.

Да, это то, на что я намекал в

Меня в приведённых примерах беспокоит разве что потеря точности.


S>

S>S(0)=0
S>S(n+1)=(a_n+1-S(n))/(n+1)+S(n)

S>По этой методе недостатков округления сильно меньше (они есть, но результат устойчив). Вот забыл совсем как формула называется, если кто помнит подскажите плз.
Тут есть некоторая сложность. Если по этой методе усреднять целые числа, то получится пежня из-за округления промежуточных результатов.
Попробуйте посчитать Average<int, long>(new[] {1, 2, 3, 4, 5}).
Заставлять всегда считать среднее только в плавающей запятой — так себе идея.
Можно сделать две версии — IntAverage и FloatAverage, т.к. в дотнете нельзя сделать перегрузки методов, которые бы отличались только констреинтами на дженериках.
А можно просто взять для суммирования Алгоритм Кэхэна. Для плавающей запятой он минимизирует погрешности; для целых чисел его, скорее всего, JIT сведёт к тому же бинарному коду, что и простое суммирование.

Но для достижения счастья нам, конечно же, понадобится что-то вроде этого: http://blog.zachbjornson.com/2019/08/11/fast-float-summation.html
То есть вычисление суммы всё же придётся делать не-дженерик, а специфично для конкретного типа. В реальной боевой библиотеке код Sum<T, TResult> скорее всего будет выглядеть как набор if(typeof(T) == typeof(int64))..., т.к. в дотнете это единственный способ сделать специализацию дженерика без потери производительности.
Зато вот код Average и StandardDeviation опишется обобщённым способом.

Правда, потом нас не устроит вычисление суммы квадратов отдельным проходом. Мы выкинем нафиг функцию Average, и запилим алгоритмы в зависимости от используемых типов. То есть — берём за основу что-то отсюда: https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance, и ускоряем при помощи SIMD.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.