Slice a slice as evenly as possible given the maximum length of the sub-slices

Getting Help
1

Hi,

This might be more of a math problem, but since I need to solve in Go, I hope someone could help me out here.

Say you have a sorted slice (of any length)

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

you know want to split it into smaller slices, as evenly as possible, which each sub-slice not exceeding a given length.

Slicing a slice is rather easy to do with:

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
}

However this implies that you know already what would be the value on n so that the lengths of the sub-slice are as evenly as possible.

Just to take make an example if I do

slicing(mySlice, 4)

the result of slicing is [[1 2 3 4] [5 6 7 8] [9 10 11 12] [13 14 15 16] [17 18 19 20] [21]] which would not be correct, since we have 5 slice of length 4 and 1 slice of length 1, while the “more even” slicing should be [[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)

Again, for

slicing(mySlice, 8)

you get [[1 2 3 4 5 6 7 8] [9 10 11 12 13 14 15 16] [17 18 19 20 21]], while the “more even” result would be [[1 2 3 4 5 6 7] [8 9 10 11 12 13 14] [15 16 17 18 19 20 21]] (7+7+7)

for

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)

Any suggestion?

2

Maybe you can round up (math package - math - pkg.go.dev).
For example,

slicing(mySlice, 4)

21 elements and you want to split with max 4.
21 / 4 = 5.25 (you will need 6 slices)

You have to create 6 new slices with “3.5” elements each.
21 / 6 = 3.5
Round up to 4 for the first slice.

Now you have 17 elements and 5 slice left.
17 / 5 = 3.5
Round up to 4 for the second slice.

Now you have 13 elements and 4 slice left.
13 / 4 = 3.5
Round up to 4 for the third slice.

Now you have 9 elements and 3 slice left.
9 / 3 = 3
Round up to 3…

3

21 % 6 will give you 3, the number of slices that must have Math.ceil(21/6)==4 elements, the remaining slices must contain Math.floor(21/6)==3 elements. 3 slices of 4 elements + (6-3) slices of 3 elements = 12 + 9 = 21

4

Check the results with your examples or your code :grinning_face_with_smiling_eyes:

5

In my terseness I was probably not clear. I hope you didn’t think I was correcting what was quoted. 21 / 6 is 3.5 as you said. Instead, I was expanding on that information to optimize the repetitive algorithm that you described. One can use the remainder from 21 /6, which is where 21 % 6 = 3 comes from, to determine directly how many of each of the larger and small subslices are needed.

6

Sure, maybe there are many solutions.
Try it with other cases like a slice with 17 elements and max 8.
I believe that your expected result is (6,6,5)?

7

17 / 8 = 2.5 or 2 with a remainder of 1. (17 %8 == 1)
2 slices
1 (the remainder) of the larger size and 2-1 = 1 of the smaller size
The smaller size is math.Floor(17/2) = 8 (2 → number of slices)
The larger size is math.Ceil(17/2) = 9
8 + 9 = 17

Looks like my max size is off by one. I’ll adjust my algorithm and add the corrected one shortly.

8

Thanks @GonzaSaya & @mje, your replies gave me some hints, and after banging my head a couple of times against the wall I came up with something that works. Not sure it is the most efficient way of doing it, but for it work :slight_smile:

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

9

Nice!
I like how you solve the size variable.

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
}

Can you check this solution?

10

Thanks.
No, something is off.
slicing(mySlice, 4) and slicing(mySlice, 6) do not return the wanted result. I will look at it deeper as soon as I can

11

I had to modify a few things from your solution:

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
}

This now gives the right output.
Probably this is a better alternative to my solution (just one loop, and no intermediate slice allocation), but I do not have the expertise to support this claim, neither I know how to benchmark it properly. If you do, please let me know :slight_smile:

12

Nice!
Question: The only difference with my solution is which slice is bigger than the other. Is that important for your code?

I have only 2 suggestions:

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

to

extra := len(s) % size

AND

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

to

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

So

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

is indeed ok.
Regarding the first suggestion, you should notice that s changes inside the loop, so its length, and that is why extra keeps changes, and needs to be re-evaluate.

Regarding your question, it is kid of important, to be on the safe side the slicing should happen from left to right, rather than from right to left.

I did some benchmarking (hopefully in the right way, still learning) with various lengths of s [10-50-150-250-500] and maxv[7-13-16-19-23], your implementation seems to be slower but less demanding, mine is faster but definitely use more memory.

As an example, mine:

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

yours:

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
14

Great, one last suggestion to improve performace/memory:

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
}
15

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.