go实现对slice的去重并移除元素

使用map来进去重slice里面相同的元素,使用for循环实现对元素的去除,判断是否为IPv4

post thumb
Algorithm
作者 Louis 发表于 2020年9月5日

[TOC]

问题描述:

在写sealos exec的时候, 有个需求是对用户输入的ip和hostname进行操作, 逻辑是将hostname转为ip来操作; 在一个slice里面,要区分两者的话, 就要去重和去去除元素。 因此有了这两个算法。

解决思路

删除元素的算法及对比

// remove is remove b in a []string
func remove(a []string, b string) []string {
	if len(a) == 0 {
		return a
	}
	for i, v := range a {
		if v == b {
			a = append(a[:i], a[i+1:]...)
			return remove(a, b)
			break
		}
	}
	return a
}

// 
func removeByreUse(a []string, b string) []string {
	if len(a) == 0 {
		return a
	}
	res := a[:0]
	for _, v := range a {
		if v != b {
			res = append(res, v)
		}
	}
	return res
}

测试函数

func Test_remove(t *testing.T) {
	type args struct {
		a []string
		b string
	}
	tests := []struct {
		name string
		args args
		want []string
	}{
		{"test01", args{
			a: []string{"123", "245", "345"},
			b: "123",
		}, []string{"245", "345"}},
		{"test02", args{
			a: []string{"123", "245", "345", "123", "245", "345", "123", "245", "345"},
			b: "123",
		}, []string{"245", "345", "245", "345", "245", "345"}},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			if got := remove(tt.args.a, tt.args.b); !reflect.DeepEqual(got, tt.want) {
				t.Errorf("remove() = %v, want %v", got, tt.want)
			}
		})
	}
}

func Test_removeByUse(t *testing.T) {
	type args struct {
		a []string
		b string
	}
	tests := []struct {
		name string
		args args
		want []string
	}{
		{"test01", args{
			a: []string{"123", "245", "345"},
			b: "123",
		}, []string{"245", "345"}},
		{"test02", args{
			a: []string{"123", "245", "345", "123", "245", "345", "123", "245", "345"},
			b: "123",
		}, []string{"245", "345", "245", "345", "245", "345"}},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			if got := removeByreUse(tt.args.a, tt.args.b); !reflect.DeepEqual(got, tt.want) {
				t.Errorf("remove() = %v, want %v", got, tt.want)
			}
		})
	}
}

func Benchmark_remove(b *testing.B) {
	b.ResetTimer()
	origin := []string{"123", "245", "345", "123", "245", "345", "123", "245", "345"}
	for i:=0; i<b.N;i++ {
		remove(origin, "123")
	}
}

func Benchmark_removeByUse(b *testing.B) {
	b.ResetTimer()
	origin := []string{"123", "245", "345", "123", "245", "345", "123", "245", "345"}
	for i:=0; i<b.N;i++ {
		removeByreUse(origin, "123")
	}
}

Benchmark

$ go test -v -bench=. -benchtime=3s -benchmem
=== RUN   Test_remove
=== RUN   Test_remove/test01
=== RUN   Test_remove/test02
--- PASS: Test_remove (0.00s)
    --- PASS: Test_remove/test01 (0.00s)
    --- PASS: Test_remove/test02 (0.00s)
=== RUN   Test_removeByUse
=== RUN   Test_removeByUse/test01
=== RUN   Test_removeByUse/test02
--- PASS: Test_removeByUse (0.00s)
    --- PASS: Test_removeByUse/test01 (0.00s)
    --- PASS: Test_removeByUse/test02 (0.00s)
goos: linux
goarch: amd64
pkg: github.com/fanux/sealos/k8s
Benchmark_remove
Benchmark_remove-4              60721201                54.8 ns/op             0 B/op          0 allocs/op
Benchmark_removeByUse
Benchmark_removeByUse-4         52462827                65.7 ns/op             0 B/op          0 allocs/op
PASS
ok      github.com/fanux/sealos/k8s     6.921s

去重算法

这里是使用了map来存储了相关信息, 利用map的key的不重复性质。

// removeRep is Deduplication []string
func removeRep(a []string) []string {
	if len(a) == 0 {
		return a
	}
	res := make([]string, 0, len(a))
	tmp := map[string]struct{}{}
	for _, v := range a {
		if _, ok := tmp[v]; !ok {
			tmp[v] = struct{}{}
			res = append(res, v)
		}
	}
	return res
}

测试函数

func Test_removeRep(t *testing.T) {
	type args struct {
		a []string
	}
	tests := []struct {
		name string
		args args
		want []string
	}{
		{"test01", args{
			a: []string{"123", "245", "345", "345"},
		}, []string{"123", "245", "345"}},
		{"test02", args{
			a: []string{"123", "245", "345", "123", "245", "345", "123", "245", "345"},
		}, []string{"123", "245", "345"}},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			if got := removeRep(tt.args.a); !reflect.DeepEqual(got, tt.want) {
				t.Errorf("removeRep() = %v, want %v", got, tt.want)
			}
		})
	}
}

Test结果

$ go test -v -bench=. -benchtime=3s -benchmem
=== RUN   Test_removeRep
=== RUN   Test_removeRep/test01
=== RUN   Test_removeRep/test02
--- PASS: Test_removeRep (0.00s)
    --- PASS: Test_removeRep/test01 (0.00s)
    --- PASS: Test_removeRep/test02 (0.00s)
Benchmark_removeRep
Benchmark_removeRep-4           11675400               300 ns/op             144 B/op          1 allocs/op
ok      github.com/fanux/sealos/k8s     10.617s

判断是否为IPv4的算法

判断ipv4是leetcode地址

func IsIpv4(ip string) bool {
	//matched, _ := regexp.MatchString("((2(5[0-5]|[0-4]\\d))|[0-1]?\\d{1,2})(\\.((2(5[0-5]|[0-4]\\d))|[0-1]?\\d{1,2})){3}", ip)

	arr := strings.Split(ip, ".")
	if len(arr) != 4 {
		return false
	}
	for _, v := range arr {
		if v == "" {
			return false
		}
		if len(v) > 1 && v[0] == '0' {
			return false
		}
		num := 0
		for _, c := range v {
			if c >= '0' && c <= '9' {
				num = num*10 + int(c-'0')
			} else {
				return false
			}
		}
		if num > 255 {
			return false
		}
	}
	return true
}

test函数

func TestIsIpv4(t *testing.T) {
	type args struct {
		ip string
	}
	tests := []struct {
		name string
		args args
		want bool
	}{
		{"test01", args{
			"192.168.0.1",
		}, true},
		{"test02", args{
			"192.168.00.1",
		}, false},
		{"test03", args{
			"dev-master",
		}, false},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			if got := IsIpv4(tt.args.ip); got != tt.want {
				t.Errorf("IsIp() = %v, want %v", got, tt.want)
			}
		})
	}
}



func BenchmarkIsIpv4(b *testing.B) {
	b.ResetTimer()
	origin := "192.168.00.1"
	for i:=0; i<b.N;i++ {
		IsIpv4(origin)
	}
}

func BenchmarkIsIpv42(b *testing.B) {
	b.ResetTimer()
	origin := "192.168.00.1"
	for i:=0; i<b.N;i++ {
		_, _ = regexp.MatchString("((2(5[0-5]|[0-4]\\d))|[0-1]?\\d{1,2})(\\.((2(5[0-5]|[0-4]\\d))|[0-1]?\\d{1,2})){3}", origin)
	}
}

func BenchmarkIsIpv43(b *testing.B) {
	b.ResetTimer()
	origin := "192.168.00.1"
	for i:=0; i<b.N;i++ {
		func(ip string) bool {
			strs := strings.Split(ip, ".")
			if len(strs) != 4 {
				return false
			}
			for _, s := range strs {
				if len(s) == 0 || (len(s) > 1 && s[0] == '0') {
					return false
				}
				if s[0] < '0' || s[0] > '9' {
					return false
				}
				n, err := strconv.Atoi(s)
				if err != nil {
					return false
				}
				if n < 0 || n > 255 {
					return false
				}
			}
			return true
		} (origin)
	}
}

Benchmark, 使用正则的速度是最慢的。

=== RUN   TestIsIpv4
=== RUN   TestIsIpv4/test01
=== RUN   TestIsIpv4/test02
=== RUN   TestIsIpv4/test03
--- PASS: TestIsIpv4 (0.00s)
    --- PASS: TestIsIpv4/test01 (0.00s)
    --- PASS: TestIsIpv4/test02 (0.00s)
    --- PASS: TestIsIpv4/test03 (0.00s)
goos: linux
goarch: amd64
pkg: github.com/fanux/sealos/k8s
BenchmarkIsIpv4
BenchmarkIsIpv4-4         	25295156	       142 ns/op	      64 B/op       1 allocs/op
BenchmarkIsIpv42
BenchmarkIsIpv42-4        	  183339	     19405 ns/op	   18450 B/op     100 allocs/op
BenchmarkIsIpv43
BenchmarkIsIpv43-4        	24223809	       147 ns/op	      64 B/op       1 allocs/op
PASS
ok  	github.com/fanux/sealos/k8s	22.042s

参考

上一篇
kubernetes1.18.0部署harborv2.0.2