使用tokio在Rust中调用递归API的有效方法
使用tokio在Rust中调用递归API的有效方法
提问于 2022-11-25 05:52:11
问题
我最近参加了一次编码考试，遇到了一个类似下面的问题。
我用另一种语言解决了这个问题，但现在我试图用Rust来解决这个问题，以提高我的锈蚀编码技能.
您将得到数字n和一个API端点。
实现以下函数f(n)并输出f(n)的值
f(0) = 1
f(2) = 2
f(n) = f(n-1)+f(n-2)+f(n-3) (when n %2 == 0)
f(n) = CallAPI(n) (when n%2 !=0)- CallAPI函数返回0到100之间的数字。
- 如果输入值n是相同的，CallAPI函数总是返回相同的值。
- 应该尽可能少地调用CallAPI函数。
我的解决方案
我认为可以通过实现函数回忆录来解决这个问题，所以我编写了这样的代码。
use std::{
collections::HashMap,
sync::{Arc, Mutex},
};
use async_recursion::async_recursion;
type Memo = Arc<Mutex<HashMap<usize, usize>>>;
#[tokio::main]
pub async fn main() -> Result<(), Box<dyn std::error::Error>> {
// In real situation number n would be passed as a input argument.
let n = "60";
let mut temp = HashMap::new();
temp.insert(0, 1);
temp.insert(2, 2);
let memo: Memo = Arc::new(Mutex::new(temp));
let ans = f(n.parse::<usize>().expect("error"), memo).await;
println!("{}", ans);
Ok(())
}
#[async_recursion]
async fn f(n: usize, memo: Memo) -> usize {
if let Some(&ans) = memo.lock().unwrap().get(&n) {
return ans;
}
if n % 2 == 0 {
let memo1 = memo.clone();
let memo2 = memo.clone();
let memo3 = memo.clone();
let (one, two, three) = tokio::join!(f(n - 1, memo1), f(n - 2, memo2), f(n - 3, memo3));
let ans = one + two + three;
let mut mut_memo = memo.lock().unwrap();
mut_memo.insert(n, ans);
ans
} else {
let n_str = n.to_string();
let ans = ask_server(&n_str).await;
let mut mut_memo = memo.lock().unwrap();
mut_memo.insert(n, ans);
ans
}
}
async fn ask_server(n: &String) -> usize {
// In real situation I sent HTTP GET Request(So this function needs to be async) and return a number that is contained in response, bot just return 100 for simplicity.
100
}它看起来很管用，但是它的性能肯定不是很好。(我为我糟糕的密码感到抱歉.)我认为这是因为每次都会锁定“备忘录”变量。但我不知道如何改进这个代码，尽管我尽了全力.
我想问那些知道如何处理锈菌的人，它是如何有效地实施的。
回答 1
Stack Overflow用户
回答已采纳
发布于 2022-11-25 07:12:30
我的第一步是研究这个问题，并找出我们是否可以将输入重写成更方便的形式。
f(0) = 1
f(1) = CallAPI(1)
f(2) = 2
f(3) = CallAPI(3)
f(4) = CallAPI(3) + 2 + CallAPI(1)
f(5) = CallAPI(5)
f(6) = CallAPI(5) + 2 * CallAPI(3) + 2 + CallAPI(1)从这里开始，我注意到的第一个模式是，当n大于3时，通常有2种情况，如果n是奇数，那么我们可以默认使用CallAPI。然而，如果n是偶数，则我们的总数变成(CallAPI(n - 1) + CallAPI(n - 3)) + (CallAPI(n - 3) + CallAPI(n - 5)) + ... + 2。正如您所看到的，我们使用前面的值调用CallAPI的唯一时间是直接跟随的调用。这很好，因为我们可以将其转换为一种迭代方法，在这种方法中，可以将多个异步调用分组在一起。这让我们可以同时等待更多的未来。虽然我们可以尝试并发执行每个CallAPI，但我们不希望耗尽系统上的所有内存并重载API服务器，因此我们可以施加一个限制，在给定的时间只发送有限数量的请求。
在所有这些之后，我将如何编写解决方案。请记住，async锈蚀不是我的专长，因此可能有一个较短的方式，这可以写。
use futures::prelude::*;
use futures::stream::FuturesUnordered;
// The maximum number of concurrent API calls to call concurrently in an
// unordered futures group.
const API_CALL_LIMIT: usize = 64;
#[tokio::main]
pub async fn main() -> Result<(), Box<dyn std::error::Error>> {
let answer = f(60).await;
println!("{}", answer);
Ok(())
}
async fn f(n: usize) -> usize {
match n {
0 => 1,
2 => 2,
x if x % 2 != 0 => perform_api_call(x).await,
x => {
let mut group = FuturesUnordered::new();
// Create iterator of values to put through the API
let mut search_values = (3..x - 1).step_by(2);
// Fill the unordered futures group up to the call limit
for y in (&mut search_values).take(API_CALL_LIMIT) {
group.push(perform_api_call(y));
}
let mut total = 0;
// Once call limit is reached, the remaining values to get from the
// API are added when a new position opens up.
for y in search_values {
// Wait for empty position
if let Some(result) = group.next().await {
total += 2 * result;
} else {
unreachable!("There must be remaining items if we are still pushing entries");
}
// Push new future to replace the one we just popped
group.push(perform_api_call(y));
}
// The first and last calls are special since they are not doubled
let first_call = perform_api_call(1);
let last_call = perform_api_call(x - 1);
// Wait for remaining entries in the group
while let Some(result) = group.next().await {
total += 2 * result;
}
// Add in the first and last entries along with f(2).
2 + total + first_call.await + last_call.await
}
}
}
async fn perform_api_call(_: usize) -> usize {
100
}如果我们试图模拟执行HTTP请求所需的时间，这种差异就会更加明显。
use std::time::Duration;
async fn perform_api_call(_: usize) -> usize {
tokio::time::sleep(Duration::from_millis(500)).await;
100
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/74568781
复制相关文章
相似问题
腾讯云开发者
