I'm trying to flatten a vector of 2 element tuples.
Here is what I came out with
let endpoints:Vec<i32> = intervals.iter().fold(Vec::new(), |mut array, c| {
array.push(c.0);
array.push(c.1);
array
});
`.
intervals is the vector of 2-element tuples
Any better elegant way of doing this ?
I would stick to that method and maybe hide it behind a trait.
A simpler version would be using flat_map, but that doesn't work, because tuples are not iterable. This comes from the fact that they could be homogenous and not necessarily have elements of the same type.
You could optimise a little, though, by using Vec::with_capacity(intervals.len() * 2) instead of new, which makes sure that the resulting Vec does not reallocate during the fold operation.
I've studied the resulting asm of few alternative solutions:
#![allow(private_no_mangle_fns)]
#[no_mangle]
#[inline(never)]
fn flatten1(data: &[(i32, i32)]) -> Vec<i32> {
data
.iter()
.fold(Vec::with_capacity(data.len() * 2),
|mut acc, p| { acc.extend(&[p.0, p.1]); acc })
}
#[no_mangle]
#[inline(never)]
fn flatten2(data: &[(i32, i32)]) -> Vec<i32> {
data
.iter()
.fold(Vec::with_capacity(data.len() * 2),
|mut acc, p| { acc.push(p.0); acc.push(p.1); acc })
}
#[no_mangle]
#[inline(never)]
fn flatten3(data: &[(i32, i32)]) -> Vec<i32> {
let mut result = Vec::with_capacity(data.len() * 2);
for &(a, b) in data {
result.push(a);
result.push(b);
}
result
}
#[no_mangle]
#[inline(never)]
fn flatten4(data: &[(i32, i32)]) -> Vec<i32> {
let mut result = vec![0; data.len() * 2];
for (i, &(a, b)) in data.iter().enumerate() {
result[i * 2 + 0] = a;
result[i * 2 + 1] = b;
}
result
}
#[no_mangle]
#[inline(never)]
fn flatten5(data: &[(i32, i32)]) -> Vec<i32> {
let len = data.len() * 2;
let mut result = Vec::with_capacity(len);
unsafe {
for (i, &(a, b)) in data.iter().enumerate() {
*result.get_unchecked_mut(i * 2) = a;
*result.get_unchecked_mut(i * 2 + 1) = b;
}
result.set_len(len);
}
result
}
#[no_mangle]
#[inline(never)]
fn flatten6(data: &[(i32, i32)]) -> Vec<i32> {
let mut result = data.to_vec();
unsafe {
result.set_len(data.len() * 2);
std::mem::transmute(result)
}
}
fn main() {
for flatten in &[flatten1, flatten2, flatten3,
flatten4, flatten5, flatten6] {
println!("{:?}", flatten(&[(1,2), (3,4), (5,6)]));
println!("{:?}", flatten(&[(1,2), (3,4)]));
}
}
For a system programmer flatten6 is probably the most reasonable solution, it's short, fast (it's equivalent to a malloc + memcpy), and unsafe (but the types are inferred, this avoids some bugs).
But for its signature I'd like to write some like this (that's allowed in D language), that is less bug-prone:
fn flatten6(data: &[(i32, i32)]) -> Vec<typeof(data[0].0)> {
flatten4 looks efficient but the compiler is fails to see that a vec of pairs of length N is fitting inside a 2*N array, so both array accesses have bound tests.
flatten5 avoids that problem, but it's a bad idea to write code like that for i32 data.
The asm of flatten1 seems a bit worse than flatten2 that has two simpler push.
iter::once and chain to the rescue!
fn flatten(intervals: &[(i32, i32)]) -> Vec<i32> {
use std::iter::once;
intervals.iter()
.flat_map(|tup| once(tup.0).chain(once(tup.1)))
.collect()
}
Alternatively,
.flat_map(|tup| [tup.0, tup.1].iter().cloned())
(Note that these flat_map solutions won't be as fast as the ones provided by @leonardo, mostly due to FlatMap not providing appropriate size_hint)
Sure, you can construct an intermediate that is iterable, but I would call both versions hard to grok.
@leonardo, you should propose a Flatten trait for itertools and implement it for all types of type (T, T, ..., T). That flatten6 of yours is probably going to be the most elegant (if you can call unsafe that) and performant solution.
In Itertools I expect lazy iterables, so probably a solution based on flat_map.
I'm looking at the bare beauty of flatten6, and wondering about the assumptions encoded in it about tuple layout. Would this work for any T?
If you want a lazy operation:
#![allow(private_no_mangle_fns)]
#![feature(conservative_impl_trait)]
#[no_mangle]
#[inline(never)]
fn flatten7<'a>(data: &'a [(i32, i32)]) -> impl Iterator<Item=i32> + 'a {
use std::iter::once;
data
.iter()
.flat_map(|&(a, b)| once(a).chain(once(b)))
}
#[no_mangle]
#[inline(never)]
fn flatten8(data: &[(i32, i32)]) -> &[i32] {
use std::mem::transmute;
use std::slice::from_raw_parts;
unsafe {
transmute( from_raw_parts(data.as_ptr(), data.len() * 2) )
}
}
fn main() {
let a1 = [(1,2), (3,4), (5,6)];
let a2 = [(1,2), (3,4)];
println!("{:?}", flatten7(&a1).collect::<Vec<_>>());
println!("{:?}", flatten7(&a2).collect::<Vec<_>>());
println!("{:?}", flatten8(&a1));
println!("{:?}", flatten8(&a2));
}
/*
flatten8:
leaq (%rsi,%rsi), %rdx
movq %rdi, %rax
retq
*/
@leonardo's flatten6 would be my favorite if it weren't for the fact that I think that it is undefined behavior. The Nomicon says:
Transmuting between non-
repr(C)types is UB
Since afaik neither Vec<T> nor tuples are repr(C), I decided to go with one of the safe versions instead.
Transmuting between non-repr(C) types is UB
Since afaik neither Vec nor tuples arerepr(C),
If all items of a tuple are of the same type then I think the risk is lower.
Unfortunately in Rust you can't dispatch a generic algorithm on Vec differently at compile time if T is repr(C), currently... I think.
I think tuple is the problematic one here - tuples do not have a guaranteed layout. If one could replace the tuple with a 2-element array, then I think this is sound given arrays guarantee their layout. On top of that, Vec provides a bunch of additional guarantees about its layout and behavior: Vec in std::vec - Rust. So I think those two things together ought to make array+Vec sound.
For the Vec part, it can be handled reliably with Vec in std::vec - Rust
Personally I think repr(rust) should just guarantee that (T, T) is layout-compatible with [T; 2], and suspect there's code out there relying on it already, but...
If you'd like to argue that this should be fixed, see the discussion in this PR:
I wonder how the performance of this compares to flattening-based approaches?
let mut vec: Vec<u32> = tuples.iter().map(|(a, _)| *a).collect();
let vec2: Vec<u32> = tuples.iter().map(|(_, b)| *b).collect();
vec.extend(vec2);
A lot of approaches in this thread can't be multi-threaded with Rayon but I'm not sure if this approach would do any better since it's essentially 3 serial operations.