commit d30eda15e81c51dafe6cd9c56313a72733da3609
parent 93d8a9a54ff8eae2c2997137c0e7bd75e632ec80
Author: ling0x <ling0x@users.noreply.github.com>
Date: Sat, 11 Apr 2026 15:45:49 +0100
tests: add benchmark
Diffstat:
2 files changed, 111 insertions(+), 16 deletions(-)
diff --git a/Cargo.toml b/Cargo.toml
@@ -4,7 +4,7 @@ version = "0.1.0"
edition = "2024"
[dependencies]
+tracing = "*"
[dev-dependencies]
-tracing = "*"
tracing-subscriber = "*"
diff --git a/src/hash_table/two_sum.rs b/src/hash_table/two_sum.rs
@@ -1,40 +1,135 @@
-use std::collections::HashSet;
+use tracing::info;
-// First try
-pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
- let mut result = HashSet::<i32>::new();
+// 101ms, 2.37MB
+pub fn two_sum_1(nums: Vec<i32>, target: i32) -> Vec<i32> {
+ let mut result = std::collections::HashSet::<i32>::new();
nums.iter().enumerate().for_each(|(idx, x)| {
let pair = nums
.iter()
.enumerate()
.find(|(idx2, y)| *y + x == target && &idx != idx2);
- if let Some((idx2, y)) = pair {
+ if let Some((idx2, _)) = pair {
result.insert(idx as i32);
result.insert(idx2 as i32);
- println!("result: {} + {:?} = {}", x, y, target);
}
});
- println!("{:#?}", result);
result.into_iter().collect()
}
+// 56ms, 2.23MB
+pub fn two_sum_2(nums: Vec<i32>, target: i32) -> Vec<i32> {
+ let mut result = std::collections::HashSet::<i32>::new();
+
+ for (idx, num) in nums.iter().enumerate() {
+ let pair = target - num;
+ let idx2 = nums
+ .iter()
+ .enumerate()
+ .position(|(i, x)| x == &pair && i != idx);
+ if let Some(idx2) = idx2 {
+ result.insert(idx as i32);
+ result.insert(idx2 as i32);
+ return result.into_iter().collect();
+ }
+ }
+ result.into_iter().collect()
+}
+
+// 86ms, 2.28MB
+pub fn two_sum_3(nums: Vec<i32>, target: i32) -> Vec<i32> {
+ for (i, x) in nums.iter().enumerate() {
+ let idx = nums
+ .iter()
+ .enumerate()
+ .rposition(|(i2, y)| i2 != i && *y == target - x);
+ if let Some(idx) = idx {
+ return Vec::from([i as i32, idx as i32]);
+ }
+ }
+ Vec::new()
+}
+
#[cfg(test)]
mod tests {
- use crate::hash_table::two_sum::two_sum;
- use crate::test_utils::benchmark::run_with_metrics;
+ use tracing::info;
+
+ use crate::hash_table::two_sum::{two_sum_1, two_sum_2, two_sum_3};
+ use crate::test_utils::benchmark::{init_benchmark_tracing, run_with_metrics};
+
+ fn assert_indices_any_order(mut actual: Vec<i32>, mut expected: Vec<i32>) {
+ actual.sort_unstable();
+ expected.sort_unstable();
+ assert_eq!(actual, expected);
+ }
+
+ #[test]
+ // #[ignore]
+ fn two_sum_1_test_1() {
+ init_benchmark_tracing();
+ let (result, _) = run_with_metrics("two_sum_1_test_1", || two_sum_1(vec![2, 7, 11, 15], 9));
+ assert_indices_any_order(result, vec![0, 1]);
+ }
+ #[test]
+ // #[ignore]
+ fn two_sum_1_test_2() {
+ init_benchmark_tracing();
+ let (result, _) = run_with_metrics("two_sum_1_test_2", || two_sum_1(vec![3, 2, 3], 6));
+ assert_indices_any_order(result, vec![0, 2]);
+ }
+ #[test]
+ // #[ignore]
+ fn two_sum_1_test_3() {
+ init_benchmark_tracing();
+ let (result, _) = run_with_metrics("two_sum_1_test_3", || two_sum_1(vec![3, 2, 4], 6));
+ assert_indices_any_order(result, vec![1, 2]);
+ }
+
+ #[test]
+ // #[ignore]
+ fn two_sum_2_test_1() {
+ init_benchmark_tracing();
+ let (result, _) = run_with_metrics("two_sum_2_test_1", || two_sum_2(vec![2, 7, 11, 15], 9));
+ assert_indices_any_order(result, vec![0, 1]);
+ }
+ #[test]
+ // #[ignore]
+ fn two_sum_2_test_2() {
+ init_benchmark_tracing();
+ let (result, _) = run_with_metrics("two_sum_2_test_2", || two_sum_2(vec![3, 2, 3], 6));
+ assert_indices_any_order(result, vec![0, 2]);
+ }
+ #[test]
+ // #[ignore]
+ fn two_sum_2_test_3() {
+ init_benchmark_tracing();
+ let (result, _) = run_with_metrics("two_sum_2_test_3", || two_sum_2(vec![3, 2, 4], 6));
+ assert_indices_any_order(result, vec![1, 2]);
+ }
#[test]
- fn two_sum_test_1() {
- let _ = run_with_metrics("two_sum_test_1", || two_sum(vec![2, 7, 11, 15], 9));
+ // #[ignore]
+ fn two_sum_3_test_1() {
+ init_benchmark_tracing();
+ let (result, _) = run_with_metrics("two_sum_3_test_1", || two_sum_3(vec![2, 7, 11, 15], 9));
+ info!("{result:?}");
+ assert_indices_any_order(result, vec![0, 1]);
}
#[test]
- fn two_sum_test_2() {
- let _ = run_with_metrics("two_sum_test_2", || two_sum(vec![3, 2, 3], 6));
+ // #[ignore]
+ fn two_sum_3_test_2() {
+ init_benchmark_tracing();
+ let (result, _) = run_with_metrics("two_sum_3_test_2", || two_sum_3(vec![3, 2, 3], 6));
+ info!("{result:?}");
+ assert_indices_any_order(result, vec![0, 2]);
}
#[test]
- fn two_sum_test_3() {
- let _ = run_with_metrics("two_sum_test_3", || two_sum(vec![3, 2, 4], 6));
+ // #[ignore]
+ fn two_sum_3_test_3() {
+ init_benchmark_tracing();
+ let (result, _) = run_with_metrics("two_sum_3_test_3", || two_sum_3(vec![3, 2, 4], 6));
+ info!("{result:?}");
+ assert_indices_any_order(result, vec![1, 2]);
}
}
