Extension traits

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

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

упр.10 задача 1

Краен срок:
17.12.2025 23:59
Точки:
2

Имаш голям вектор от числа. Искаш да филтрираш само тези, които отговарят на определено условие, но паралелно. Вектор Vec и някакъв предикат :

  • всички числа > 100
  • всички четни числа
  • всички числа, които са прости
  • всички числа, делящи се на 7
enum Predicate {
    GreaterThan100,
    Even,
    Prime,
    DivisibleBy7,
}

Трябва да направиш: Раздели вектора на N части. Създай по една нишка за всяка част.

fn parallel_filter(data: Vec<i32>, n_threads: usize, predicate: Predicate) -> Vec<i32> {
   //your code
}

Всяка нишка:

  • взима своя сегмент
  • проверява всяко число спрямо предиката
  • връща вектор от филтрираните числа чрез join().

Главната нишка:

  • събира всички резултатни вектори във един общ
  • връща крайния филтриран вектор.

Задължително прочетете (или си припомнете): Указания за предаване на домашни

Погрижете се решението ви да се компилира с базовия тест:

// Include the solution source in the same file, so we
// don't have to worry about item visibility.
// Please don't use `include!` in real code, this is a hack
// around the checking system.
include!{ "../src/lib.rs" }
#[test]
fn test_basic() {
let data = random_vec_(8);
let n_threads = 2;
assert_eq!(
parallel_filter(data.clone(), n_threads, Predicate::GreaterThan100),
data.iter().copied().filter(|&x| x > 100).collect::<Vec<_>>(),
);
assert_eq!(
parallel_filter(data.clone(), n_threads, Predicate::Even),
data.iter().copied().filter(|&x| x % 2 == 0).collect::<Vec<_>>(),
);
assert_eq!(
parallel_filter(data.clone(), n_threads, Predicate::Prime),
data.iter()
.copied()
.filter(|&x| is_prime_(x))
.collect::<Vec<_>>(),
);
assert_eq!(
parallel_filter(data.clone(), n_threads, Predicate::DivisibleBy7),
data.iter().copied().filter(|&x| x % 7 == 0).collect::<Vec<_>>(),
);
}
#[test]
fn test_uneven_split() {
let data = random_vec_(59);
let n_threads = 3;
assert_eq!(
parallel_filter(data.clone(), n_threads, Predicate::GreaterThan100),
data.iter().copied().filter(|&x| x > 100).collect::<Vec<_>>(),
);
assert_eq!(
parallel_filter(data.clone(), n_threads, Predicate::Even),
data.iter().copied().filter(|&x| x % 2 == 0).collect::<Vec<_>>(),
);
assert_eq!(
parallel_filter(data.clone(), n_threads, Predicate::Prime),
data.iter()
.copied()
.filter(|&x| is_prime_(x))
.collect::<Vec<_>>(),
);
assert_eq!(
parallel_filter(data.clone(), n_threads, Predicate::DivisibleBy7),
data.iter().copied().filter(|&x| x % 7 == 0).collect::<Vec<_>>(),
);
}
fn is_prime_(n: i32) -> bool {
const PRIMES: &[i32] = &[
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,
109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359,
367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491,
499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641,
643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787,
797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
947, 953, 967, 971, 977, 983, 991, 997,
];
PRIMES.contains(&n)
}
fn random_vec_(len: usize) -> Vec<i32> {
// Don't have access to third-party crates, so can't use `rand`.
// Using a hash function as an ad-hoc random number generator.
struct Fnv1a {
state: u32,
prime: u32,
}
impl Fnv1a {
fn hash(&mut self, data: u32) -> u32 {
for byte in data.to_be_bytes() {
(self.state, _) = self.state.overflowing_mul(self.prime);
self.state = self.state ^ (byte as u32);
}
self.state
}
}
let mut fnv = Fnv1a {
state: 0x811c9dc5,
prime: 0x01000193,
};
(0..len)
.map(|i| (fnv.hash(i as u32) % 1000) as i32)
.collect()
}