Узагальнені чисельні алгоритми STL. Частина 14

наступну, дуже потрібну і дуже потужну групу STL алгоритмів представляють узагальнені чисельні алгоритми (заголовки <числовий>). Це не якісь особливі обчислювальні методи, як можна подумати виходячи з назви. це алгоритми, що дозволяють застосовувати загальновідомі бібліотечні або свої власні обчислювальні функції до всієї сукупності елементів контейнера.

А оскільки так, то і викликаються вони подібно до всіх інших алгоритмам STL. Використовуються такі узагальнені алгоритми, головним чином в математичних обчисленнях стосовно контейнерів, що містить числові елементи. Але це зовсім не обов'язково. І якщо вас не цікавлять чисельні обчислення (наприклад з області цифрової обробки сигналів), то ви можете просто безболісно пропустити цю частину викладу…

Перерахуємо представлені STL узагальнені чисельні алгоритми: йота (створення монотонно зростаючій послідовності), накопичуватися (накопичення), inner_product (skalyarnoe proïzvedenïe), partial_sum (часткова сума), adjacent_difference (суміжна різницю).

Ілюстрацію роботи найкраще провести на самому використовуваному і інтуїтивно зрозумілій алгоритмі накопичуватися. Цей алгоритм редукує (зменшує розмірність) контейнера з накопиченням значень. Зокрема, для простих числових значень він згортає vector<> или list<> до одиночного скалярного результуючого значення.

алгоритм накопичуватися (як, втім, і більшість інших) має 2 синтаксичні форми:

template <class InputIterator, class T>
T accumulate( InputIterator first, InputIterator last, T init );

template <class InputIterator, class T, class BinaryOperation>
T accumulate( InputIterator first, InputIterator last, T init, BinaryOperation binary_op );

template <class InputIterator, class T>

T accumulate( InputIterator first, InputIterator last, T init );

template <class InputIterator, class T, class BinaryOperation>

T accumulate( InputIterator first, InputIterator last, T init, BinaryOperation binary_op );

У 1-й формі (вона менш цікава) алгоритм підсумовує значення елементів контейнера. Не забуваємо при цьому, що для типу string, например, операция ‘+‘ означає конкатенацію, склеювання). У 2-й формі алгоритм накопичує результат бінарної операції (функції 2-х змінних), застосовуваної до накопичувати значенням (акумулятора) і по черзі до кожного елементу контейнера.

Не зрозуміло? Це потужна техніка, і зараз все стане зрозуміло з прикладу…

У математичній статистиці знаходять застосування кілька видів середнього значення для числової послідовності:

Среднее арифметическое:
середнє геометричне:
середнє гармонійне:

середнє квадратичне:

Чи не станемо заглиблюватися в зміст кожного з варіантів. Ми зробимо додаток, яке підраховує ці середні і ще деякі характеристики (дисперсію, середньоквадратичне відхилення) для введеної числової послідовності. Вхідну послідовність вводимо або з терміналу, або перенаправленням з попередньо підготовленого файлу даних:

#include <iostream> 
#include <vector> 
#include <sstream> 
#include <numeric> 
#include <cmath> 
using namespace std;

double amean;  // среднее арифметическое (значение)

double disp(double acc, double seq) { // накопление квадратов отклонений
	seq -= amean;
	return acc + seq * seq;
}

double mul(double acc, double seq) {  // произведение элементов
	return acc * seq;
}

double garm(double acc, double seq) { // сумма обратных значений
	return acc + 1. / seq;
}

double sqr(double acc, double seq) {  // сумма квадратов элементов
	return acc + seq * seq;
}

int main(void) {
	setlocale(LC_ALL, "rus");

	string s;
	getline(cin, s);        // читаем входную строку

	istringstream ist(s);   // поток для чтения мз строки
	double d;
	vector<double> ser;     // числовой массив

	while (ist >> d)
		ser.push_back(d);  // поэлементное чтение чисел в массив

	int n = ser.size();
	auto b = ser.begin(), e = ser.end();
	amean = accumulate(b, e, 0.) / n; // сумма элементов
	double variance = accumulate(b, e, 0., disp) / n,
	       deviation = sqrt(variance),
               gmean = exp(log(accumulate(b, e, 1., mul)) / n),
	       rmean = n / accumulate(b, e, 0., garm),
	       smean = sqrt(accumulate(b, e, 0., sqr) / n);

	cout << "ср.ариф.=" << amean << " ср.геом.=" << gmean
		<< " ср.гарм.=" << rmean << " ср.квад.=" << smean << endl
		<< "дисперсия=" << variance << " СКО=" << deviation << endl;
}

#include <iostream>

#include <vector>

#include <sstream>

#include <numeric>

#include <cmath>

using namespace std;

double amean; // среднее арифметическое (значение)

double disp(double acc, double seq) { // накопление квадратов отклонений

seq -= amean;

return acc + seq * seq;

}

double mul(double acc, double seq) { // произведение элементов

return acc * seq;

}

double garm(double acc, double seq) { // сумма обратных значений

return acc + 1. / seq;

}

double sqr(double acc, double seq) { // сумма квадратов элементов

return acc + seq * seq;

}

int main(void) {

setlocale(LC_ALL, "rus");

string s;

getline(cin, s); // читаем входную строку

istringstream ist(s); // поток для чтения мз строки

double d;

vector<double> ser; // числовой массив

while (ist >> d)

ser.push_back(d); // поэлементное чтение чисел в массив

int n = ser.size();

auto b = ser.begin(), e = ser.end();

amean = accumulate(b, e, 0.) / n; // сумма элементов

double variance = accumulate(b, e, 0., disp) / n,

deviation = sqrt(variance),

gmean = exp(log(accumulate(b, e, 1., mul)) / n),

rmean = n / accumulate(b, e, 0., garm),

smean = sqrt(accumulate(b, e, 0., sqr) / n);

cout << "ср.ариф.=" << amean << " ср.геом.=" << gmean

<< " ср.гарм.=" << rmean << " ср.квад.=" << smean << endl

<< "дисперсия=" << variance << " СКО=" << deviation << endl;

}

Як легко бачити, кожна із записаних вище складних математичних формул обчислюється всього лише в один рядок, використовуючи техніку узагальнених алгоритмів:

Узагальнені чисельні алгоритми stl в c ++

Тут ми можемо спостерігати відоме співвідношення, яке підтверджує коректність наших обчислень. Полягає воно в тому, що для будь-якої послідовності чисел середнє арифметичне більше або дорівнює середнього геометричного, яке, в свою чергу, більше або дорівнює середнього гармонійного. Причому рівність в цих твердженнях досягається тільки якщо всі члени числової послідовності рівні між собою:

Узагальнені чисельні алгоритми stl в c ++

Повернемося до вивчення коду. Перший виклик алгоритму накопичуватися( b, е, 0. ) демонструє 1-ю форму використання: значення контейнера підсумовуються з початковим значенням 0.0.

попередження!: Запис точки в константі початкового значення, яка вказує, що це дійсне значення - принципово важливо. Без цього код компілюватиметься навіть без попереджень, але виконуватися з абсолютно невірними і вкрай складно тлумаченими результатами! Это связано с тем, що алгоритми визначені як template, і тип 3-го параметра визначить для якого типу даних будуть задіяні внутрішні операції при накопиченні.

Всі решта (4 штуки) виклики накопичуватися() використовують 2-ю форму виклику – передають 4-м параметром функцію накопичення. Як видно з прикладів, вона приймає параметрами поточний накопичене значення і черговий елемент контейнера. А повертає результат накопичує операції. Для наочності, все накопичують функції записані в прикладі в простому і ясному вигляді. На практиці, щоб уникнути залежності від типу оброблюваних даних, їх також зазвичай записують, як шаблонні функції. Тоді це може виглядати так:

template <typename T> T mul( T& acc, const T& seq ) { 
   return acc * seq; 
} 

int main( void ) { 
   vector<long> ser = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 
   cout << accumulate( ser.begin(), ser.end(), 1L, mul<long> ) << endl; 
} 
$ ./numb3 
362880

template <typename T> T mul( T& acc, const T& seq ) {

return acc * seq;

}

int main( void ) {

vector<long> ser = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

cout << accumulate( ser.begin(), ser.end(), 1L, mul<long> ) << endl;

}

$ ./numb3

362880

нарешті, Зверніть увагу, якщо не звернули досі, що при накопиченні сум ми використовуємо початкове значення 0 (3-й параметр накопичуватися() ), а при накопиченні творів, естественно, 1, з відповідним типом даних.

2 думки про "Узагальнені чисельні алгоритми. STL (частина 14)”

Saneksig говорить:
15.01.2017 at 15:06
Всім привіт!
Сьогодні заглянув на онлайн сайти, де раніше дивився, здивовано знайшов що вони не працюють, тобто їх фільми не транслюють взагалі, типо у вашій країні відео запрещенно!
Тепер фільми не глянути онлайн по всюди фільми видалені, що знову назад на торренти?
відповісти
1. Olej говорить:
  15.01.2017 at 23:33
  Чи не … просто “типо”: руки ростуть з дупи :-(
  відповісти

Узагальнені чисельні алгоритми. STL (частина 14)

2 думки про "Узагальнені чисельні алгоритми. STL (частина 14)”

залишити коментар Скасувати відповідь

Останні повідомлення

недавні коментарі

Статистика