woodpenker's blog

while(life!=0){study++;}

0%

比较[]int的方法实现

Posted on Edited on In Views: Valine:
Symbols count in article: 10k Reading time ≈ 9 mins.
判断两个int数组是否相等的实现对比, 并依次发散讨论各种位操作技巧和性能和字符串数组比较实现.

判断int数组/string数据相等的方法及位操作讨论

判断int数组相等(数组元素可能重复)

go中我们时常会遇到判断两个int数组是否相同的需求, 自己撸一个方法也很简单, 搞起来:

方法1

思路1: 把两个数组排序以后,对比每个位置上的数据是否相同.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func isSliceEqualSlow(a, b []int) bool {
	if len(a) != len(b) {
		return false
	}
	if a == nil {
		return b == nil
	}
	if b == nil {
		return a == nil
	}
	sort.Ints(a)
	sort.Ints(b)
	for k, v := range a {
		if b[k] != v {
			return false
		}
	}
	return true
}

但是这样每个数组都需要排序, 如果是快排, 也是o(2nlgn+n) ~ o(nlgn)时间复杂度, 有点慢啊

方法2

思路2: 观察发现, 如果两个数组相同 , 那么其中任一个int数据其出现的次数一定是偶数个的, 那么用hash记录一下出现次数, 空间换时间?

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
func isSliceEqualHash(a, b []int) bool {
	if len(a) != len(b) {
		return false
	}
	if a == nil {
		return b == nil
	}
	if b == nil {
		return a == nil
	}
	hashMap := make(map[int]int, len(a))
	var v, tmp int
	var ok bool
	for _, v = range a {
		if tmp, ok = hashMap[v]; ok {
			hashMap[v] = tmp + 1
		} else {
			hashMap[v] = 1
		}
	}
	for _, v = range b {
		if tmp, ok = hashMap[v]; ok {
			hashMap[v] = tmp - 1
		} else {
			return false
		}
	}
	for _, v = range hashMap {
		if v != 0 {
			return false
		}
	}
	return true
}

方法3 (只针对数组内存在重复的情况)

思路3: 如果两个数组相同 , 那么其中任一个int数据其出现的次数一定是偶数个的, 用hash空间消耗也不少. 我们知道一个数与或其自己一定是0,偶数个相同的数与或也一定是0,那么用位操作岂不是很快? 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func isSliceEqual(a, b []int) bool {
	if len(a) != len(b) {
		return false
	}
	if a == nil {
		return b == nil
	}
	if b == nil {
		return a == nil
	}
	var r int
	for _, v := range a {
		r = r ^ v
	}
	for _, v := range b {
		r = r ^ v
	}
	if r != 0 {
		return false
	}
	return true
}

以上实现 针对 [2 2 2] [2 3 3]和[-1 -1 2 2] [0 0 1 1]这样的数组就失效了.

对比测试

  1. 测试正确性:
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
var (
	input = [][][]int{
		[][]int{[]int{1, 2, 3, 4}, []int{1, 2, 3, 4}},
		[][]int{[]int{1, 2, 3}, []int{1, 2, 3, 4}},
		[][]int{[]int{1, 2, 3, 4}, []int{1, 2}},
		[][]int{[]int{1}, []int{1}},
		[][]int{[]int{1}, []int{2}},
		[][]int{[]int{}, []int{1}},
		[][]int{[]int{}, []int{}},
		[][]int{nil, []int{}},
		[][]int{[]int{},nil},
		[][]int{nil, nil},
		[][]int{nil, []int{1}},
		[][]int{[]int{1}, nil},
		[][]int{[]int{1, 2, 2, 2}, []int{1, 2, 2, 2}},
		[][]int{[]int{1, 2, 2}, []int{1, 2, 1, 1}},
		[][]int{[]int{2, 2, 3}, []int{2, 2, 3, 1}},
		[][]int{[]int{2, 2, 3}, []int{2, 2, 3}},
		[][]int{[]int{2, 2, 2}, []int{3, 3, 2}},
		[][]int{[]int{2, 2, 2, 2}, []int{3, 3, 3, 3}},
		[][]int{[]int{2, 2, -1, -1}, []int{1, 1, 0, 0}},
	}
	expect = []bool{
		true,
		false,
		false,
		true,
		false,
		false,
		true,
		false,
		false,
		true,
		false,
		false,
		true,
		false,
		false,
		true,
		false,
		false,
		false,
	}
)

func TestIsSliceEqual(t *testing.T) {
	t.Run("1:", TestIsSliceEqual1)
	t.Run("2:", TestIsSliceEqual2)
	t.Run("3:", TestIsSliceEqual3)
}

func TestIsSliceEqual1(t *testing.T) {
	for k, v := range input {
		if r := isSliceEqualSlow(v[0], v[1]); r != expect[k] {
			t.Errorf("at %d, input: %v, expect: %v, result: %v, not equal", k, v, expect[k], r)
		}
	}
}

func TestIsSliceEqual2(t *testing.T) {
	for k, v := range input {
		if r := isSliceEqualHash(v[0], v[1]); r != expect[k] {
			t.Errorf("at %d, input: %v, expect: %v, result: %v, not equal", k, v, expect[k], r)
		}
	}
}

func TestIsSliceEqual3(t *testing.T) {
	for k, v := range input {
		if r := isSliceEqual(v[0], v[1]); r != expect[k] {
			t.Errorf("at %d, input: %v, expect: %v, result: %v, not equal", k, v, expect[k], r)
		}
	}
}

注:
TestIsSliceEqual3无法通过测试,但是如果是数组元素不重复的测试集则可以通过测试.

  1. benchmarks测试
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
func BenchmarkIsSliceEqual(b *testing.B) {
	b.Run("1:", BenchmarkIsSliceEqual1)
	b.Run("2:", BenchmarkIsSliceEqual2)
	b.Run("3:", BenchmarkIsSliceEqual3)
}

func BenchmarkIsSliceEqual1(b *testing.B) {
	for _, v := range input {
		for i := 0; i < b.N; i++ {
			isSliceEqualSlow(v[0], v[1])
		}
	}
}

func BenchmarkIsSliceEqual2(b *testing.B) {
	for _, v := range input {
		for i := 0; i < b.N; i++ {
			isSliceEqualHash(v[0], v[1])
		}
	}
}

func BenchmarkIsSliceEqual3(b *testing.B) {
	for _, v := range input {
		for i := 0; i < b.N; i++ {
			isSliceEqual(v[0], v[1])
		}
	}
}

测试结果:

1
2
3
4
5
6
7
goos: linux
goarch: amd64
pkg: testcase
BenchmarkIsSliceEqual/1:-8         	  579404	      1818 ns/op	     512 B/op	      16 allocs/op
BenchmarkIsSliceEqual/2:-8         	  502230	      2515 ns/op	     256 B/op	       8 allocs/op
BenchmarkIsSliceEqual/3:-8         	 6719389	       180 ns/op	       0 B/op	       0 allocs/op
PASS

由测试结果可见: 位操作的威力之大! 写代码时常还是需要考虑性能的, 代码=数据结构+算法的确是哲理.同时附上个人理解 业务>代码,哈哈:-).

针对不同的数据场景可以选择不同的比较方式, 如果输入的数组中元素不重复, 那么就使用位操作的方法, 如果重复, 则使用第一种方式, 排序后依次对比.

发散思考1

既然位操作很niubility, 那么不由得想到leetcode上各种位操作解题. 其中有个问题正好来研究研究:
位移操作 比 & 操作 慢吗?

问题由来: counting-bits 以及Number of 1 Bits

对于计算1的个数的实现:

方法1 使用位移操作

1
2
3
4
5
6
7
8
func hammingWeightBitMove(num uint32) int {
	var res int
	for num > 0 {
		res += int(num & 1)
		num = num >> 1
	}
	return res
}

方法2 使用&和减1操作

1
2
3
4
5
6
7
8
func hammingWeightMinusOne(num uint32) int {
	var res int
	for num > 0 {
		res++
		num = (num - 1) & num
	}
	return res
}

测试:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
var (
	input = []uint32{
		0,
		1,
		2,
		4,
		7,
		8,
		12345,
		54321,
		123456789,
		987654321,
		1357924680,
		2468013579,
		2<<31 -1,
	}
	expect = []int{
		0,
		1,
		1,
		1,
		3,
		1,
		6,
		7,
		16,
		17,
		11,
		15,
		32,
	}
)
func TestHammingWeightBitMove(t *testing.T){
	var tmp int
	for k,v:=range input{
		if tmp = hammingWeightBitMove(v); expect[k] != tmp{
			t.Errorf("at index %v, input: %v, expect: %v, get %v",k,v,expect[k],tmp)
		}
	}
}

func TestHammingWeightMinusOne(t *testing.T){
	var tmp int
	for k,v:=range input{
		if tmp = hammingWeightMinusOne(v); expect[k] != tmp{
			t.Errorf("at index %v, input: %v, expect: %v, get %v",k,v,expect[k],tmp)
		}
	}
}

func TestHammingWeight(t *testing.T){
	t.Run("bit move:",TestHammingWeightBitMove)
	t.Run("minus one:",TestHammingWeightMinusOne)
}

func BenchmarkHammingWeightBitMove(b *testing.B){
	for _, v:=range input{
		for i:=0;i<b.N;i++{
			hammingWeightBitMove(v)
		}
	}
}

func BenchmarkHammingWeightMinusOne(b *testing.B){
	for _, v:=range input{
		for i:=0;i<b.N;i++{
			hammingWeightMinusOne(v)
		}
	}
}

func BenchmarkHammingWeight(b *testing.B){
	b.Run("bit move:", BenchmarkHammingWeightBitMove)
	b.Run("minus one:",BenchmarkHammingWeightMinusOne)
}

结果如下, 可见使用减1取与 n = n & (n-1) 确实比位移操作 n = n >> 1 快, 原因是计算机中数据都是使用补码存储的, 操作补码执行位移操作就比执行&操作耗时一些了.

1
2
3
4
5
6
7
goos: linux
goarch: amd64
pkg: testonebits
BenchmarkHammingWeight/bit_move:-8         	 4188075	       293 ns/op	       0 B/op	       0 allocs/op
BenchmarkHammingWeight/minus_one:-8        	 6249888	       196 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	testonebits	2.942s

发散思考2

那么比较两个字符串数组是否相等, 又该如何比较呢?

暂时只想到用hash/sort. 如果你有好的方法, 请不吝赐教.

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
46
47
48
49
50
51
52
func isStrSliceEqualHash(a []string, b []string) bool {
	if len(a) != len(b) {
		return false
	}
	if a == nil {
		return b == nil
	}
	if b == nil {
		return a == nil
	}
	hashMap := make(map[string]int, len(a))
	for _, v := range a {
		if tmp, ok := hashMap[v]; ok {
			hashMap[v] = tmp + 1
		} else {
			hashMap[v] = 1
		}
	}
	for _, v := range b {
		if tmp, ok := hashMap[v]; ok {
			hashMap[v] = tmp - 1
		} else {
			return false
		}
	}
	for _, v := range hashMap {
		if v != 0 {
			return false
		}
	}
	return true
}

func isStrSliceEqualSort(a []string, b []string) bool {
	if len(a) != len(b) {
		return false
	}
	if a == nil {
		return b == nil
	}
	if b == nil {
		return a == nil
	}
	sort.Strings(a)
	sort.Strings(b)
	for k, v := range a {
		if v != b[k] {
			return false
		}
	}
	return true
}

测试数据:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
type D struct {
	input  interface{}
	expect interface{}
}

dataStr = []D{
		D{[][]string{[]string{"1", "2", "abcef", "ef", "abcdefg", "abcdf"}, []string{"1", "2", "abcef", "ef", "abcdefg", "abcdf"}}, true},
		D{[][]string{[]string{"abcdefg", "abcdf"}, []string{"1", "2"}}, false},
		D{[][]string{[]string{"abcdeg", "abcdfg", "abc", ""}, []string{"abcdeg", "abcdfg", "abc"}}, false},
		D{[][]string{[]string{}, []string{"abcdeg", "abcdfg", "abc"}}, false},
		D{[][]string{[]string{}, []string{}}, true},
		D{[][]string{[]string{}, nil}, false},
		D{[][]string{nil, nil}, true},
		D{[][]string{nil, []string{}}, false},
		D{[][]string{nil, []string{"123"}}, false},
		D{[][]string{[]string{"123", "123"}, []string{"123"}}, false},
		D{[][]string{[]string{"123", "123"}, []string{"123", "123"}}, true},
		D{[][]string{[]string{"123", "1234", "1234"}, []string{"123", "123", "1234"}}, false},
		D{[][]string{[]string{"123", "1234", ""}, []string{"123", "1234", "", ""}}, false},
		D{[][]string{[]string{"123", "1234", "1234"}, []string{"123", "1234", "1234", "1234"}}, false},
		D{[][]string{[]string{"123"}, []string{"123"}}, true},
		D{[][]string{[]string{""}, []string{"123"}}, false},
		D{[][]string{[]string{""}, []string{""}}, true},
	}

测试结果:

1
2
3
4
5
6
goos: linux
goarch: amd64
pkg: testonebits
BenchmarkIsStrSliceEqual/hash:-8         	  593346	      2113 ns/op	       0 B/op	       0 allocs/op
BenchmarkIsStrSliceEqual/sort:-8         	  576940	      2014 ns/op	     512 B/op	      16 allocs/op
PASS

两者相差无几.

速记: 位操作的各种技巧

  1. 实现乘除法: >> 1右移1位 等于 除以2, <<1左移1位等于 乘以2, 左右移相比乘除法快一点
  2. 位操作进行两数值交换: a^=b; b^=a; a^=b;, 适合各种比较后交换的排序场景
  3. 判断奇偶: n & (n -1) == 0 或者 n & 1 == 0是偶数 否则 奇数, 比使用 n % 2 效率高, 适合交替执行的条件判断场景
  4. 交换符号将正数变成负数，负数变成正数: ~a + 1 , 整数取反加1，正好变成其对应的负数(补码表示)；负数取反加一，则变为其原码，即正数
  5. 求绝对值: 对于32位数而言, 符号位: flag = a >> 31; 绝对值则是 ((a ^ flag) - flag), 求绝对值公式: (a^(a>>31))-(a>>31), 适合高频求绝对值进行数据判断的场景
  6. 二进制逆序: 对于32位数, 依次以 2 , 4, 6, 8 位作为一组，再进行组内高低位交换
    1
    2
    3
    4
    a = (( a & 0xAAAA) >> 1 | (( a & 0x5555)  << 1)
    a = (( a & 0xCCCC) >> 2  | (( a & 0x3333)  << 2)
    a = (( a & 0xF0F0) >> 4   | (( a & 0x0F0F)  << 4)
    a = (( a & 0xFF00) >> 8   | (( a & 0x00FF)  << 8)
  7. 取两个数的平均数: 使用 ( x&y ) + ((x ^ y) >> 1) 比使用 (x+y)/2效率高. 适合热点代码并且无需考虑 x+y 溢出的问题. 前半部分求得相同的bit,其除2后保持不变,后半部分求不同的bit,右移1位即除以2.加和后即是平均数. 适合高频求平均数场景.