From 62fe810c118c37b596c5329b9360fec2b33b04b0 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Wed, 18 Nov 2020 08:47:12 -0500 Subject: ks: Use sort_unstable_by_key rather than sort_by_cached_key The comparison key is just a single coordinate, no need for the overhead of caching. --- src/kd.rs | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/src/kd.rs b/src/kd.rs index dae73ec..5434ddd 100644 --- a/src/kd.rs +++ b/src/kd.rs @@ -14,7 +14,7 @@ use std::ops::Deref; /// A node in a k-d tree. #[derive(Debug)] struct KdNode { - /// The vantage point itself. + /// The item stored in this node. item: T, /// The left subtree, if any. left: Option>, @@ -51,7 +51,7 @@ impl KdNode { return None; } - nodes.sort_by_cached_key(|x| Ordered::new(x.as_ref().unwrap().item.coord(level))); + nodes.sort_unstable_by_key(|x| Ordered::new(x.as_ref().unwrap().item.coord(level))); let (left, right) = nodes.split_at_mut(nodes.len() / 2); let (node, right) = right.split_first_mut().unwrap(); @@ -317,7 +317,7 @@ where /// A node in a flat k-d tree. #[derive(Debug)] struct FlatKdNode { - /// The vantage point itself. + /// The item stored in this node. item: T, /// The size of the left subtree. left_len: usize, @@ -347,7 +347,7 @@ impl FlatKdNode { /// Create a balanced subtree. fn balance_recursive(nodes: &mut [Self], level: usize) { if !nodes.is_empty() { - nodes.sort_by_cached_key(|x| Ordered::new(x.item.coord(level))); + nodes.sort_unstable_by_key(|x| Ordered::new(x.item.coord(level))); let mid = nodes.len() / 2; nodes.swap(0, mid); -- cgit v1.2.3