From ed51d48f7353a5ceefa798ded52d3af465d4d0ec Mon Sep 17 00:00:00 2001 From: Vika Date: Mon, 13 Nov 2023 22:19:42 +0300 Subject: Switch reply contexts from a Vec to HashMap This reduces the worst-case complexity to O(n) from O(n^2). --- src/micropub/mod.rs | 31 +++++++++++++++---------------- 1 file changed, 15 insertions(+), 16 deletions(-) diff --git a/src/micropub/mod.rs b/src/micropub/mod.rs index c3e78fe..4a501bb 100644 --- a/src/micropub/mod.rs +++ b/src/micropub/mod.rs @@ -1,4 +1,5 @@ use std::collections::HashMap; +use url::Url; use std::sync::Arc; use crate::database::{MicropubChannel, Storage, StorageError}; @@ -58,18 +59,15 @@ struct FetchedPostContext { fn populate_reply_context( mf2: &serde_json::Value, prop: &str, - ctxs: &[FetchedPostContext], + ctxs: &HashMap, ) -> Option> { mf2["properties"][prop].as_array().map(|array| { array .iter() - // TODO: This seems to be O(n^2) and I don't like it. - // Switching `ctxs` to a hashmap might speed it up to O(n) - // The key would be the URL/UID .map(|i| { - let mut item = ctxs - .iter() - .find(|ctx| Some(ctx.url.as_str()) == i.as_str()) + let mut item = i.as_str() + .and_then(|i| i.parse::().ok()) + .and_then(|url| ctxs.get(&url)) .and_then(|ctx| ctx.mf2["items"].get(0)) .unwrap_or(i) .clone(); @@ -153,13 +151,13 @@ async fn background_processing( .get("webmention") .and_then(|i| i.first().cloned()); - dbg!(Some(FetchedPostContext { + dbg!(Some((url.clone(), FetchedPostContext { url, mf2: serde_json::to_value(mf2).unwrap(), webmention - })) + }))) }) - .collect::>() + .collect::>() .await }; @@ -201,9 +199,9 @@ async fn background_processing( tokio_stream::iter( post_contexts .into_iter() - .filter(|ctx| ctx.webmention.is_some()), + .filter(|(url, ctx)| ctx.webmention.is_some()), ) - .for_each_concurrent(2, |ctx| async move { + .for_each_concurrent(2, |(url, ctx)| async move { let mut map = std::collections::HashMap::new(); map.insert("source", uid); map.insert("target", ctx.url.as_str()); @@ -729,16 +727,17 @@ mod tests { "content": ["This is a post which was reacted to."] } }); - let reply_contexts = vec![FetchedPostContext { - url: "https://fireburn.ru/posts/example".parse().unwrap(), + let fetched_ctx_url: url::Url = "https://fireburn.ru/posts/example".parse().unwrap(); + let reply_contexts = vec![(fetched_ctx_url.clone(), FetchedPostContext { + url: fetched_ctx_url.clone(), mf2: json!({ "items": [test_ctx] }), webmention: None, - }]; + })].into_iter().collect(); let like_of = super::populate_reply_context(&mf2, "like-of", &reply_contexts).unwrap(); assert_eq!(like_of[0]["properties"]["content"], test_ctx["properties"]["content"]); - assert_eq!(like_of[0]["properties"]["url"][0].as_str().unwrap(), reply_contexts[0].url.as_str()); + assert_eq!(like_of[0]["properties"]["url"][0].as_str().unwrap(), reply_contexts[&fetched_ctx_url].url.as_str()); assert_eq!(like_of[1], already_expanded_reply_ctx); assert_eq!(like_of[2], "https://fireburn.ru/posts/non-existent"); -- cgit 1.4.1