Golang如何将切片尽可能均匀地分割为指定最大长度的子切片

Golang如何将切片尽可能均匀地分割为指定最大长度的子切片 这可能更像是一个数学问题，但由于我需要用Go语言解决，希望有人能在这里帮助我。

假设你有一个已排序的切片（长度任意）

mySlice := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21}

你现在想把它分割成更小的切片，尽可能均匀，并且每个子切片的长度不超过给定的最大值。

使用以下方法分割切片相当容易：

func slicing(s []int, n int) [][]int {
	var res [][]int
	for {
		if len(s) == 0 {
			break
		}

		if len(s) < n {
			n = len(s)
		}

		res = append(res, s[0:n])
		s = s[n:]
	}

	return res
}

然而，这暗示你已经知道 n 的值，以便子切片的长度尽可能均匀。

举个例子，如果我执行

slicing(mySlice, 4)

slicing 的结果是 [[1 2 3 4] [5 6 7 8] [9 10 11 12] [13 14 15 16] [17 18 19 20] [21]]，这是不正确的，因为我们有5个长度为4的切片和1个长度为1的切片，而“更均匀”的分割应该是 [[1 2 3 4] [5 6 7 8] [9 10 11 12] [13 14 15] [16 17 18] [19 20 21]] (4+4+4+3+3+3)

同样，对于

slicing(mySlice, 8)

你得到 [[1 2 3 4 5 6 7 8] [9 10 11 12 13 14 15 16] [17 18 19 20 21]]，而“更均匀”的结果应该是 [[1 2 3 4 5 6 7] [8 9 10 11 12 13 14] [15 16 17 18 19 20 21]] (7+7+7)

对于

slicing(mySlice, 6)

[[1 2 3 4 5 6] [7 8 9 10 11 12] [13 14 15 16 17 18] [19 20 21]] → [[1 2 3 4 5 6] [7 8 9 10 11] [12 13 14 15 16] [17 18 19 20 21]] (6+5+5+5)

有什么建议吗？


更多关于Golang如何将切片尽可能均匀地分割为指定最大长度的子切片的实战教程也可以访问 https://www.itying.com/category-94-b0.html

14 回复

请用你的示例或代码检查结果 😄

更多关于Golang如何将切片尽可能均匀地分割为指定最大长度的子切片的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


当然，可能有很多解决方案。 尝试用其他情况测试一下，比如一个包含17个元素且最大值为8的切片。 我认为你期望的结果是 (6,6,5) 吗？

谢谢。 不，有些不对劲。 slicing(mySlice, 4) 和 slicing(mySlice, 6) 没有返回期望的结果。我会尽快更深入地研究它。

在我之前的简洁表述中，可能没有说清楚。希望您不要认为我是在纠正引用的内容。正如您所说，21 除以 6 等于 3.5。实际上，我是在此基础上进行扩展，以优化您所描述的重复算法。我们可以利用 21 除以 6 的余数（即 21 % 6 = 3）来直接确定需要多少较大的子切片和多少较小的子切片。

GonzaSaya:

21 / 6 = 3.5

21 % 6 的结果是 3，这意味着必须有 Math.ceil(21/6) == 4 个切片包含 4 个元素，而剩余的切片必须包含 Math.floor(21/6) == 3 个元素。3 个包含 4 个元素的切片 + (6-3) 个包含 3 个元素的切片 = 12 + 9 = 21。

很好！
问题：我的解决方案与你唯一的区别在于哪个切片比另一个更大。这对你的代码重要吗？

我只有两个建议：

extra := len(s) % ((len(s) + maxv - 1) / maxv)

改为

extra := len(s) % size

以及

currentSliceCount = (len(s) / (size - i)) + (extra / extra)

改为

currentSliceCount = (len(s) / (size - i)) + 1

17 / 8 = 2.5 或 2 余 1。（17 % 8 == 1） 2 个切片 1 个（余数）较大尺寸的切片和 2-1 = 1 个较小尺寸的切片 较小尺寸是 math.Floor(17/2) = 8（2 → 切片数量） 较大尺寸是 math.Ceil(17/2) = 9 8 + 9 = 17

看起来我的最大尺寸差了一个。我会调整我的算法，并很快添加修正后的版本。

Go Playground - The Go Programming Language

Go Playground - The Go Programming Language

也许你可以使用向上取整函数（math package - math - pkg.go.dev）。 例如，

slicing(mySlice, 4)

假设有21个元素，你想以最多4个为一组进行分割。 21 / 4 = 5.25（你将需要6个切片）

你必须创建6个新的切片，每个切片包含“3.5”个元素。 21 / 6 = 3.5 对第一个切片向上取整到4。

现在你剩下17个元素和5个切片。 17 / 5 = 3.5 对第二个切片向上取整到4。

现在你剩下13个元素和4个切片。 13 / 4 = 3.5 对第三个切片向上取整到4。

现在你剩下9个元素和3个切片。 9 / 3 = 3 向上取整到3…

我不得不对你的解决方案进行一些修改：

func slicing(s []int, maxv int) [][]int {
	size := (len(s) + maxv - 1) / maxv
	res := make([][]int, size)
	for i := 0; i < size; i++ {
		var currentSliceCount int
		extra := len(s) % ((len(s) + maxv - 1) / maxv)
		if extra > 0 {
			currentSliceCount = (len(s) / (size - i)) + (extra / extra)
		} else {
			currentSliceCount = (len(s) / (size - i))
		}
		res[i] = s[:currentSliceCount]
		s = s[currentSliceCount:]
	}
	return res
}

现在这个函数能给出正确的输出。 这可能比我的解决方案更好（只需一个循环，且没有中间切片分配），但我没有足够的专业知识来支持这个说法，也不知道如何正确地对其进行基准测试。如果你知道怎么做，请告诉我

很好，这是最后一个提升性能/内存的建议：

package main

import (
	"fmt"
)

func main() {
	mySlice := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21}
	out := slicing(mySlice, 4)
	fmt.Println(out)
	out = slicing(mySlice, 8)
	fmt.Println(out)
	out = slicing(mySlice, 6)
	fmt.Println(out)
}

func slicing(s []int, maxv int) [][]int {
	size := (len(s) + maxv - 1) / maxv
	res := make([][]int, size)
	startFrom := 0
	for i := 0; i < size; i++ {
		currentSliceCount := (len(s) - startFrom) / (size - i)
		res[i] = s[startFrom : startFrom+currentSliceCount]
		startFrom += currentSliceCount
	}
	return res
}

感谢 @GonzaSaya 和 @mje，你们的回复给了我一些提示，经过几次碰壁后，我找到了一个可行的方案。不确定这是否是最有效的方法，但它确实能工作 🙂

func slicing(s []int, maxv int) [][]int {
	size := (len(s) + maxv - 1) / maxv
	extra := len(s) % ((len(s) + maxv - 1) / maxv)
	value := len(s) / ((len(s) + maxv - 1) / maxv)

	pres := make([]int, size)
	for i := 0; i < size; i++ {
		pres[i] = value
	}

	for i := 0; i < extra; i++ {
		pres[i] = pres[i] + 1
	}

	res := make([][]int, size)
	for i := 0; i < size; i++ {
		res[i] = s[:pres[i]]
		s = s[pres[i]:]
	}

	return res
}

Go Playground

很好！ 我喜欢你解决 size 变量的方式。

package main

import (
	"fmt"
)

func main() {
	mySlice := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21}
	out := slicing(mySlice, 4)
	fmt.Println(out)
	out = slicing(mySlice, 8)
	fmt.Println(out)
	out = slicing(mySlice, 6)
	fmt.Println(out)
}

func slicing(s []int, maxv int) [][]int {
	size := (len(s) + maxv - 1) / maxv
	res := make([][]int, size)
	for i := 0; i < size; i++ {
		currentSliceCount := len(s) / (size - i)
		res[i] = s[:currentSliceCount]
		s = s[currentSliceCount:]
	}
	return res
}

你能检查一下这个解决方案吗？

Go Playground

Go Playground - The Go Programming Language

所以

currentSliceCount = (len(s) / (size - i)) + 1

确实是可行的。 关于第一个建议，你应该注意到 s 在循环内部会发生变化，因此它的长度也会改变，这就是为什么 extra 会不断变化，并且需要重新评估。

关于你的问题，这有点重要，为了安全起见，切片操作应该从左到右进行，而不是从右到左。

我用不同长度的 s [10-50-150-250-500] 和 maxv [7-13-16-19-23] 做了一些基准测试（希望方法正确，仍在学习中），你的实现似乎较慢但需求较低，我的实现更快但肯定使用了更多内存。

例如，我的实现：

BenchmarkSlicing-12      6856872               172.5 ns/op           256 B/op          2 allocs/op
BenchmarkSlicing-12      6794420               174.5 ns/op           256 B/op          2 allocs/op
BenchmarkSlicing-12      7106743               182.1 ns/op           256 B/op          2 allocs/op
BenchmarkSlicing-12      6989544               176.6 ns/op           256 B/op          2 allocs/op
BenchmarkSlicing-12      6991738               177.7 ns/op           256 B/op          2 allocs/op

你的实现：

BenchmarkSlicing2-12             3969279               309.4 ns/op           192 B/op          1 allocs/op
BenchmarkSlicing2-12             3916411               313.1 ns/op           192 B/op          1 allocs/op
BenchmarkSlicing2-12             3882604               317.2 ns/op           192 B/op          1 allocs/op
BenchmarkSlicing2-12             3988410               313.5 ns/op           192 B/op          1 allocs/op
BenchmarkSlicing2-12             3862108               313.9 ns/op           192 B/op          1 allocs/op

package main

import "fmt"

func splitEvenly(s []int, maxLen int) [][]int {
    if maxLen <= 0 {
        return [][]int{}
    }
    
    n := len(s)
    if n == 0 {
        return [][]int{}
    }
    
    // 计算需要分成多少组
    groups := (n + maxLen - 1) / maxLen  // 向上取整
    
    // 计算每组的基本大小和需要额外增加1的组数
    baseSize := n / groups
    extra := n % groups
    
    result := make([][]int, 0, groups)
    start := 0
    
    for i := 0; i < groups; i++ {
        // 确定当前组的大小
        size := baseSize
        if i < extra {
            size++
        }
        
        // 确保不超过最大长度（理论上不会超过，但保留检查）
        if size > maxLen {
            size = maxLen
        }
        
        // 添加子切片
        end := start + size
        if end > n {
            end = n
        }
        result = append(result, s[start:end])
        start = end
    }
    
    return result
}

func main() {
    mySlice := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21}
    
    fmt.Println("maxLen = 4:")
    result1 := splitEvenly(mySlice, 4)
    for _, sub := range result1 {
        fmt.Println(sub)
    }
    
    fmt.Println("\nmaxLen = 8:")
    result2 := splitEvenly(mySlice, 8)
    for _, sub := range result2 {
        fmt.Println(sub)
    }
    
    fmt.Println("\nmaxLen = 6:")
    result3 := splitEvenly(mySlice, 6)
    for _, sub := range result3 {
        fmt.Println(sub)
    }
}

输出：

maxLen = 4:
[1 2 3 4]
[5 6 7 8]
[9 10 11 12]
[13 14 15]
[16 17 18]
[19 20 21]

maxLen = 8:
[1 2 3 4 5 6 7]
[8 9 10 11 12 13 14]
[15 16 17 18 19 20 21]

maxLen = 6:
[1 2 3 4 5 6]
[7 8 9 10 11]
[12 13 14 15 16]
[17 18 19 20 21]

这个算法的核心逻辑是：

  1. 首先计算需要分成多少组：groups = ceil(n / maxLen)
  2. 计算每组的基本大小：baseSize = n / groups
  3. 计算需要额外增加1的组数：extra = n % groups
  4. 前extra组的大小为baseSize + 1，其余组的大小为baseSize

这样就能保证：

  • 所有子切片长度都不超过maxLen
  • 子切片长度尽可能均匀（相差不超过1）
  • 较大的子切片会出现在前面
回到顶部