When I use these different solutions on leetcode the "for loop" version is 4ms and the "iterator" version is 44ms fairly consistently. I know the pseudo-benchmark I'm using on the playground is not equivalent, but it consistently seems to give a faster result with the "iterator" version. Can anyone explain why one might be faster or slower than the other?
use std::collections::HashMap;
fn main() {
let nums = vec![1, 2, 3, 4, 5];
let k = 1i32;
let start1 = time::precise_time_s();
for _ in 0..100000 {
find_pairs(nums.clone(), k);
}
let end1 = time::precise_time_s();
for _ in 0..100000 {
iter_find_pairs(nums.clone(), k);
}
let end2 = time::precise_time_s();
println!("for loop time: {}", end1 - start1);
println!("iterator approach time: {}", end2 - end1);
}
pub fn find_pairs(nums: Vec<i32>, k: i32) -> i32 {
if nums.is_empty() || k < 0 {
return 0;
}
let mut tally = HashMap::with_capacity(nums.len());
for num in nums {
*tally.entry(num).or_insert(0) += 1;
}
let mut count = 0;
for (num, _val) in tally.iter() {
if let Some(paired_num) = tally.get(&(num - k)) {
if k > 0 {
count += 1
} else if k == 0 && *paired_num > 1 {
count += 1
}
}
}
count
}
pub fn iter_find_pairs(nums: Vec<i32>, k: i32) -> i32 {
let mut tally = HashMap::with_capacity(nums.len());
for num in nums.iter() {
*tally.entry(num).or_insert(0) += 1;
}
match k {
k if k < 0 => 0,
k if k == 0 => tally.iter().filter(|(_, val)| **val > 1).count() as i32,
_ => tally
.iter()
.filter(|(x, _)| nums.contains(&(**x - k)))
.count() as i32,
}
}
Your HashMap makes things difficult to actually time because an iterator is essentially
let internal_HashMap = vec![(1, 1), (2, 1), (3, 1), (4, 1)];
for i in internal_HashMap {}
while the other requires something like this
let internal_HashMap = ///
let val_to_compare = {
//Hash the value we `get` on
};
for (hash, data) in internal_HashMap {
if hash == val_to_compare {return Some(&data);}
}
None
your other methods are fast but do not do the same thing. The goal is to find complementary pairs such that the difference between them is k. you are just finding matches of k.
Sorry, it seems I might've overlooked what the algorithm was trying to actually do
In any case, my point on how the iterator would be faster still somewhat stands, in that an iterator would essentially require iterating over a set of key/value pairs and checking equality, while a for loop would force you to hash each value and then look for it in the key/value pairs.
Make sure to benchmark the code in release mode, it makes a big difference:
Compiling playground v0.0.1 (/playground)
Finished release [optimized] target(s) in 1.68s
Running `target/release/playground`
Standard Output
for loop time: 0.032227625139057636
iterator approach time: 0.029460886493325233
But as others have said, the code is quite different in the two versions, so I would start by making it more equal and then do benchmarking afterwards.
I didn't do a good job in the original post by not providing the prompt for the problem. In essence the goal is to find number pairs with an absolute difference of k in a set of numbers, but each pair is only counted once. So for k = 2 and nums = [1,3,4,1] the count is 1 because (1,3) and (3,1) are duplicates. This is why a HashMap is used, to ensure uniqueness but still be able to find pairs for k = 0.
If I understand your point correctly, you are saying the iterator should be expected to be faster than the for loop because the hash function is applied in each iteration of the for loop. That makes sense and is consistent with what I get on the playground but contradicts the output I get from the leetcode site.
Thanks. With regard to release vs debug mode, that shouldn't affect the relative efficiency of the different methods to one another much, should it? For instance even in your output the for loop is still slower than the iterator method. Which is in contrast to what the leetcode site returns. I'm just trying to figure out what it is about the different approaches that would make one more efficient than the other. So far the major differentiating factor seems to be HashMap::get() vs slice::contains() and the precedence for checking k == 0.
UPDATE:
I think the get() vs contains() was the biggest differentiator. Using the same match syntax and precedence for checking k == 0 did not have much impact, but using the slice::contains() vs HashMap::get() in the for loop made it slightly faster than the iterator version. Changing the iterator version to use fold() vs chaining filter().count() made no impact. I wonder if some of the test cases in the leetcode problem actually make the get() approach more efficient than the contains() one. Maybe for a very large sequence of numbers searching the HashMap is more efficient than searching the slice, but in smaller sequences the slice is faster.
