Решение на Polynomial от Георги Божинов
Резултати
- 15 точки от тестове
- 0 бонус точки
- 15 точки общо
- 15 успешни тест(а)
- 0 неуспешни тест(а)
Код
Лог от изпълнението
Compiling solution v0.1.0 (file:///tmp/d20171121-6053-abjcac/solution)
Finished dev [unoptimized + debuginfo] target(s) in 6.14 secs
Running target/debug/deps/solution-200db9172ea1f728
running 0 tests
test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Running target/debug/deps/solution_test-e3c9eb714e09105e
running 15 tests
test solution_test::test_add_poly ... ok
test solution_test::test_add_poly_zero_one ... ok
test solution_test::test_arithmetic_properties ... ok
test solution_test::test_create_poly ... ok
test solution_test::test_div_poly_f64 ... ok
test solution_test::test_div_poly_f64_zero ... ok
test solution_test::test_fp_comparison ... ok
test solution_test::test_has_point ... ok
test solution_test::test_lagrange_poly_1 ... ok
test solution_test::test_lagrange_poly_2 ... ok
test solution_test::test_lagrange_poly_err_eq_x ... ok
test solution_test::test_mul_poly ... ok
test solution_test::test_mul_poly_f64 ... ok
test solution_test::test_mul_poly_f64_zero ... ok
test solution_test::test_mul_poly_zero_one ... ok
test result: ok. 15 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Doc-tests solution
running 0 tests
test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
История (2 версии и 3 коментара)
Георги качи решение на 20.11.2017 13:41 (преди почти 8 години)
use std::ops::{Mul, Div, Add};
const EPS: f64 = 1e-10;
const ZERO: f64 = 0_f64;
#[derive(Debug, Clone)]
pub struct Polynomial {
coeffs: Vec<f64>,
}
fn clear_trailing_zeros(vector: Vec<f64>) -> Vec<f64> {
let new_vec: Vec<_> = vector.into_iter().skip_while(|&c| c == ZERO).collect();
new_vec
}
fn prepend_zeros_until(desired_length: usize, vector: Vec<f64>) -> Vec<f64> {
let mut new_vec = vec![];
- for _ in 0..desired_length - 1 {
+ for _ in 0..desired_length - vector.clone().len() {
new_vec.push(ZERO);
}
for elem in vector {
new_vec.push(elem)
}
+
new_vec
}
fn find_and_prepend_zeros_to_longer(
left_coeffs: &Vec<f64>,
right_coeffs: &Vec<f64>,
) -> (Vec<f64>, Vec<f64>) {
Подозирам, че реагира на дължината на функцията :). За функции с доста аргументи, дълги имена, или множество where клаузи, вероятно ще изглежда доста по-четимо така.
let left = left_coeffs.len();
let right = right_coeffs.len();
- let mut shorter = vec![];
- let mut longer = vec![];
+ let shorter;
+ let longer;
if left > right {
shorter = prepend_zeros_until(left, right_coeffs.clone());
longer = left_coeffs.clone();
} else if right > left {
longer = prepend_zeros_until(right, left_coeffs.clone());
shorter = right_coeffs.clone();
+ } else {
+ longer = right_coeffs.clone();
+ shorter = left_coeffs.clone();
}
(longer, shorter)
}
fn count_occurrences(element: f64, vector: &Vec<(f64, f64)>) -> usize {
vector.iter().filter(|f| f.0 == element).count()
}
fn calculate_elementary_lagrange_polynomial(j: usize, points: &Vec<(f64, f64)>) -> Polynomial {
- let mut polynomial = Polynomial::default();
+ let mut polynomial = Polynomial::from(vec![1.0]);
for m in 0..points.len() {
- polynomial = polynomial.clone() +
- Polynomial::from(vec![1.0, points[m].0]) / (points[j].0 - points[m].0);
+ if m != j {
+ polynomial = polynomial.clone() * Polynomial::from(vec![1.0, -(points[m].0)]) /
+ (points[j].0 - points[m].0);
+ }
}
polynomial
}
impl Polynomial {
pub fn has(&self, point: &(f64, f64)) -> bool {
let mut sum = ZERO;
let len = self.coeffs.len();
for (index, item) in self.coeffs.clone().into_iter().enumerate() {
sum = sum + (item as f64) * (point.0).powi((len - index - 1) as i32);
}
(sum - point.1).abs() < EPS
}
pub fn interpolate(points: Vec<(f64, f64)>) -> Option<Self> {
let mut lagrange = Polynomial::default();
if points
.clone()
.iter()
.map(|p| count_occurrences(p.0, &points))
.any(|p| p > 1)
{
return None;
}
for j in 0..points.len() {
let elementary = calculate_elementary_lagrange_polynomial(j, &points);
lagrange = lagrange + (elementary * points[j].1);
}
Some(lagrange)
}
}
impl From<Vec<f64>> for Polynomial {
fn from(coeffs: Vec<f64>) -> Self {
Polynomial { coeffs: clear_trailing_zeros(coeffs) }
}
}
impl Default for Polynomial {
fn default() -> Self {
Polynomial { coeffs: vec![] }
}
}
impl PartialEq for Polynomial {
fn eq(&self, rhs: &Self) -> bool {
+ if self.coeffs.clone().len() != rhs.coeffs.clone().len() {
+ return false;
+ }
+
for elem in self.coeffs.clone().into_iter().zip(
rhs.coeffs
.clone()
.into_iter(),
)
{
let (ai, bi) = elem;
if (ai - bi).abs() > EPS {
return false;
}
}
true
}
}
impl Mul<f64> for Polynomial {
type Output = Polynomial;
fn mul(self, rhs: f64) -> Self::Output {
let mut new_coeffs = vec![];
for elem in self.coeffs {
new_coeffs.push(elem * rhs);
}
Polynomial::from(new_coeffs)
}
}
impl Div<f64> for Polynomial {
type Output = Polynomial;
fn div(self, rhs: f64) -> Self::Output {
let mut new_coeffs = vec![];
for elem in self.coeffs {
new_coeffs.push(elem / rhs);
}
Polynomial::from(new_coeffs)
}
}
impl Mul for Polynomial {
type Output = Polynomial;
fn mul(self, rhs: Polynomial) -> Self::Output {
let (longer, shorter) = find_and_prepend_zeros_to_longer(&self.coeffs, &rhs.coeffs);
let length = longer.clone().len();
let mut pairs_of_coeffs = vec![];
let mut right_pairs_of_coeffs = vec![];
for (index, elem) in longer.clone().into_iter().enumerate() {
right_pairs_of_coeffs.push((length - index - 1, elem));
}
for (index, elem) in shorter.clone().into_iter().enumerate() {
pairs_of_coeffs.push((length - index - 1, elem));
}
let mut multiplied_pairs = vec![];
for elem in pairs_of_coeffs.clone() {
for n in right_pairs_of_coeffs.clone() {
multiplied_pairs.push((elem.0 + n.0, elem.1 * n.1));
}
}
Хмм, не ми харесват тия клонирания. Трудно ми е да преценя доколко са нужни. Добра идея ще е да поекспериментираш, и да видиш дали можеш да ги махнеш и как. Примерно, вместо да ползваш .clone().into_iter(), може да опиташ .iter() -- дори да ти връща references, може тях да копираш, понеже са просто единични числа. Иначе първо копираш всичките, и после ги копираш още веднъж като ги подаваш на push.
let mut new_coeffs = vec![];
for i in 0..multiplied_pairs.len() {
new_coeffs.push(
multiplied_pairs
.clone()
.into_iter()
.filter(|&pair| pair.0 == i)
.fold(ZERO, |acc, p| acc + p.1),
);
}
+
+ new_coeffs.reverse();
Polynomial::from(clear_trailing_zeros(new_coeffs))
}
}
impl Add for Polynomial {
type Output = Polynomial;
fn add(self, rhs: Polynomial) -> Self::Output {
let (longer, shorter) = find_and_prepend_zeros_to_longer(&self.coeffs, &rhs.coeffs);
let mut new_coeffs = vec![];
for elem in shorter.clone().iter().zip(longer.into_iter()) {
let (ai, bi) = elem;
new_coeffs.push(ai + bi);
}
Polynomial::from(clear_trailing_zeros(new_coeffs))
}
}
rust-fmt е странно нещо
Подозирам, че реагира на дължината на функцията :). За функции с доста аргументи, дълги имена, или множество where клаузи, вероятно ще изглежда доста по-четимо така.
Хмм, не ми харесват тия клонирания. Трудно ми е да преценя доколко са нужни. Добра идея ще е да поекспериментираш, и да видиш дали можеш да ги махнеш и как. Примерно, вместо да ползваш
.clone().into_iter(), може да опиташ.iter()-- дори да ти връща references, може тях да копираш, понеже са просто единични числа. Иначе първо копираш всичките, и после ги копираш още веднъж като ги подаваш наpush.