Използване на Option като итератор

Програмиране с Rust

Курс във Факултета по Математика и Информатика към СУ

Решение на Polynomial от Николай Коцев

Обратно към всички решения

Към профила на Николай Коцев

Резултати

  • 13 точки от тестове
  • 0 бонус точки
  • 13 точки общо
  • 13 успешни тест(а)
  • 2 неуспешни тест(а)

Код

use std::ops::Mul;
use std::ops::Div;
use std::ops::Add;
#[derive(Debug, Clone)]
pub struct Polynomial {
coefficients: Vec<f64>
}
const EPS: f64 = 1.0e-10;
impl Polynomial {
pub fn eval(&self, x: f64) -> f64 {
let mut result: f64 = 0.0;
let mut power = self.coefficients.len();
for coef in self.coefficients.iter() {
power -= 1;
result += coef*x.powi(power as i32);
}

Това може да се напише без мутация така:

for (power, coef) in self.coefficients.iter().rev().enumerate() {
    result += coef*x.powi(power as i32);
}

Обръщането на коефициентите тук е безплатно, понеже вектора дава double-ended итератор, спокойно може да цикли отзад-напред. Метода enumerate пък връща елементите с индекс, който може да се използва като степен.

Андрей
result
}
pub fn has(&self, point: &(f64, f64)) -> bool {
Polynomial::equal_floats(self.eval(point.0), point.1)
}
fn equal_floats(lhs: f64, rhs: f64) -> bool {
if lhs.is_nan() || rhs.is_nan() || lhs.is_infinite() ||
rhs.is_infinite() {
return false;
}
(lhs - rhs).abs() < EPS
}
pub fn interpolate(_points: Vec<(f64, f64)>) -> Option<Self> {
None
}
}
impl Default for Polynomial {
fn default() -> Self {
Self {
coefficients: vec![0.0_f64]
}
}
}
impl From<Vec<f64>> for Polynomial {
fn from(coefs: Vec<f64>) -> Self {
let result = coefs.into_iter()
.skip_while(|elem| Polynomial::equal_floats(*elem, 0.0))
.collect::<Vec<f64>>();
if result.is_empty() {
Self::default()
}
else {
Self { coefficients: result }
}
}
}
impl Mul<f64> for Polynomial {
type Output = Self;
fn mul(self, rhs: f64) -> Self {
Self::from(self.coefficients.iter().map(|elem| elem * rhs)
.skip_while(|elem| *elem == 0.0).collect::<Vec<f64>>())
}
}
impl Div<f64> for Polynomial {
type Output = Self;
fn div(self, rhs: f64) -> Self {
Self::from(self.coefficients.iter().map(|elem| elem / rhs)
.collect::<Vec<f64>>())
}
}
impl PartialEq for Polynomial {
fn eq(&self, rhs: &Self) -> bool {
if self.coefficients.len() != rhs.coefficients.len() { return false };
self.coefficients.iter().zip(rhs.coefficients.iter())
.all(|(l, r)| Polynomial::equal_floats(*l, *r))
}
}
impl Add for Polynomial {
type Output = Self;
fn add(self, rhs: Self) -> Self {
if self.coefficients.len() >= rhs.coefficients.len() {
let length_diff = self.coefficients.len() - rhs.coefficients.len();
let mut new_coefs: Vec<f64> = vec![];
new_coefs.extend_from_slice(&self.coefficients[0..length_diff]);
for (i, elem) in rhs.coefficients.iter().enumerate(){
new_coefs.push(self.coefficients[i + length_diff] + elem);
}
Self::from(new_coefs)
}
else {
rhs + self
}
}
}
impl Mul for Polynomial {
type Output = Self;
fn mul(self, rhs: Self) -> Self {
let len_sum = self.coefficients.len() + rhs.coefficients.len();
let mut product = vec![0.0; len_sum -1];
for i in 0..self.coefficients.len() {
for j in 0..rhs.coefficients.len() {
product[i + j] = product[i + j] + self.coefficients[i] *
rhs.coefficients[j]
}
}
Self::from(product)
}
}

Лог от изпълнението

Compiling solution v0.1.0 (file:///tmp/d20171121-6053-dcpikw/solution)
    Finished dev [unoptimized + debuginfo] target(s) in 5.32 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 ... FAILED
test solution_test::test_lagrange_poly_2 ... FAILED
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

failures:

---- solution_test::test_lagrange_poly_1 stdout ----
	thread 'solution_test::test_lagrange_poly_1' panicked at 'called `Option::unwrap()` on a `None` value', src/libcore/option.rs:335:20
note: Run with `RUST_BACKTRACE=1` for a backtrace.

---- solution_test::test_lagrange_poly_2 stdout ----
	thread 'solution_test::test_lagrange_poly_2' panicked at 'assertion failed: poly.is_some()', tests/solution_test.rs:232:4


failures:
    solution_test::test_lagrange_poly_1
    solution_test::test_lagrange_poly_2

test result: FAILED. 13 passed; 2 failed; 0 ignored; 0 measured; 0 filtered out

error: test failed, to rerun pass '--test solution_test'

История (2 версии и 2 коментара)

Николай качи първо решение на 13.11.2017 23:42 (преди почти 8 години)

Добра работа до момента, дори и без interpolate, но имай предвид, че без този метод, системата не може да компилира кода, така че за момента имаш 0 точки. Ако само създадеш празна имплементация, така че базовия тест да се компилира, вероятно ще получиш доста точки дори и така.

Разбира се, можеш просто да седнеш и да го напишеш тоя метод, и да целиш пълните 15 ;).

Николай качи решение на 20.11.2017 09:04 (преди почти 8 години)

-// Няма interpolate, но се надявам, че утре ще стигна и до там...
-
use std::ops::Mul;
use std::ops::Div;
use std::ops::Add;
#[derive(Debug, Clone)]
pub struct Polynomial {
coefficients: Vec<f64>
}
+const EPS: f64 = 1.0e-10;
+
impl Polynomial {
pub fn eval(&self, x: f64) -> f64 {
let mut result: f64 = 0.0;
let mut power = self.coefficients.len();
for coef in self.coefficients.iter() {
power -= 1;
result += coef*x.powi(power as i32);
}

Това може да се напише без мутация така:

for (power, coef) in self.coefficients.iter().rev().enumerate() {
    result += coef*x.powi(power as i32);
}

Обръщането на коефициентите тук е безплатно, понеже вектора дава double-ended итератор, спокойно може да цикли отзад-напред. Метода enumerate пък връща елементите с индекс, който може да се използва като степен.

Андрей
result
}
pub fn has(&self, point: &(f64, f64)) -> bool {
- (self.eval(point.0) - point.1).abs() < 1.0e-10
+ Polynomial::equal_floats(self.eval(point.0), point.1)
}
- // fn equal_floats(left: f64, right: f64) -> bool {
- // (left - right).abs() < 1.0e-10
- // }
- //
- // fn all_unique(xs: &Vec<f64>) -> bool {
- // xs.iter().enumerate().all(|(i, e)| {
- // xs[(i + 1)..].iter().all(|j| !Polynomial::equal_floats(*e, *j))
- // })
- // }
- //
- // fn check_points(points: Vec<(f64, f64)>) -> bool {
- // let xs = points.iter().map(|pair| pair.0).collect();
- // points.len() >= 2 && Polynomial::all_unique(xs)
- // }
+ fn equal_floats(lhs: f64, rhs: f64) -> bool {
+ if lhs.is_nan() || rhs.is_nan() || lhs.is_infinite() ||
+ rhs.is_infinite() {
- // pub fn interpolate(points: Vec<(f64, f64)>) -> Option<Self> {
- // if !Polynomial::check_points(points) { panic!() };
- // let pz: f64 = 0.0;
- // }
+ return false;
+ }
+ (lhs - rhs).abs() < EPS
+ }
+
+ pub fn interpolate(_points: Vec<(f64, f64)>) -> Option<Self> {
+ None
+ }
}
impl Default for Polynomial {
fn default() -> Self {
Self {
coefficients: vec![0.0_f64]
}
}
}
impl From<Vec<f64>> for Polynomial {
fn from(coefs: Vec<f64>) -> Self {
- if coefs.is_empty() {
- Self { coefficients: coefs }
+ let result = coefs.into_iter()
+ .skip_while(|elem| Polynomial::equal_floats(*elem, 0.0))
+ .collect::<Vec<f64>>();
+
+ if result.is_empty() {
+ Self::default()
}
- else if coefs.iter().all(|elem| *elem == 0.0) {
- Self { coefficients: vec![0_f64] }
- }
else {
- Self { coefficients: coefs.into_iter().skip_while(|elem| *elem == 0.0).collect() }
+ Self { coefficients: result }
}
}
}
impl Mul<f64> for Polynomial {
type Output = Self;
fn mul(self, rhs: f64) -> Self {
- let new_coefs: Vec<f64>= self.coefficients.iter()
- .map(|elem| elem * rhs).skip_while(|elem| *elem == 0.0).collect();
- if new_coefs.is_empty(){
- Self::from(vec![0.0])
- }
- else {
- Self::from(new_coefs)
- }
+ Self::from(self.coefficients.iter().map(|elem| elem * rhs)
+ .skip_while(|elem| *elem == 0.0).collect::<Vec<f64>>())
}
}
impl Div<f64> for Polynomial {
type Output = Self;
fn div(self, rhs: f64) -> Self {
- let new_coefs: Vec<f64> = self.coefficients.iter()
- .map(|elem| elem / rhs).collect();
-
- Self::from(new_coefs)
+ Self::from(self.coefficients.iter().map(|elem| elem / rhs)
+ .collect::<Vec<f64>>())
}
}
impl PartialEq for Polynomial {
fn eq(&self, rhs: &Self) -> bool {
- self.coefficients.iter().enumerate()
- .all(|(i, e)| (e - rhs.coefficients[i]).abs() < 1.0e-10)
+ if self.coefficients.len() != rhs.coefficients.len() { return false };
+ self.coefficients.iter().zip(rhs.coefficients.iter())
+ .all(|(l, r)| Polynomial::equal_floats(*l, *r))
}
}
impl Add for Polynomial {
type Output = Self;
fn add(self, rhs: Self) -> Self {
if self.coefficients.len() >= rhs.coefficients.len() {
let length_diff = self.coefficients.len() - rhs.coefficients.len();
let mut new_coefs: Vec<f64> = vec![];
new_coefs.extend_from_slice(&self.coefficients[0..length_diff]);
for (i, elem) in rhs.coefficients.iter().enumerate(){
new_coefs.push(self.coefficients[i + length_diff] + elem);
}
Self::from(new_coefs)
}
else {
rhs + self
}
}
}
impl Mul for Polynomial {
type Output = Self;
fn mul(self, rhs: Self) -> Self {
let len_sum = self.coefficients.len() + rhs.coefficients.len();
- let mut product = Vec::new();
- for _ in 0..(len_sum - 1) {
- product.push(0.0_f64);
- }
+ let mut product = vec![0.0; len_sum -1];
for i in 0..self.coefficients.len() {
for j in 0..rhs.coefficients.len() {
product[i + j] = product[i + j] + self.coefficients[i] *
rhs.coefficients[j]
}
}
Self::from(product)
}
}