Min Distance Target

An exercise finding nearest element in a slice. Several sequential solutions and an easy parallelization.

We consider today the min distance to target element pb.

Being given a slice, a target value and a start index we want to return the minimal distance from start in the slice where to find the target.

For example, for a slice [0,4,2,3,1,2,4,0] if the target is 4 and the start is 2 then we can find targets at positions 1 and 6. The nearest position from start is position 1 at distance 2-1 = 1 which shall be returned.

We will consider the following input generator:

use rand::prelude::*;
fn random_input(limit: u32, length: usize) -> (Vec<u32>, u32, usize) {
    let nums: Vec<_> = std::iter::repeat_with(|| rand::random::<u32>() % limit)
        .take(length)
        .collect();
    let target = nums.choose(&mut rand::thread_rng()).copied().unwrap();
    let start = rand::random::<usize>() % length;
    (nums, target, start)
}

and we should complete the following function:

fn get_min_distance(nums: &[u32], target: u32, start: usize) -> Option<usize> {
    todo!()
}

Sequential Solutions

Ok, the first sequential solution which might come to mind is to just transcribe the definition of the solution into code: returning the minimal distance.

fn get_min_distance(nums: &[u32], target: u32, start: usize) -> Option<usize> {
    nums.iter()
        .enumerate()
        .filter(|&(_, e)| *e == target)
        .map(|(i, _)| (i as isize - start as isize).abs() as usize)
        .min()
}

This is straightforward and has a nice linear time worst case complexity. It has however a drawback: the best case complexity is also linear and this could be avoided. If we start looking for targets in the neighbourhood of the start then any match should end the algorithm. We can thus avoid looking at the whole slice and abort the execution early. We need a way to loop on all positions from the start, increasing gradually their distances.

Let’s see our solution:

use itertools::Itertools;
fn get_min_distance2(nums: &[u32], target: u32, start: usize) -> Option<usize> {
    let n = nums.len();
    (start..n)
        .interleave((0..start).rev())
        .find(|&nums_index| nums[nums_index] == target)
        .map(|i| (i as isize - start as isize).abs() as usize)
}

Here we just interleave two ranges iterators. The first one is leaving start towards higher indices and the second one leaving start towards lower indices. We can then use find to abort the execution as soon as we meet a target.

Parallel Solutions

For once the parallel solutions are pretty straightforward. We just need to switch to parallel iterators and change the find to find_first.

fn par_get_min_distance(nums: &[u32], target: u32, start: usize) -> Option<usize> {
    nums.par_iter()
        .enumerate()
        .filter(|&(_, e)| *e == target)
        .map(|(i, _)| (i as isize - start as isize).abs() as usize)
        .min()
}

fn par_get_min_distance2(nums: &[u32], target: u32, start: usize) -> Option<usize> {
    let n = nums.len();
    (start..n)
        .into_par_iter()
        .interleave((0..start).into_par_iter().rev())
        .find_first(|&nums_index| nums[nums_index] == target)
        .map(|i| (i as isize - start as isize).abs() as usize)
}

Note that interleave is available in rayon while not yet in the standard lib.

I did a quick bench but performances are not that great for rayon here on my laptop. I guess it is again too memory intensive. You can play with the benchmark here if you like.