Функция Аккермана в Русте


Используя алгоритм в конце этого исследования, я написал чрезвычайно быстрый 1 Аккермана функция в Русте. Может реализация быть быстрее?

Мысли:

  • Используя структуру struct делает много смысла, но это странно, чтобы Some(Box::new(v2)). Этого можно избежать каким-то образом?
  • Для петли лучший способ делать v преобразований? Будет (1..(i + 1)).fold(Record::new(1, 0, None), |v, k| a_use_p(k - 1, 1, v)) быть более "деревенский"? Кажется, немного быстрее, но это трудно сказать.
  • Есть ли способ, чтобы распараллелить этот? Или любой его части?

Спасибо.

extern crate time;

use time::PreciseTime;

fn main() {
    let m = 3;

    for n in 1..20 {
        let s = PreciseTime::now();
        let res = fast_ackermann(m, n);
        let e = PreciseTime::now();
        println!("a_opt(3, {}) -> {} took {}", n, res, s.to(e))
    }
}

#[derive(Clone)]
struct Record {
    result: u64,
    previous_result: u64,
    cache: Option<Box<Record>>,
}

impl Record {
    fn new(result: u64, previous_result: u64, cache: Option<Box<Record>>) -> Record {
        Record { result, previous_result, cache }
    }
}

fn fast_ackermann(m: u64, n: u64) -> u64 {
    let mut cache = Record::new(1, 0, None);
    for m_builder in 0..m {
        cache = ack_with_incrementalization(m_builder, 1, cache)
    }
    for n_builder in 1..(n + 1) {
        cache = ack_with_incrementalization(m, n_builder, cache)
    }
    cache.result
}

fn ack_with_incrementalization(m: u64, n: u64, current_cache: Record) -> Record {
    if m == 0 {
        Record::new(n + 1, 0, None)
    } else if n == 0 {
        let mut new_cache = Record::new(1, 0, None);
        for m_builder in 0..m {
            new_cache = ack_with_incrementalization(m_builder, 1, new_cache);
        }
        new_cache
    } else if n == 1 {
        let cache_result = current_cache.result;
        let mut new_cache = current_cache;
        for n_builder in 2..(cache_result + 1) {
            new_cache = ack_with_incrementalization(m - 1, n_builder, new_cache);
        }
        Record::new(new_cache.result, cache_result, Some(Box::new(new_cache)))
    } else {
        let cache_result = current_cache.result;
        let mut new_cache = *current_cache.cache.unwrap();
        for n_builder in (current_cache.previous_result + 1)..(current_cache.result + 1) {
            new_cache = ack_with_incrementalization(m - 1, n_builder, new_cache);
        }
        Record::new(new_cache.result, cache_result, Some(Box::new(new_cache)))
    }
}

1 С m = 3, n = 20, код занимает 0.95 секунд. С n = 30 она занимает 16 минут. В статье n = 20 занимает 5.05 секунд и n =30 занимает 87 минут. Вариант с промежуточным кэшем (в ржавчине), n = 20 взял 2,1 секунды и n = 25 (а не 30 как у других) занимает 39 минут.



184
2
задан 1 марта 2018 в 08:03 Источник Поделиться
Комментарии
1 ответ

Я понял, что вложенные отчеты не идут более 3-х глубоких (внешний, средний, внутренний), что означает, что он может быть переписан, чтобы использовать примитивные массивы.

Сравнение 1:

n: 20
fas_ack -> 8388605 took PT0.399960323S
arr_ack -> 8388605 took PT0.115302129S
n: 25
fas_ack -> 268435453 took PT11.283535003S
arr_ack -> 268435453 took PT3.553065491S
n: 30
fas_ack -> 8589934589 took PT757.605898139S
arr_ack -> 8589934589 took PT233.040801010S

Сравнение 2:

n: 20
fas_ack -> 8388605 took PT0.807311828S
arr_ack -> 8388605 took PT0.442201425S
n: 25
fas_ack -> 268435453 took PT35.765848937S
arr_ack -> 268435453 took PT14.004015773S
n: 30
fas_ack -> 8589934589 took PT959.685955407S
arr_ack -> 8589934589 took PT141.390498532S

Обновленный код:

extern crate time;

use time::PreciseTime;

fn main() {
let m = 3;

for n in [20, 25, 30].iter() {
println!("n: {}", n);
let s = PreciseTime::now();
let res = arr_ack(m, *n);
let e = PreciseTime::now();
println!("arr_ack -> {} took {}", res, s.to(e))
}
}

fn arr_ack(m: u64, n: u64) -> u64 {
let mut cache: [u64; 6] = [0; 6];
cache[0] = 1;
for m_builder in 0..m {
cache = _arr_ack(m_builder, 1, cache)
}
for n_builder in 1..(n + 1) {
cache = _arr_ack(m, n_builder, cache)
}
cache[0]
}

fn _arr_ack(m: u64, n: u64, mut cache: [u64; 6]) -> [u64; 6] {
if m == 0 {
[n + 1, 0, 0, 0, 0, 0]
} else if m == 1 {
[n + 2, 0, 0, 0, 0, 0]
} else if n == 0 {
let mut new_cache = [1, 0, 0, 0, 0, 0];
for m_builder in 0..m {
new_cache = _arr_ack(m_builder, 1, new_cache);
}
new_cache
} else if n == 1 {
let previous_result = cache[0];
for n_builder in 2..(previous_result + 1) {
cache = _arr_ack(m - 1, n_builder, cache);
}
[cache[0], previous_result, cache[0], cache[1], cache[2], cache[3]]
} else {
let previous_result = cache[0];
let mut new_cache = [cache[2], cache[3], cache[4], cache[5], 0, 0];
for n_builder in (cache[1] + 1)..(previous_result + 1) {
new_cache = _arr_ack(m - 1, n_builder, new_cache);
}
[new_cache[0], previous_result, new_cache[0], new_cache[1], new_cache[2], new_cache[3]]
}
}

2
ответ дан 2 марта 2018 в 08:03 Источник Поделиться