GolangNote

Golang笔记

Golang Slice 生成组合的两种高效方法及性能比较

Permalink

Go 语言生成一个 Slice 指定个数的组合有多种实现方法,这里介绍两种性能比较好的。

上图是性能比较结果,前两种是指定取组合长度,第一种比较快,第二种代码简单,性能稍差一点,第三种是全组合。

第一种的算法按 Python 的 itertools 算法实现,速度确实很快。

Go: golang Port of some Python's itertools
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
func Combinations(iterable []string, r int) (rt [][]string) {
	pool := iterable
	n := len(pool)

	if r > n {
		return
	}

	indices := make([]int, r)
	for i := range indices {
		indices[i] = i
	}

	result := make([]string, r)
	for i, el := range indices {
		result[i] = pool[el]
	}
	s2 := make([]string, r)
	copy(s2, result)
	rt = append(rt, s2)

	for {
		i := r - 1
		for ; i >= 0 && indices[i] == i+n-r; i -= 1 {
		}

		if i < 0 {
			return
		}

		indices[i] += 1
		for j := i + 1; j < r; j += 1 {
			indices[j] = indices[j-1] + 1
		}

		for ; i < len(indices); i += 1 {
			result[i] = pool[indices[i]]
		}
		s2 = make([]string, r)
		copy(s2, result)
		rt = append(rt, s2)
	}

}

第二种代码简单

Go: Combinations
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func Combinations2(set []string, n int) (subsets [][]string) {
	length := uint(len(set))

	if n > len(set) {
		n = len(set)
	}

	// Go through all possible combinations of objects
	// from 1 (only first object in subset) to 2^length (all objects in subset)
	for subsetBits := 1; subsetBits < (1 << length); subsetBits++ {
		if n > 0 && bits.OnesCount(uint(subsetBits)) != n {
			continue
		}

		var subset []string

		for object := uint(0); object < length; object++ {
			// checks if object is contained in subset
			// by checking if bit 'object' is set in subsetBits
			if (subsetBits>>object)&1 == 1 {
				// add object to subset
				subset = append(subset, set[object])
			}
		}
		// add subset to subsets
		subsets = append(subsets, subset)
	}
	return subsets
}

顺带测试全组合

Go: 全组合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func All(set []string) (subsets [][]string) {
	length := uint(len(set))

	// Go through all possible combinations of objects
	// from 1 (only first object in subset) to 2^length (all objects in subset)
	for subsetBits := 1; subsetBits < (1 << length); subsetBits++ {
		var subset []string

		for object := uint(0); object < length; object++ {
			// checks if object is contained in subset
			// by checking if bit 'object' is set in subsetBits
			if (subsetBits>>object)&1 == 1 {
				// add object to subset
				subset = append(subset, set[object])
			}
		}
		// add subset to subsets
		subsets = append(subsets, subset)
	}
	return subsets
}

测试结果

plaintext: 测试结果
1
2
3
4
5
6
7
8
9
10
11
goos: darwin
goarch: amd64
cpu: Intel(R) Core(TM) i7-4870HQ CPU @ 2.50GHz
Benchmark_Combinations
Benchmark_Combinations-8    	  740014	      1519 ns/op	    1296 B/op	      17 allocs/op
Benchmark_Combinations2
Benchmark_Combinations2-8   	  421512	      2895 ns/op	    1864 B/op	      35 allocs/op
Benchmark_All
Benchmark_All-8             	  183870	      6249 ns/op	    3992 B/op	      80 allocs/op
PASS
ok  	command-line-arguments	3.615s

参考

本文网址: https://golangnote.com/topic/301.html 转摘请注明来源

Related articles

Golang 生成防识别的图片验证码

验证码 captcha 是对抗密码强力破解、垃圾信息的有效方式,一般用于用户注册、登录,当检测到频繁发帖时也会启用验证码。下面介绍用golang 生成防机器识别的图片验证码。...

Write a Comment to "Golang Slice 生成组合的两种高效方法及性能比较"

Submit Comment Login
Based on Golang + fastHTTP + sdb | go1.22.3 Processed in 3ms