How can I repeat some elements in a vector based on a condition?
I ran into this issue during kata . My more readable implementation was as follows:
use std::vec::Vec;
fn repeat_even(v: Vec<i32>) -> Vec<i32> {
v.into_iter().flat_map(|x| match x % 2 { 0 => vec![x, x], _ => vec![x] }).collect()
}
fn main() {
let v = vec![1, 2, 3, 4, 6];
assert_eq!(repeat_even(v), vec![1, 2, 2, 3, 4, 4, 6, 6]);
}
I have two questions:
-
Do I need to create another one
Vec
? Can I use the sameVec
, i.e. Change it during iteration? -
My solution, I think, is inefficient: I am allocating a lot of vectors and I have no guarantee that this will be optimized. Is there a better solution: readable and with less distribution?
source to share
flat_map
expects iterators, so you can return an iterator of values:
use std::iter;
fn double_even(v: &[i32]) -> Vec<i32> {
v.iter().flat_map(|&x| {
let count = if x % 2 == 0 { 2 } else { 1 };
iter::repeat(x).take(count)
}).collect()
}
fn main() {
let v = vec![1, 2, 3, 4, 6];
assert_eq!(double_even(&v), vec![1, 2, 2, 3, 4, 4, 6, 6]);
}
Notes:
- There is no reason to have
use std::vec::Vec
. It is already imported via prelude . - You are not using memory allocation of the passed vector so there is no reason to accept it. See Also Why is it not a good idea to accept a String (& String) or Vec (& Vec) reference as a function argument?
- Do not use
vec!()
; use insteadvec![]
. This is not important to the compiler, but it is important to humans.
If you are really configured to try to reuse memory, I would go backwards through the iterator to avoid invalidating the index:
fn double_even(mut v: Vec<i32>) -> Vec<i32> {
for i in (0..v.len()).rev() {
let val = v[i];
if val % 2 == 0 {
v.insert(i, val);
}
}
v
}
This is probably algorithmically worse; each insert
moves all the data after it. I believe the worst case would be O(n^2)
when each element is even.
I would also normally not take meaning here. I would use a variable reference instead. You can always set it back to value if you really need it:
fn double_even_ref(v: &mut Vec<i32>) {
for i in (0..v.len()).rev() {
let val = v[i];
if val % 2 == 0 {
v.insert(i, val);
}
}
}
fn double_even(mut v: Vec<i32>) -> Vec<i32> {
double_even_ref(&mut v);
v
}
source to share
You could do this within the same vector, but you would have to move the rest of the vector (after the doubled number) every time you encounter an even number, which is inefficient. It would be better to do this using a new vector and a simple loop:
fn main() {
let v = vec![1, 2, 3, 4, 6];
let mut v2 = Vec::with_capacity(v.len() + v.iter().filter(|&n| n % 2 == 0).count());
for n in v {
v2.push(n);
if n % 2 == 0 { v2.push(n) }
}
assert_eq!(v2, vec![1, 2, 2, 3, 4, 4, 6, 6]);
}
This solution only allocates memory once with the exact space needed to store all numbers, including doubled values.
source to share
Do I need to create another one
Vec
? Is it possible to use the sameVec
, i.e. Change it during iteration?
This is possible, but not effective. Vec
allocates a block of memory on the heap, where each element is adjacent to the next. If you just want to perform some kind of numeric operation on each item, then yes, you can do that operation in place. But you need to insert new elements between others, which would mean moving all the following elements one place to the right and (possibly) allocating more memory.
The Haskell code you're thinking of probably uses Haskell Data.List
, which is a linked list, not a vector. If you have used more cost-effective storage structure, for example Data.Vector.Unboxed
, or repa , you will also not be able to insert elements during iteration.
My solution is inefficient in my opinion: I am allocating a lot of vectors and I have no guarantee that this will be optimized. Is this the best solution: readable and with less placement?
Something like this might work. It has a functional feel, but works by isolating one Vec
and then mutating it:
fn double_even(v: Vec<i32>) -> Vec<i32> {
// allocate for the worst case (i.e. all elements of v are even)
let result = Vec::with_capacity(v.len() * 2);
v.into_iter().fold(result, |mut acc, n| {
acc.push(n);
if n % 2 == 0 {
acc.push(n);
}
acc
})
}
You can also shrink_to_fit()
at the end, but that would look a little ugly since you couldn't return the solution as an expression.
source to share
Do I need to create another Vec? Can the same Vec be used, i.e. Change it during iteration?
My solution, I think, is inefficient: I am allocating a lot of vectors and I have no guarantee that this will be optimized. Is there a better solution: readable and with less distribution?
One thing you can do, which is pretty idiomatic, is to implement your function as an "iterator adapter", that is, instead of dealing with Vec
a particular look at the Iterator
elements i32
. Then everything will be a variable on the stack and no allocation will be made at all. It might look something like this:
struct DoubleEven<I> {
iter: I,
next: Option<i32>,
}
impl<I> Iterator for DoubleEven<I>
where I: Iterator<Item=i32>
{
type Item = i32;
fn next(&mut self) -> Option<Self::Item> {
self.next.take().or_else(||
self.iter.next().map(|value| {
if value % 2 == 0 { self.next = Some(value) }
value
})
)
}
}
Then you can write
fn main() {
let vec = vec![1, 2, 3, 4, 5, 6];
let double_even = DoubleEven {
iter: vec.into_iter(),
next: None,
};
for x in double_even {
print!("{}, ", x) // prints 1, 2, 2, 3, 4, 4, 5, 6, 6,
}
}
Better yet, you can add a function double_even
to anything that can be turned into an iterator i32
, allowing you to write the following:
trait DoubleEvenExt : IntoIterator + Sized {
fn double_even(self) -> DoubleEven<Self::IntoIter> {
DoubleEven {
iter: self.into_iter(),
next: None,
}
}
}
impl<I> DoubleEvenExt for I where I: IntoIterator<Item=i32> {}
fn main() {
let vec = vec![1, 2, 3, 4, 5, 6];
for x in vec.double_even() {
print!("{}, ", x) // prints 1, 2, 2, 3, 4, 4, 5, 6, 6,
}
}
Now I admit that in this case the templating bar is folded, but you can see that the code in the call site is really very concise. For more complex adapters, this pattern can be very useful. Also, apart from the initial allocation Vec
, there is no memory allocation at all! Simply stacked variables that allow for highly efficient code in a release build.
source to share