LINUX.ORG.RU

Помогите написать этот код по-нормальному

 ,


1

3

Изучаю Rust, решаю всякие задачки. Понадобились простые числа, решил создать вспомогательный «класс» для их генерации. Идея в том, чтобы генерировать последовательность путём стандартного итерирования. Вроде решил, но как-то сложно получилась, какие-то лайфтаймы, мутабельности, такое ощущение, что перемудрил и юзать не очень удобно: нельзя просто написать for p in primes { ... }, только for p in &mut primes { ... }, можно ли как-то получше сделать? Если что, primes должен быть потенциально многоразовый.

fn main() {
    let mut primes = Primes::new();
    let mut counter = 0;
    for p in &mut primes {
        println!("{}", p);
        counter += 1;
        if counter > 10 {
            break;
        }
    }
}

struct Primes {
    cache: Vec<u64>,
}

impl Primes {
    fn new() -> Primes {
        Primes { cache: vec!(2, 3) }
    }
}

impl<'a> IntoIterator for &'a mut Primes {
    type Item = u64;
    type IntoIter = PrimesIterator<'a>;

    fn into_iter(self) -> PrimesIterator<'a> {
        PrimesIterator { cache: &mut self.cache, cache_index: 0 }
    }
}

struct PrimesIterator<'a> {
    cache: &'a mut Vec<u64>,
    cache_index: usize,
}

impl<'a> Iterator for PrimesIterator<'a> {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let result: u64;
        if self.cache_index < self.cache.len() {
            result = self.cache[self.cache_index];
        } else {
            let mut n = self.cache[self.cache_index - 1] + 2;
            loop {
                let mut i = 0;
                let is_prime = loop {
                    let p = self.cache[i];
                    if n % p == 0 {
                        break false;
                    }
                    if p * p > n {
                        break true;
                    }
                    i += 1;
                };
                if is_prime {
                    break;
                }
                n += 2;
            }
            self.cache.push(n);
            result = n;
        }
        self.cache_index += 1;
        Some(result)
    }
}
★★★★★

Если не хотите лайфтаймы - оберните Primes.cache в Rc.

нельзя просто написать for p in primes { ... }, только for p in &mut primes { ... }, можно ли как-то получше сделать?

Первый вариант забирает владение себе, второй нет. Думайте.

RazrFalcon ★★★★★
()
Ответ на: комментарий от RazrFalcon

Ну я могу написать for p in primes.into_iter() и всё работает, то бишь он как-то автоматом переписывает это в for p in (&mut primes).into_iter(), но без into_iter() не хочет переписывать, это выглядит странно.

Legioner ★★★★★
() автор топика
Ответ на: комментарий от hateyoufeel

Конечно с кешированием, как можно простые числа без кеширования искать, это же будет ад.

Legioner ★★★★★
() автор топика
Ответ на: комментарий от Legioner

Так всё правильно. https://doc.rust-lang.org/std/iter/index.html#for-loops-and-intoiterator

let result = match IntoIterator::into_iter(values) {

У вас IntoIterator реализован только для &mut Primes, вот его он и требует. Реализуйте чисто для Primes и будет ок.

Но для него не получится, так как нужна ссылка. Ибо вы хотите модифицировать себя, что в расте дурной тон.

RazrFalcon ★★★★★
()
Ответ на: комментарий от Legioner

Ну я могу написать for p in primes.into_iter() и всё работает, то бишь он как-то автоматом переписывает это в for p in (&mut primes).into_iter()

Автоматически это работает потому, что into_iter это метод, а методы осуществляют автоматическое заимствование (или владение) «объекта» в зависимости от своей сигнатуры (automatic referencing and dereferencing)

но без into_iter() не хочет переписывать, это выглядит странно

Мало сахарку, да?)

Virtuos86 ★★★★★
()
Ответ на: комментарий от Legioner

так как у тебя числа ограничены типом u64, то достаточно простого теста Миллера по 7 базам. Кэш не нужен.

anonymous
()
Ответ на: комментарий от RazrFalcon

вы хотите модифицировать себя, что в расте дурной тон.

Вот этот момент не понятен, почему это дурной тон и как можно сделать эту задачу не модифицируя себя? Или этот пример принципиально плохо ложится на Rust?

Legioner ★★★★★
() автор топика
Ответ на: комментарий от anonymous

Спасибо, надо будет почитать, хотя пока в первую очередь интересует такая реализация в рамках Rust, это всё же учебная задачка, а не реальная.

Legioner ★★★★★
() автор топика
Ответ на: комментарий от RazrFalcon

Кеширование это антипаттерн? По-моему это примерно как в C++ когда делают const-метод, который внутри меняет какие-то данные исходя из соображений производительности, при этом для внешнего наблюдателя это выглядит как иммутабельный объект. Тут то же самое. По сути генератор простых чисел это концептуально иммутабельный объект, то, что внутри мутабельный кеш, это уже дело внутренностей. Я понимаю, что в случае с Rust это не просто договорённости про мутабельность/иммутабельность, это поддержка компилятором более строгих гарантий, поэтому и пытаюсь понять, как это должно быть. Выше кинули ссылку, надо изучить, попробую ещё про Rc понять, пока не дошёл до этого класса, хотя исходя из названия кажется странным, зачем мне счётчик ссылок, вроде не нужен он мне.

Legioner ★★★★★
() автор топика
Ответ на: комментарий от Legioner

По-моему это примерно как в C++ когда делают const-метод, который внутри меняет какие-то данные

Такой же быдлокод, за исключением мютексов и прочих редких случаев.

зачем мне счётчик ссылок, вроде не нужен он мне

Тогда почему вы жалуетесь на лайфтаймы?

RazrFalcon ★★★★★
()
Ответ на: комментарий от Legioner

Или этот пример принципиально плохо ложится на Rust?

Да

можно сделать эту задачу не модифицируя себя?

Полностью без модификаций не выйдет. Ты ж в кэш пишешь. Но можешь погуглить про std::cell::RefCell что б не передавать свой контейнер по мутабельной ссылке.
Но я бы не стал использовать такое решение в данном контексте.

Aswed ★★★★★
()
Ответ на: комментарий от Legioner

Ну я могу написать for p in primes.into_iter() и всё работает, то бишь он как-то автоматом переписывает это в for p in (&mut primes).into_iter(), но без into_iter() не хочет переписывать, это выглядит странно.

По соглашению функции начинающиеся с `into_` поглощают свой аргумент. Так что различающееся поведение для `for p in primes` и `for p in primes.into_iter()` действительно выглядит странно и неожиданно.

Поэтому, если требуется только заимствовать аргумент, делают метод `iter()`: https://play.rust-lang.org/?gist=5c71edee34d34948b3ac413ae7439781&version...

red75prim ★★★
()
Последнее исправление: red75prim (всего исправлений: 1)
Ответ на: комментарий от Legioner

Я не могу понять тут комментаторы не знают про Cell и RefCell или просто дурят мозги?

anonymous
()

go кал. забей на него. тут нету экспертов по нему кроме чсвшных любителей смузи и побаловаться в попку

tz4678 ★★
()

Я понимаю, что rust для тебя в новинку, а с ФП скорее всего тоже не было опыта. Попробуй заменять циклы и счётчики на итераторы, везде где это возможно. Это превращает мешанину из переходов в линейный код.

struct PrimesIterator<'a> {
    cache: &'a mut Vec<u64>,
    cache_index: std::ops::RangeFrom<usize>,
}

impl<'a> Iterator for PrimesIterator<'a> {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let index = self.cache_index.next()?;

        self.cache.get(index).map(|n| *n).or_else(|| {
            let last = *self.cache.last().expect("cache is empty");
            (last..)
                .step_by(2)
                .skip(1)
                .find(|&n| {
                    self.cache
                        .iter()
                        .take_while(|&p| n % p != 0)
                        .any(|&p| p * p > n)
                })
                .map(|n| {
                    self.cache.push(n);
                    n
                })
        })
    }
}
anonymous
()
Ответ на: комментарий от anonymous

Спасибо, еле вкурил этот матан, давно уже не ковырял что-то нетривиальное. Интересные результаты, мой исходный вариант начинает за здравие и за первые 10 секунд генерирует примерно 2.1кк чисел, тогда как миллер-рабин генерирует примерно 1.75кк чисел (подозреваю, что если взять первую секунду, разница ещё больше), но очень быстро мой вариант проседает, а миллер-рабин, хотя тоже проседает, но примерно 100к в секунду продолжает выдавать доволно долго. Учитывая, что памяти он не жрёт, крутой результат.

Вот код, если кому интересно. Переделал на u32, судя по скорости мне этого хватит с головой. Что любопытно, на u32 скорость более чем в 2 раза больше. То ли кеш сказался, то ли деление 32-битных чисел работает намного быстрей 64-битных.

pub struct Primes {
    next_candidate: u32,
}

impl Primes {
    pub fn new() -> Primes {
        Primes { next_candidate: 2 }
    }
}

const BASE_1_MAX: u32 = 49141;
const BASE_1: [u32; 1] = [921211727];
const BASE_2_MAX: u32 = 360018361;
const BASE_2: [u32; 2] = [1143370, 2350307676];
const BASE_3: [u32; 3] = [15, 176006322, 4221622697];


impl Iterator for Primes {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        let mut candidate = self.next_candidate;
        if candidate == 2 {
            self.next_candidate = 3;
            return Some(2)
        }
        if candidate < 9 {
            self.next_candidate = candidate + 2;
            return Some(candidate);
        }
        while candidate % 3 == 0 || candidate % 5 == 0 || candidate % 7 == 0 {
            candidate = candidate + 2;
        }
        while candidate < BASE_1_MAX {
            if mr_test_probably_prime(candidate, BASE_1.iter()) == None {
                self.next_candidate = candidate + 2;
                return Some(candidate);
            }
            candidate += 2;
        }
        while candidate < BASE_2_MAX {
            if mr_test_probably_prime(candidate, BASE_2.iter()) == None {
                self.next_candidate = candidate + 2;
                return Some(candidate);
            }
            candidate += 2;
        }
        while candidate < u32::max_value() {
            if mr_test_probably_prime(candidate, BASE_3.iter()) == None {
                self.next_candidate = candidate + 2;
                return Some(candidate);
            }
            candidate += 2;
        }
        self.next_candidate = candidate;
        None
    }
}

// Miller–Rabin test
// if there's a witness that n is composite, it's returned as Some(a)
// if there are not witnesses that n is composite (which means that n is probably prime), None returned
pub fn mr_test_probably_prime<'a, T>(n: u32, bases: T) -> Option<u32>
    where T: Iterator<Item = &'a u32> {
    let n1 = n - 1;
    let s = n1.trailing_zeros();
    let d = n1 >> s;

    'base_loop: for base in bases {
        let mut a = *base;
        if a >= n {
            a %= n;
            if a == 0 {
                continue;
            }
        }
        let mut x = mod_pow(a, d, n);
        if x == 1 || x == n - 1 {
            continue;
        }
        for _ in 1..s {
            x = (x as u64 * x as u64 % n as u64) as u32;
            if x == 1 {
                return Some(*base);
            }
            if x == n1 {
                continue 'base_loop;
            }
        }
        return Some(*base);
    }
    None
}

// c = (a^e)%m
fn mod_pow(mut a: u32, mut e: u32, m: u32) -> u32 {
    let mut c: u32 = 1;
    while e > 0 {
        if e & 1 != 0 {
            c = (c as u64 * a as u64 % m as u64) as u32;
        }
        a = (a as u64 * a as u64 % m as u64) as u32;
        e = e >> 1;
    }
    c
}

#[cfg(test)]
mod tests {
    #[test]
    fn primes_test() {
        use super::Primes;
        assert_eq!(vec!(2, 3, 5, 7, 11, 13, 17, 19, 23, 29), Primes::new().take(10).collect::<Vec<u32>>());
        assert_eq!(Primes::new().nth(9999), Some(104729));
    }

    #[test]
    fn mr_test_probably_prime() {
        use super::mr_test_probably_prime;
        assert_eq!(mr_test_probably_prime(221, vec!(174, 137).iter()), Some(137));
        assert_eq!(mr_test_probably_prime(252601, vec!(85132).iter()), Some(85132));
        assert_eq!(mr_test_probably_prime(3057601, vec!(99908).iter()), Some(99908));
        assert_eq!(mr_test_probably_prime(104717, vec!(96152).iter()), None);
        assert_eq!(mr_test_probably_prime(577757, vec!(314997).iter()), None);
        assert_eq!(mr_test_probably_prime(101089, vec!(314997).iter()), None);
        assert_eq!(mr_test_probably_prime(280001, vec!(105532).iter()), None);
        assert_eq!(mr_test_probably_prime(95721889, vec!(21906436).iter()), Some(21906436));
        assert_eq!(mr_test_probably_prime(30121, vec!(2).iter()), Some(2));
        assert_eq!(mr_test_probably_prime(75361, vec!(2).iter()), Some(2));
        assert_eq!(mr_test_probably_prime(65, vec!(1, 8, 18, 47, 57, 64).iter()), None);
        assert_eq!(mr_test_probably_prime(85, vec!(1, 13, 38, 47, 72, 84, 69).iter()), Some(69));
        assert_eq!(mr_test_probably_prime(49141, vec!(921211727).iter()), None);
        assert_eq!(mr_test_probably_prime(360018361, vec!(1143370, 2350307676).iter()), None);
    }

    #[test]
    fn mod_pow() {
        use super::mod_pow;
        assert_eq!(mod_pow(3, 0, 5), 1); // 3^0 % 5 = 0 % 5 = 1
        assert_eq!(mod_pow(3, 1, 5), 3); // 3^1 % 5 = 3 % 5 = 4
        assert_eq!(mod_pow(3, 2, 5), 4); // 3^2 % 5 = 9 % 5 = 4
        assert_eq!(mod_pow(3, 3, 5), 2); // 3^3 % 5 = 27 % 5 = 2
        assert_eq!(mod_pow(2345678901, 3456789012, 4152637485), 469297656);
    }
}

Legioner ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.