Минимизация (z-xi) ^ 2
Если я хочу найти median (это эквивалентно минимизации функции | z — xя|), Я могу использовать следующее code snippet:
std::vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};
std::nth_element(v.begin(), v.begin() + v.size()/2, v.end());
std::cout << "The median is " << v[v.size()/2] << '\n';
Есть ли что-то подобное, чтобы найти "median" для минимизации (з-хя) ^ 2? То есть я хочу найти элемент массива, в котором сумма этих функций будет минимальной.
Решение
Дан массив х1, Икс2, …, ИксN целых чисел, действительное число z, которое минимизирует ∑i∈ {1,2, …, п} (г — хя)2 это имею в виду z * = (1 / n) ∑i∈ {1,2, …, п} Икся. Вы хотите позвонить std::min_element с компаратором, который обрабатывает хя меньше чем хJ тогда и только тогда, когда | n xя — n z * | < | н хJ — n z * | (мы используем n z * = ∑i∈ {1,2, …, п} Икся избегать арифметики с плавающей точкой; Есть способы уменьшить дополнительную точность требуется).
Другие решения
Если вы хотите найти nth_element() в соответствии с предикатом сравнения (z - xi) ^ 2 Вы можете просто добавить соответствующую логику в двоичный предикат, который вы можете при желании передать nth_element():
auto trans = [=](int xi){ return (z - xi) * (z - xi); };
std::nth_element(v.begin(), v.begin() + v.size() / 2, v.end(),
[&](int v0, int v1) { return trans(v0) < trans(v1); });
Из вопроса не ясно, z или же xi это переменная переменная. Судя по всему, я предположил xi должен быть xя. Если z меняется, просто переименуйте аргумент в лямбду trans (который я только что дал = в плен …).
Ваш вопрос работает как минимум на двух разных уровнях: вы спрашиваете, как воплощать в жизнь определенный алгоритм идиоматически в C ++ 11, и в то же время вы просите эффективный алгоритм для вычисления среднего списка целых чисел.
Вы правильно заметили, что для вычисления медиана, все, что нам нужно сделать, это запустить Алгоритм быстрого выбора с k установить равным n/2, В стандартной библиотеке C ++ QuickSelect написано std::nth_element:
int v[] = { 5, 6, 4, 3, 2, 6, 7, 9, 3 };
const int k = std::size(v) / 2;
std::nth_element(std::begin(v), &v[k], std::end(v)); // mutate in-place
int median = v[v.size()/2]; // now the k'th element is
(За std::sizeсм предложение N4280, скоро на C ++ 17 рядом с вами! До этого используйте свой любимый макрос NELEM или вернитесь к использованию кучи vector.)
Эта реализация QuickSelect на самом деле не имеет ничего общего с поиском элемента массива ИксК такой, что ∑я |Икся — ИксК| сводится к минимуму. «Я имею в виду, это математически эквивалентно, да, но нет ничего в код это соответствует суммированию или вычитанию целых чисел.
Наивный алгоритм «найти элемент массива» ИксК такой, что ∑я |Икся — ИксК| сворачивается просто
int v[] = { 5, 6, 4, 3, 2, 6, 7, 9, 3 };
auto sum_of_differences = [v](int xk) {
int result = 0;
for (auto&& xi : v) {
result += std::abs(xi - xk);
}
return result;
};
int median =
std::min_element(std::begin(v), std::end(v), [](int xa, int xb) {
return sum_of_differences(xa) < sum_of_differences(xb);
});
Это ужасно неэффективный алгоритм, учитывая, что QuickSelect выполняет ту же работу.
Тем не мение, тривиально расширить этот код для работы с любой математической функцией, для которой вы хотите «минимизировать сумму». Вот тот же скелет кода, но с функцией «разница в квадрате» вместо «разница»:
int v[] = { 5, 6, 4, 3, 2, 6, 7, 9, 3 };
auto sum_of_squared_differences = [v](int xk) {
int result = 0;
for (auto&& xi : v) {
result += (xi - xk) * (xi - xk);
}
return result;
};
int closest_element_to_the_mean =
std::min_element(std::begin(v), std::end(v), [](int xa, int xb) {
return sum_of_squared_differences(xa) < sum_of_squared_differences(xb);
});
В этом случае мы можем также найти улучшенный алгоритм; а именно, вычислите среднее значение заранее и только потом просканируйте массив, ища элемент, который ближе всего к этому значению:
int v[] = { 5, 6, 4, 3, 2, 6, 7, 9, 3 };
double actual_mean = std::accumulate(std::begin(v), std::end(v), 0.0) / std::size(v);
auto distance_to_actual_mean = [=](int xk) {
return std::abs(xk - actual_mean);
};
int closest_element_to_the_mean =
std::min_element(std::begin(v), std::end(v), [](int xa, int xb) {
return distance_to_actual_mean(xa) < distance_to_actual_mean(xb);
});
(П.С. — помните, что никто из приведенного выше фрагментов кода следует использовать на практике, если только вы не абсолютно уверены, что вам не нужно заботиться о целочисленном переполнении, ошибке округления с плавающей точкой и множестве других математических проблем.)