如何对向量中的切片序列进行排序？

Question

我有一个数据结构，从概念上讲，我有一个整数元组序列，所有大小都相同。然而，这个大小在编译时是未知的，所以我不能使用实际的元组或数组等：它们需要在类型中指定它们的长度。这类似于迭代器上的

chunks

方法，只不过我需要随机访问“元组”。所以我想将其实现为整数

Vec

，将这些“元组”作为 Vec 的连续切片进行访问。例如，序列

(1, 2, 4), (1, 2, 3), (2, 2, 1)

将表示为向量

[1, 2, 4, 1, 2, 3, 2, 2, 1]

，其中“块大小”单独存储，并以

v[i * chunk_size .. (i+1) * chunk_size]

的形式访问第 i 个切片。我有一些工作。

现在我想按字典顺序对切片序列进行排序，从概念上将上面的内容变成

(1, 2, 3), (1, 2, 4), (2, 2, 1)

，这意味着向量将变成

[1, 2, 3, 1, 2, 4, 2, 2, 1]

。当然，我可以实现自己的简单排序算法来做到这一点，但如果可能的话，我想将切片包装到某个结构中，实现

Ord

，然后调用

sort_unstable()

。像这样的东西：

#[derive(PartialEq, Eq, Ord, PartialOrd)]
struct Chunk<'a>
{
    slice: &'a [usize],
}

impl<'a> Chunk<'a> {
    /// Consider chunks as a collection of slices of length chunk_size. Sort
    /// this collection in place, leaving each slice intact. This will panic
    /// if the length of `chunks` is not a multiple of `chunk_size`.
    pub fn sort_slice_of_chunks(mut chunks: &[usize], chunk_size: usize) {
        let n_slices = chunks.len() / chunk_size();
        let mut chunk_objects: Vec<_> = (0 .. n_slices)
           .map(|i| Chunk {
                slice: &chunks[i * chunk_size..(i + 1) * chunk_size],
            })
            .collect();
        chunk_objects.sort_unstable();
    }
}

但是，这只会对我的块对象的向量

chunk_objects

进行排序，而不是对底层切片进行排序。有没有办法让

sort_unstable()

修改底层切片，或者这是错误的方法？我应该硬着头皮实施 Introsort 吗？

Answer 1

要使用切片方法就地排序，要排序的值在编译时需要有一个已知的大小，因为在底层它是作为交换实现的，它需要知道它要交换的东西的大小执行交换的代码。这意味着您必须知道每个子数组的长度，以便使用内置切片排序方法进行就地排序。如果 Rust 让您以某种方式专门化交换操作，那么您可以使用新类型通过运行时提供的子数组长度来完成此操作，但这是不可能的。

据我所知，有两种方法可以在某种程度上有效地处理这个问题，而无需求助于构建自己的就地排序：

1. 您可以收集

   Vec

   切片并对它们进行排序（就像您在此处所做的那样），然后将该排序应用于原始

   Vec

   。 这需要少量且恒定的分配数量。
2. 您可以使用原始数组来构建

   Vec<Vec<_>>

   ，对其进行排序，然后将其展平。 这很简单，不需要不安全的代码，但需要 N+2 额外的分配。

如何解决第一种方法？ 好吧，我们不能只交换底层数组中的内容，因为借用检查器不允许我们这样做。 有一种方法可以使用大量不安全的代码来处理这个问题，但也许更简单的是通过收集每个子数组的所有起始索引来“制作我们自己的切片”。 我们不需要长度，因为我们已经有了它 (

chunk_size

)，所以这也需要使用切片的一半内存。

我们仍然需要一些不安全的代码来进行实际的交换。

让我们构建这个函数：

pub fn sort_chunks<T: Ord>(chunks: &mut [T], chunk_size: usize);

首先，我们需要收集开始每个子数组的索引。

let mut chunk_indices: Vec<_> = (0..chunks.len()).step_by(chunk_size).collect();

然后根据原始数组的相应子部分的排序方式对它们进行排序。

chunk_indices.sort_unstable_by(|&a, &b| chunks[a..(a + chunk_size)].cmp(&chunks[b..(b + chunk_size)]));

好吧...现在怎么办？ 我们不能盲目地移动东西，因为经典问题是一些重新排列形成一个循环，例如子切片 0 属于位置 1，子切片 1 属于位置 0。

除了实现一个非常复杂的算法来处理这个问题之外，最简单的方法是创建一个新的分配来暂时按新顺序保存元素，然后将它们写回。

我们仍然需要不安全的代码，但不是那么多。 我们将把每个

T

的内容“窃取”到新数组中，然后将它们写回。 为了确保这是安全的，我们希望在开始传输数据之前预先分配空间来保存临时副本。

let mut new_order: Vec<T> = Vec::with_capacity(chunk_indices.len() * chunk_size);

分配此空间后，我们可以将

T

从

chunks

移出并放入新的

Vec

中。 当我们这样做时，我们将它们重新排序为最终顺序。

new_order.extend(
    chunk_indices
        .into_iter()
        .flat_map(|i| (i..(i + chunk_size)).map(|i| unsafe { std::ptr::read(&chunks[i]) })),
);

最后，我们将它们传输回源切片。

for (dest, src) in chunks.iter_mut().zip(new_order) {
    unsafe {
        std::ptr::write(dest, src);
    }
}

请注意，这会消耗临时副本而不删除它们，因为我们将副本移动到

std::ptr::write

，据记录不会删除源值。

大家一起：

pub fn sort_chunks<T: Ord>(chunks: &mut [T], chunk_size: usize) {
    let mut chunk_indices: Vec<_> = (0..chunks.len()).step_by(chunk_size).collect();

    chunk_indices
        .sort_unstable_by(|&a, &b| chunks[a..(a + chunk_size)].cmp(&chunks[b..(b + chunk_size)]));

    // Allocate before we do this stuff to ensure we can't panic.
    let mut new_order: Vec<T> = Vec::with_capacity(chunk_indices.len() * chunk_size);

    new_order.extend(
        chunk_indices
            .into_iter()
            .flat_map(|i| (i..(i + chunk_size)).map(|i| unsafe { std::ptr::read(&chunks[i]) })),
    );

    for (dest, src) in chunks.iter_mut().zip(new_order) {
        unsafe {
            std::ptr::write(dest, src);
        }
    }
}

据我所知，即使对于非

Copy

，这也是合理的，因为任何

T

都不应该被丢弃在

sort_chunks

中。 但是，如果您限制

T: Copy

，则可以完全消除不安全的代码。

pub fn sort_chunks<T: Copy + Ord>(chunks: &mut [T], chunk_size: usize) {
    let mut chunk_indices: Vec<_> = (0..chunks.len()).step_by(chunk_size).collect();

    chunk_indices
        .sort_unstable_by(|&a, &b| chunks[a..(a + chunk_size)].cmp(&chunks[b..(b + chunk_size)]));

    // Allocate before we do this stuff to ensure we can't panic.
    let mut new_order: Vec<T> = Vec::with_capacity(chunk_indices.len() * chunk_size);

    new_order.extend(
        chunk_indices
            .into_iter()
            .flat_map(|i| (i..(i + chunk_size)).map(|i| chunks[i])),
    );

    for (dest, src) in chunks.iter_mut().zip(new_order) {
        *dest = src;
    }
}