Count and Say
Reducing lists with extra operations.
We are going to code a “count and say” algorithm.
We have as input a slice of integers and we need to output how we would read it aloud.
For example the slice [5,5,2,2,2,4,8,8,8] would be read as:
two fives, three twos, one four, three eights.
The slice [1,1,1,3,3,2,3,3,1] would be read as: three ones, two threes, one two, two
threes, one one.
We return a Vec<(usize, u32)> which would be
[(2,5), (3,2), (1,4), (3,8)][(3,1), (2,3), (1,2), (2,3), (1,1)]for our two examples.
For the parallel code we give you a hint:
fn par_count_and_say(s: &[u32]) -> Vec<(usize, u32)> {
rayon::iter::split(s, |s| {
if s.len() < 2 {
(s, None)
} else {
let mid = s.len() / 2;
let (left, right) = s.split_at(mid);
(left, Some(right))
}
})
this parallel iterator will iterate an subslices of s (decomposed dynamically).
As you can see this implies nothing special is done when dividing.
This means some extra operations must take place during the reduction.
You can find some code to complete here.
Sequential Solution
use itertools::Itertools;
fn count_and_say(s: &[u32]) -> Vec<(usize, u32)> {
s.iter()
.group_by(|e| *e)
.into_iter()
.map(|(key, group)| (group.into_iter().count(), *key))
.collect()
}
Nothing special here, I just use the group_by method of the itertools crate.
Parallel Solution
Ok, lets go for the parallel code.
What we do is:
- divide into subslices
- solve each subslice indenpendently
- collect all vectors using the list trick
- fuse sequentially
Now the fusion needs something special. Let’s take an example:
[1,1,1,3,3,2,3,3,1].
Assume we split as:
[1,1,1,3]- and
[3,2,3,3,1].
We would then obtain as partial solutions:
[(3,1),(1,3)]- and
[(1,3),(1,2),(2,3),(1,1)]
Now in order to merge these partial solutions we need to see that the last number of the left slice is also the first number of the right slice so their counters need to be merged.
We end up with the following code:
#![feature(iterator_fold_self)]
use rayon::prelude::*;
use std::collections::LinkedList;
fn par_count_and_say(s: &[u32]) -> Vec<(usize, u32)> {
rayon::iter::split(s, |s| {
if s.len() < 2 {
(s, None)
} else {
let mid = s.len() / 2;
let (left, right) = s.split_at(mid);
(left, Some(right))
}
})
.map(|s| count_and_say(s))
.map(|v| std::iter::once(v).collect())
.reduce(LinkedList::new, |mut l1, mut l2| {
l1.append(&mut l2);
l1
})
.into_iter()
.fold_first(|mut v1, v2| {
let skipped = v1
.last_mut()
.and_then(|(ref mut last_count, last_key)| {
v2.first().map(|(first_count, first_key)| {
if first_key == last_key {
*last_count += first_count;
1
} else {
0
}
})
})
.unwrap_or(0);
v1.par_extend(v2.into_par_iter().skip(skipped));
v1
})
.unwrap_or_else(Vec::new)
}
I leave you with the whole archive if you want to give it a try.
Now, here is a last question:
There is another way to solve this problem by doing additional operations on the division
instead of the reduction: we can adjust the splitting point such that we ensure the two
sub-slices are such that the end value of the left is different from the start value of the
right.
For example we can cut
[1,1,1,3,3,2,3,3,1] as:
[1,1,1,3,3][2,3,3,1]
and everything would be fine.
From a Work point of view. Which is the best option ?