一维元素空间分配问题：基于填充因子的Rust实现优化需求

我需要在指定空间内布局一维元素。元素拥有初始尺寸，可拉伸以填充可用空间，但不可收缩。每个元素关联一个填充因子（fill factor），用于确定与其他元素的理想尺寸比例。填充因子为0的元素始终保持初始尺寸。

当初始尺寸与可用空间无法实现理想相对尺寸分配时，我希望分配额外空间，使新的相对尺寸尽可能接近最优值。我未指定“最接近”的具体衡量标准，但绝不希望为相对空间已大于其相对填充因子的元素分配更多空间。

我编写了一个Rust实现，根据相对填充因子分配额外可用空间，但仅在有足够可用空间达成最优尺寸比例时有效。空间不足时会失效，因为它总会为所有填充因子为正的元素分配一些额外空间。

以下是我的代码及测试用例，希望能展示我的需求。

fn allocate_space(
    current_sizes: &[f32],
    fill_factors: &[u16],
    available_space: f32,
) -> Vec<f32> {
    // Assumptions
    {
        assert_eq!(current_sizes.len(), fill_factors.len());
        assert!(current_sizes.iter().sum::<f32>() <= available_space);
    }

    // Implementation
    let mut sizes = Vec::from(current_sizes);
    let fill_factor_sum = fill_factors.iter().sum::<u16>();

    // I'll probably need this
    let _fixed_size = current_sizes
        .iter()
        .zip(fill_factors)
        .filter_map(|(space, fill_factor)| {
            (*fill_factor == 0u16).then_some(space)
        })
        .sum::<f32>();

    if fill_factor_sum > 0 {
        let extra_space = available_space - sizes.iter().sum::<f32>();
        for (space, fill_factor) in sizes.iter_mut().zip(fill_factors) {
            *space += f32::from(*fill_factor) / f32::from(fill_factor_sum)
                * extra_space;
        }
    }

    // Constraints on the result
    {
        for ((current_size, new_size), fill_factor) in
            current_sizes.iter().zip(&sizes).zip(fill_factors)
        {
            // The allocated space is not allowed to shrink
            assert!(new_size >= current_size);
            // Items with a fill factor of zero keep their original size
            if *fill_factor == 0u16 {
                assert_eq!(current_size, new_size);
            }
        }
        // Can't use more space than available
        assert!(sizes.iter().sum::<f32>() <= available_space);
    }

    sizes.into()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn enough_space_for_relative_fill_factors() {
        assert_eq!(allocate_space(&[1.0, 1.0], &[1, 1], 4.0), vec![2.0, 2.0]);
        assert_eq!(allocate_space(&[1.0, 1.0], &[1, 1], 5.0), vec![2.5, 2.5]);
    }

    #[test]
    fn not_enough_space_for_relative_fill_factors() {
        assert_eq!(allocate_space(&[1.0, 2.0], &[1, 1], 3.5), vec![1.5, 2.0]);
    }

    #[test]
    fn unequal_fill_factors() {
        assert_eq!(allocate_space(&[1.0, 1.0], &[1, 2], 3.0), vec![1.0, 2.0]);
        assert_eq!(allocate_space(&[1.0, 1.0], &[1, 2], 2.5), vec![1.0, 1.5]);
    }

    #[test]
    fn fixed_spaces() {
        assert_eq!(
            allocate_space(&[1.0, 2.0, 2.0], &[0, 1, 1], 7.0),
            vec![1.0, 3.0, 3.0]
        );
        assert_eq!(
            allocate_space(&[1.0, 2.0, 2.0], &[0, 1, 2], 6.0),
            vec![1.0, 2.0, 3.0]
        );
    }

    #[test]
    fn three_variable_sizes() {
        assert_eq!(
            allocate_space(&[1.0, 1.0, 2.0], &[1, 2, 1], 4.0),
            vec![1.0, 1.0, 2.0]
        );
        assert_eq!(
            allocate_space(&[1.0, 1.0, 2.0], &[1, 2, 1], 6.0),
            vec![1.0 + 1.0 / 3.0, 2.0 + 2.0 / 3.0, 2.0]
        );
        assert_eq!(
            allocate_space(&[1.0, 1.0, 2.0], &[1, 2, 1], 7.0),
            vec![1.0 + 2.0 / 3.0, 3.0 + 1.0 / 3.0, 2.0]
        );
        assert_eq!(
            allocate_space(&[1.0, 1.0, 2.0], &[1, 2, 1], 8.0),
            vec![2.0, 4.0, 2.0]
        );
    }
}

我直觉认为这个问题有相对简单的解决方案，但我还没完全想出来。

我提供Rust代码示例是因为我在Rust程序中使用，但也欢迎任何语言、伪代码、数学公式或文字形式的帮助。

编辑
以下是我基于@btilly的答案实现的版本，使用float-cmp crate检查f32的近似相等性。

use std::cmp::Ordering;

#[derive(Debug, Clone, Copy, PartialEq)]
struct Item {
    size: f32,
    fill_factor: u16,
}

impl Item {
    fn size_over_fill(&self) -> f32 {
        self.size / self.fill_factor as f32
    }
}

fn item(size: f32, fill_factor: u16) -> Item {
    Item { size, fill_factor }
}

fn allocate_space(items: Vec<Item>, available_space: f32) -> Vec<f32> {
    assert!(
        items.iter().map(|i| i.size).sum::<f32>() <= available_space,
        "Sum of current sizes is smaller than total available space"
    );

    // Implementation
    let mut fill_factor_sum = items.iter().map(|i| i.fill_factor).sum::<u16>();
    let fixed_space = items
        .iter()
        .filter_map(|i| (i.fill_factor == 0).then_some(i.size))
        .sum::<f32>();
    let mut size_sum = available_space;

    let sorted_items = sort_items(items.clone());

    let mut new_sizes = sorted_items
        .iter()
        .map(|(i, item)| {
            let fill_size =
                item.fill_factor as f32 / fill_factor_sum as f32 * size_sum;
            let new_size = if item.size < fill_size {
                fill_size
            } else {
                item.size
            };
            size_sum -= new_size;
            fill_factor_sum -= item.fill_factor;
            (i, new_size)
        })
        .collect::<Vec<_>>();

    // Sort the elements back into original order
    new_sizes.sort_by(|(a, _), (b, _)| a.cmp(&b));

    // Constraints on the result
    for ((_, new_size), Item { size, fill_factor }) in
        new_sizes.iter().zip(&items)
    {
        assert!(
            new_size >= size,
            "Allocated space must not be smaller than the starting size"
        );
        if *fill_factor == 0u16 {
            assert_eq!(
                new_size, size,
                "Items with a fill factor of zero must keep their original
                size. Original size: {}, new size: {}",
                size, new_size
            );
        }
    }
    assert!(
        new_sizes.iter().map(|i| i.1).sum::<f32>() == available_space,
        "Should use all available space. Space used: {}, available_space: {}",
        new_sizes.iter().map(|i| i.1).sum::<f32>(),
        available_space
    );

    new_sizes.into_iter().map(|(_, size)| size).collect()
}

fn sort_items(items: Vec<Item>) -> Vec<(usize, Item)> {
    let mut items = items.into_iter().enumerate().collect::<Vec<_>>();
    items.sort_by(|a, b| {
        if a.1.fill_factor == 0 {
            return Ordering::Less;
        } else if b.1.fill_factor == 0 {
            return Ordering::Greater;
        }

        b.1.size_over_fill().total_cmp(&a.1.size_over_fill())
    });
    items
}

#[cfg(test)]
mod tests {
    use float_cmp::assert_approx_eq;

    use super::*;

    #[test]
    fn sort_correctly() {
        let item_a = item(1., 1);
        let item_b = item(1., 0);

        assert_eq!(
            sort_items(vec![item_a, item_b]),
            vec![(1, item_b), (0, item_a)]
        );

        let item_a = item(1., 1);
        let item_b = item(1., 0);
        let item_c = item(2., 1);
        let item_d = item(2., 3);
        assert_eq!(
            sort_items(vec![item_a, item_b, item_c, item_d]),
            vec![(1, item_b), (2, item_c), (0, item_a), (3, item_d)]
        );
    }

    #[test]
    fn enough_space_for_relative_fill_factors() {
        assert_eq!(
            allocate_space(vec![item(1., 1), item(1., 1)], 2.),
            vec![1., 1.]
        );
        assert_eq!(
            allocate_space(vec![item(1., 1), item(1., 1)], 4.),
            vec![2., 2.]
        );
        assert_eq!(
            allocate_space(vec![item(1., 1), item(1., 1)], 5.),
            vec![2.5, 2.5]
        );
    }

    #[test]
    fn not_enough_space_for_relative_fill_factors() {
        assert_eq!(
            allocate_space(vec![item(1., 1), item(2., 1)], 3.5),
            vec![1.5, 2.]
        );
    }

    #[test]
    fn unequal_fill_factors() {
        assert_eq!(
            allocate_space(vec![item(1., 1), item(1., 2)], 2.5),
            vec![1., 1.5]
        );
        assert_eq!(
            allocate_space(vec![item(1., 1), item(1., 2)], 3.),
            vec![1., 2.]
        );
    }

    #[test]
    fn fixed_spaces() {
        assert_eq!(
            allocate_space(vec![item(1., 0), item(2., 1), item(2., 1)], 7.),
            vec![1., 3., 3.]
        );
        assert_eq!(
            allocate_space(vec![item(1., 0), item(2., 1), item(2., 2)], 7.),
            vec![1., 2., 4.]
        );
    }

    #[test]
    fn three_variable_sizes() {
        assert_approx_eq!(
            &[f32],
            &allocate_space(vec![item(1., 1), item(1., 2), item(2., 1)], 4.),
            &[1., 1., 2.]
        );
        assert_approx_eq!(
            &[f32],
            &allocate_space(vec![item(1., 1), item(1., 2), item(2., 1)], 4.5),
            &[1., 1.5, 2.]
        );
        assert_approx_eq!(
            &[f32],
            &allocate_space(vec![item(1., 1), item(1., 2), item(2., 1)], 5.),
            &[1., 2., 2.]
        );
        assert_approx_eq!(
            &[f32],
            &allocate_space(vec![item(1., 1), item(1., 2), item(2., 1)], 6.),
            &[4. / 3., 8. / 3., 2.]
        );
        assert_approx_eq!(
            &[f32],
            &allocate_space(vec![item(1., 1), item(1., 2), item(2., 1)], 7.),
            &[5. / 3., 10. / 3., 2.]
        );
        assert_approx_eq!(
            &[f32],
            &allocate_space(vec![item(1., 1), item(1., 2), item(2., 1)], 8.),
            &[2., 4., 2.]
        );
        assert_approx_eq!(
            &[f32],
            &allocate_space(vec![item(1., 1), item(1., 2), item(2., 0)], 7.),
            &[5. / 3., 10. / 3., 2.]
        );
    }
}

内容的提问来源于stack exchange，提问作者avs