RC
пример достаточно синтетический, но хочется подружить хэшмапу с рекурсией
Size: a a a
2021 June 13
Э
Сильно зависит от конкретных примеров, в данном случае хашмапа не нужна, да и код работает, какая разница, будет ли он однострочником.
RC
в примере нахождение энного числа последовательности Фибоначчи, с использованием приёмов динамического программирования, мемоизации просчитанных значений.
RC
понятно, что можно и так. только я так ничему новому не научусь = )
TK
Через itertools::unfold попробуй
TK
Там будет ограниченная мемоизация в форме следующих двух элементов последовательности
RC
так это ж без рекурсии?
TK
Ну да, только рекуррентное соотношение всё равно будет задано, и итератор можно будет коллектнуть
ΑZ
а ещё можно матрицу перемножать. Тогда можно куда быстрее ответ получить. И тут уже можно магии научитьсЯ)
RC
ok, круто! https://habr.com/ru/post/261159/
правда, я не за этим пришёл, но спасибо! = )
правда, я не за этим пришёл, но спасибо! = )
RC
тогда вопрос наверно сводится к владению.. в методе рекурсию нельзя?
ΑZ
если вмесо скриншота кидать на плейграунд ссылку то ответ будет куда чаще и быстрее
Э
Во-первых,
or_insert жадно вычисляет передаваемые аргументы, использовать тут надо or_insert_with. Во-вторых, у тебя незаполненный entry, а ты пытаешься в хашмапу запихать ещё значения. Это та же фигня, которая происходит при запихивании значений в вектор, пока итератор в этот вектор ещё жив.TK
entry может инвалидироваться в результате изменения содержимого мапы, поэтому там и не работает .or_insert_with (который вообще-то стоило использовать вместо .or_insert). Ещё с такой рекурсией будут проблемы в виде переполнения стека: просматривать нужно глубоко, когда впервые от большого числа считаешь.
ΑZ
ну это то же дин программирование, только цикл в итератор пихнули..
Не понял какую роль filter играет
Не понял какую роль filter играет
TK
Ограничение на переполнение u64
ΑZ
сделал бы толгда checked_add
ΑZ
use itertools::unfold;
fn fib() -> impl Iterator<Item = u64> {
unfold((0u64, 1u64), |x| {
let ret = x.0;
x.0 = x.1;
x.1 = x.1.checked_add(ret)?;
Some(ret)
})
}
fn main() {
let fib: Vec<_> = fib().take(10).collect();
println!("{:?}", fib);
}TK
Не, так можно максимум элементов выжать и эффективнее чутка