铁锈桶分类

Question

首先，守则：

struct Bucket<H, V> where H: Ord
{
    hash: H,
    values: Vec<V>
}

impl<H, V> Bucket<H, V> where H: Ord {
    fn new(hash: H) -> Bucket<H, V> {
        Bucket {
            hash: hash,
            values: vec![],
        }
    }
}

pub fn bucket_sort<T, F, H>(values: Vec<T>, hasher: F) -> Vec<T>
    where T: Ord, F: Fn(&T) -> H, H: Ord
{

    let mut buckets: Vec<Bucket<H, T>> = vec![];

    for value in values.into_iter() {
        let hash = hasher(&value);
        match buckets.binary_search_by(|bucket| bucket.hash.cmp(&hash)) {
            Ok(index) => {
                buckets[index].values.push(value);
            },
            Err(index) => {
                let mut bucket = Bucket::new(hash);
                bucket.values.push(value);
                buckets.insert(index, bucket);
            }
        }
    }

    let mut sorted_values = Vec::new();
    for bucket in buckets.into_iter() {
        let mut bucket = bucket;
        bucket.values.sort();
        sorted_values.extend(bucket.values);
    }
    sorted_values
}

#[test]
fn test_bucket_sort() {
    let values = vec![5, 10, 2, 99, 32, 1, 7, 9, 92, 135, 0, 54];
    let sorted_values = bucket_sort(values, |int| int / 10);
    assert_eq!(sorted_values, vec![0, 1, 2, 5, 7, 9, 10, 32, 54, 92, 99, 135]);
}

困扰我的是，这个实现是破坏性的：bucket_sort拥有一个向量，并构建另一个向量。我首先尝试用以下签名实现桶排序：

pub fn bucket_sort<T, F, H>(values: &[T], hasher: F) -> Vec<T>
where T: Ord, F: Fn(&T) -> H, H: Ord

但我意识到传球意味着：

• 任何排序都必须就位进行。
• 或者元素必须实现Copy

Copy-ing对大量值的限制过于严格，而且可能效率低下，我不知道是否有可能通过桶排序实现就地排序。

除此之外，这种实现是否存在明显的风格/性能缺陷？

Answer 1

干得好！我注意到的一件事是extend的使用；这表明您已经在API文档中查看了什么是可用的。大多数情况下，人们从一个向量到另一个向量的所有元素都是从push开始的。

但我意识到传球意味着：

• 任何排序都必须就位进行。
• 或者元素必须实现Copy

这个分析是正确的，恭喜！事实上，这是我喜欢的铁锈的类型系统。如果我将一个方法交给一个&mut [T]，那么我就知道它很可能会在适当的地方做一些事情，大概是以一种有效的方式。

Copy-ing在大量值上...可能没有效率。

实现Copy的类型是那些通过复制位而不执行任何附加代码而在语义上重复的类型。一般来说，这是处理器擅长的事情。另一方面，属于Clone的类型在复制时需要进行一些额外的计算。这些都是你想要小心复制不必要的东西。总的来说，我不担心做一些拷贝。

但是，您关于Copy可能受到过度限制的观点是很有道理的。

1. where子句在一条单独的行上，每一个附加的限制也在一条单独的行上。这有助于可读性和理解，因为这些限制可以极大地改变函数的调用方式。
2. 在锈蚀的任何地方都要使用后缀逗号。
3. 我不喜欢对不需要的结构或方法添加类型限制。
4. 当我可以直接将集合传递给接受into_iter的东西时，我宁愿不使用IntoIterator。
5. 选择一个Vec::new或vec![]，并与之保持一致。
6. 更喜欢for mut bucket in buckets而不是重新绑定变量只是为了增加可变性。
7. 扩展Bucket::new以获取一个值。您并不需要创建一个空桶的能力。
8. match的武器可以是单线的。
9. flat_map和collect可用于将所有中间向量合并为一个。
10. 比较一个Vec<T>和一个T数组是可以的。在测试中使用这一点，以避免不必要地分配另一个向量。

struct Bucket<H, V> {
    hash: H,
    values: Vec<V>,
}

impl<H, V> Bucket<H, V> {
    fn new(hash: H, value: V) -> Bucket<H, V> {
        Bucket {
            hash: hash,
            values: vec![value],
        }
    }
}

pub fn bucket_sort<T, F, H>(values: Vec<T>, hasher: F) -> Vec<T>
    where T: Ord,
          F: Fn(&T) -> H,
          H: Ord
{
    let mut buckets: Vec<Bucket<H, T>> = Vec::new();

    for value in values {
        let hash = hasher(&value);
        match buckets.binary_search_by(|bucket| bucket.hash.cmp(&hash)) {
            Ok(index) => buckets[index].values.push(value),
            Err(index) => buckets.insert(index, Bucket::new(hash, value)),
        }
    }

    buckets.into_iter().flat_map(|mut bucket| {
        bucket.values.sort();
        bucket.values
    }).collect()
}

#[test]
fn test_bucket_sort() {
    let values = vec![5, 10, 2, 99, 32, 1, 7, 9, 92, 135, 0, 54];
    let sorted_values = bucket_sort(values, |int| int / 10);
    assert_eq!(sorted_values,
               [0, 1, 2, 5, 7, 9, 10, 32, 54, 92, 99, 135]);
}