Go神奇的内置数据结构习题题解

背景介绍

环境

  • 操作系统
    • 本机：MacOS 15
    • 远程： 阿里云封装的centos
  • go版本
    • 本机：go1.21.0
    • 远程：go1.14.12
  • IDE：GoLand
  • 辅助：ChatGPT 4o
1
2
3
4
5
6
7
8
9
10
11
12
$ cat /etc/os-release
NAME="Alibaba Cloud Linux"
VERSION="3 (Soaring Falcon)"
ID="alinux"
ID_LIKE="rhel fedora centos anolis"
VERSION_ID="3"
UPDATE_ID="9.1"
PLATFORM_ID="platform:al8"
PRETTY_NAME="Alibaba Cloud Linux 3 (Soaring Falcon)"
ANSI_COLOR="0;31"
HOME_URL="https://www.aliyun.com/"

必做：封装一个数据结构 MyMap

作业内容

封装一个数据结构 MyMap，实现并发安全的 Load，Store，Delete，LoadAndDelete，LoadOrStore 几个 API(禁止使用 sync.Map)，不用考虑性能

参考

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
package main

import "sync"

// 只支持 int 即可。

type MyMap struct {
}

func (m *MyMap) Load(key interface{}) (value interface{}, ok bool) {
	return nil, false
}

func (m *MyMap) Store(key, value interface{}) {
}

func (m *MyMap) Delete(key interface{}) {

}

func (m *MyMap) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool) {
	return nil, false
}

func (m *MyMap) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
	return nil, false
}

func main() {}

实现

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
package main

import "sync"

// 只支持 int 即可。

type MyMap struct {
	data map[int]int
	lock sync.RWMutex
}

func NewMyMap() MyMap {
	return MyMap{
		data: make(map[int]int),
	}
}

func (m *MyMap) Load(key int) (value int, ok bool) {
	m.lock.Lock()
	defer m.lock.Unlock()
	value, ok = m.data[key]
	return
}

func (m *MyMap) Store(key, value int) {
	m.lock.Lock()
	defer m.lock.Unlock()
	m.data[key] = value
}

func (m *MyMap) Delete(key int) {
	m.lock.Lock()
	defer m.lock.Unlock()
	delete(m.data, key)
}

func (m *MyMap) LoadOrStore(key, value int) (actual int, loaded bool) {
	m.lock.Lock()
	defer m.lock.Unlock()
	if actual, loaded = m.data[key]; !loaded {
		m.data[key] = value
		actual = value
	}
	return
}

func (m *MyMap) LoadAndDelete(key int) (value int, loaded bool) {
	m.lock.Lock()
	defer m.lock.Unlock()
	value, loaded = m.data[key]
	if loaded {
		delete(m.data, key)
	}
	return
}

func main() {}

v1优化 by ChatGPT-4o

改进建议

读写锁：在 Load 操作中，使用读锁 RLock 而不是写锁 Lock，这样在读取时不会阻塞其他读取操作。

具体实现

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
package main

import "sync"

// MyMap 只支持 int 类型的键值对
type MyMap struct {
	data map[int]int
	lock sync.RWMutex
}

// NewMyMap 创建一个新的 MyMap 实例
func NewMyMap() MyMap {
	return MyMap{
		data: make(map[int]int),
	}
}

// Load 从 map 中加载值，如果键存在，返回值和 true，否则返回 nil 和 false
func (m *MyMap) Load(key int) (value int, ok bool) {
	m.lock.RLock()
	defer m.lock.RUnlock()
	value, ok = m.data[key]
	return
}

// Store 将键值对存储到 map 中
func (m *MyMap) Store(key, value int) {
	m.lock.Lock()
	defer m.lock.Unlock()
	m.data[key] = value
}

// Delete 从 map 中删除键值对
func (m *MyMap) Delete(key int) {
	m.lock.Lock()
	defer m.lock.Unlock()
	delete(m.data, key)
}

// LoadOrStore 如果键存在，返回已存在的值和 true，否则存储新的键值对并返回新值和 false
func (m *MyMap) LoadOrStore(key, value int) (actual int, loaded bool) {
	m.lock.Lock()
	defer m.lock.Unlock()
	if actual, loaded = m.data[key]; !loaded {
		m.data[key] = value
		actual = value
	}
	return
}

// LoadAndDelete 如果键存在，返回值并删除键值对，否则返回 nil 和 false
func (m *MyMap) LoadAndDelete(key int) (value int, loaded bool) {
	m.lock.Lock()
	defer m.lock.Unlock()
	value, loaded = m.data[key]
	if loaded {
		delete(m.data, key)
	}
	return
}

func main() {}

v2优化 by ChatGPT-4o

改进建议

  • 减少锁的粒度：我们可以尝试进一步优化锁的使用方式，以提高并发性能。例如，可以在 LoadOrStore 和 LoadAndDelete 方法中先尝试使用读锁进行初步检查，再在需要时升级为写锁。
  • 使用sync.Map中的一些优化思想：虽然不能使用 sync.Map，但我们可以参考一些它的优化思想，比如减少写锁的持有时间。

实现

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
package main

import (
	"sync"
)

// MyMap 只支持 int 类型的键值对
type MyMap struct {
	data map[int]int
	lock sync.RWMutex
}

// NewMyMap 创建一个新的 MyMap 实例
func NewMyMap() MyMap {
	return MyMap{
		data: make(map[int]int),
	}
}

// Load 从 map 中加载值，如果键存在，返回值和 true，否则返回 0 和 false
func (m *MyMap) Load(key int) (value int, ok bool) {
	m.lock.RLock()
	defer m.lock.RUnlock()
	value, ok = m.data[key]
	return
}

// Store 将键值对存储到 map 中
func (m *MyMap) Store(key, value int) {
	m.lock.Lock()
	defer m.lock.Unlock()
	m.data[key] = value
}

// Delete 从 map 中删除键值对
func (m *MyMap) Delete(key int) {
	m.lock.Lock()
	defer m.lock.Unlock()
	delete(m.data, key)
}

// LoadOrStore 如果键存在，返回已存在的值和 true，否则存储新的键值对并返回新值和 false
func (m *MyMap) LoadOrStore(key, value int) (actual int, loaded bool) {
	m.lock.RLock()
	actual, loaded = m.data[key]
	m.lock.RUnlock()
	if loaded {
		return actual, true
	}

	m.lock.Lock()
	defer m.lock.Unlock()
	// Double check to avoid race condition
	actual, loaded = m.data[key]
	if !loaded {
		m.data[key] = value
		actual = value
	}
	return actual, loaded
}

// LoadAndDelete 如果键存在，返回值并删除键值对，否则返回 0 和 false
func (m *MyMap) LoadAndDelete(key int) (value int, loaded bool) {
	m.lock.Lock()
	defer m.lock.Unlock()
	value, loaded = m.data[key]
	if loaded {
		delete(m.data, key)
	}
	return
}

func main() {}

选做：比较MyMap与sync.Map性能差异

作业内容

写 benchmark，比较 MyMap 与 sync.Map 的同名函数性能差异(LoadAndDelete 可以不用比较，该函数在 Go 1.15 引入，我们的作业环境是 1.14.12)，输出相应的性能报告(注意，你应该使用 RunParallel)

benchmark编写

两者写法类似

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
package main

import (
	"testing"
)

func BenchmarkMyMap_Load(b *testing.B) {
	m := NewMyMap()
	b.ResetTimer()
	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			m.Load(0)
		}
	})
}

func BenchmarkMyMap_Store(b *testing.B) {
	m := NewMyMap()
	b.ResetTimer()
	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			m.Store(0, 0)
		}
	})
}

func BenchmarkMyMap_Delete(b *testing.B) {
	m := NewMyMap()
	b.ResetTimer()
	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			m.Delete(0)
		}
	})
}

func BenchmarkMyMap_LoadOrStore(b *testing.B) {
	m := NewMyMap()
	b.ResetTimer()
	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			m.LoadOrStore(0, 0)
		}
	})
}

func BenchmarkMyMap_LoadAndDelete(b *testing.B) {
	m := NewMyMap()
	b.ResetTimer()
	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			m.LoadAndDelete(0)
		}
	})
}

benchmark环境

  • 操作系统
    • 本机：MacOS 15
  • go版本
    • 本机：go1.21.0

benchmark运行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
❯ go test -bench .
goos: darwin
goarch: arm64
pkg: windtrack.xyz/go-learn/ch03/mymap
BenchmarkMyMap_Load-10                  10028256               120.7 ns/op
BenchmarkMyMap_Store-10                  9828720               121.5 ns/op
BenchmarkMyMap_Delete-10                10084636               119.7 ns/op
BenchmarkMyMap_LoadOrStore-10           10032361               119.9 ns/op
BenchmarkMyMap_LoadAndDelete-10         10002979               117.4 ns/op
BenchmarkSyncMap_Load-10                832884598                1.508 ns/op
BenchmarkSyncMap_Store-10                7580064               156.4 ns/op
BenchmarkSyncMap_Delete-10              798782074                1.464 ns/op
BenchmarkSyncMap_LoadOrStore-10         376091742                2.874 ns/op
BenchmarkSyncMap_LoadAndDelete-10       832824384                1.445 ns/op
PASS
ok      windtrack.xyz/go-learn/ch03/mymap       15.573s

选做：使用 channel 实现一个 trylock

作业内容

模板 trylock.go

1
2
3
4
5
6
7
8
9
10
11
package main

type MyLock struct {
	// you should have a channel here
}

func (m * MyLock) TryLock() bool {
	return false
}

func main() {}

实现

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
package main

import (
	"fmt"
	"time"
)

type MyLock struct {
	// you should have a channel here
	ch chan struct{}
}

func NewMyLock() *MyLock {
	return &MyLock{
		ch: make(chan struct{}, 1),
	}
}

func (m *MyLock) TryLock() bool {
	select {
	case m.ch <- struct{}{}:
		return true
	default:
		return false
	}
}

func (m *MyLock) Unlock() {
	select {
	case <-m.ch:
	default:
	}
}

func main() {
	lock := NewMyLock()

	// 尝试获取锁
	if lock.TryLock() {
		fmt.Println("Lock acquired in main")
	} else {
		fmt.Println("Unable to acquire lock in main")
	}

	// 启动一个goroutine来尝试获取锁
	go func() {
		if lock.TryLock() {
			fmt.Println("Lock acquired in goroutine")
			lock.Unlock()
		} else {
			fmt.Println("Unable to acquire lock in goroutine")
		}
	}()

	time.Sleep(1 * time.Second)
	lock.Unlock()

	// 再次尝试获取锁
	if lock.TryLock() {
		fmt.Println("Lock re-acquired in main")
		lock.Unlock()
	} else {
		fmt.Println("Unable to re-acquire lock in main")
	}
}

选做：修复deadlock.go的死锁

作业内容

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
package main

import "sync"

type task struct{}

type MyMap struct {
	m   map[int]task
	mux sync.RWMutex
}

func (m *MyMap) finishJob(t task, id int) {
	m.mux.Lock()
	defer m.mux.Unlock()

	// finish task
	delete(m.m, id)
}

func (m *MyMap) DoMyJob(taskID int) {
	m.mux.RLock()
	defer m.mux.RUnlock()

	t := m.m[taskID]

	m.finishJob(t, taskID)
}

func main() {
	var taskMap = &MyMap{
		m: map[int]task{},
	}
	taskMap.DoMyJob(1)
}

运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
fatal error: all goroutines are asleep - deadlock!

goroutine 1 [sync.RWMutex.Lock]:
sync.runtime_SemacquireRWMutex(0x14000044698?, 0x8c?, 0x1400009c000?)
        /Users/windtrack/.gvm/gos/go1.21/src/runtime/sema.go:87 +0x28
sync.(*RWMutex).Lock(0x140000446c8?)
        /Users/windtrack/.gvm/gos/go1.21/src/sync/rwmutex.go:152 +0xf8
main.(*MyMap).finishJob(0x1400009a000, {}, 0x0?)
        /Users/windtrack/go/src/windtrack.xyz/go-learn/ch03/deadlock/deadlock.go:13 +0x3c
main.(*MyMap).DoMyJob(0x1400009a000, 0x104566780?)
        /Users/windtrack/go/src/windtrack.xyz/go-learn/ch03/deadlock/deadlock.go:26 +0xcc
main.main()
        /Users/windtrack/go/src/windtrack.xyz/go-learn/ch03/deadlock/deadlock.go:33 +0x64

Process finished with the exit code 2

deadlock分析

程序在DoMyJob中获取了读锁，而finishJob尝试去获取写锁，但写锁无法在持有读锁时获取

deadlock修复

提前释放读锁即可

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
package main

import "sync"

type task struct{}

type MyMap struct {
	m   map[int]task
	mux sync.RWMutex
}

func (m *MyMap) finishJob(t task, id int) {
	m.mux.Lock()
	defer m.mux.Unlock()

	// finish task
	delete(m.m, id)
}

func (m *MyMap) DoMyJob(taskID int) {
	m.mux.RLock()

	t := m.m[taskID]
	m.mux.RUnlock()

	m.finishJob(t, taskID)
}

func main() {
	var taskMap = &MyMap{
		m: map[int]task{},
	}
	taskMap.DoMyJob(1)
}

选做：实现MyContext

作业内容

在 context 学习过程中，我们知道，在子节点中 WithValue 的数据，父节点是查不到的。请实现一个 MyContext，其 WithValue 方法赋值的 k，v 在父节点中也可以查得到。模板：mycontext.go。

实现

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
package main

import (
	"context"
	"fmt"
	"reflect"
	"sync"
)

type MyContext struct {
	data map[interface{}]interface{}
	ct   context.Context
	l    sync.RWMutex
}

func (m *MyContext) WithValue(parent context.Context, key, val interface{}) *MyContext {
	if parent == nil {
		panic("cannot create context from nil parent")
	}
	if key == nil {
		panic("nil key")
	}
	if !reflect.TypeOf(key).Comparable() {
		panic("key is not comparable")
	}
	m.l.Lock()
	defer m.l.Unlock()
	m.data[key] = val
	return &MyContext{
		ct:   parent,
		data: m.data,
	}
}

func (m *MyContext) Value(key interface{}) interface{} {
	m.l.RLock()
	defer m.l.RUnlock()
	if val, ok := m.data[key]; ok {
		return val
	}
	return m.ct.Value(key)
}

func NewMyContext(parent context.Context) *MyContext {
	if parent == nil {
		panic("cannot create context from nil parent")
	}
	return &MyContext{
		data: make(map[interface{}]interface{}),
		ct:   parent,
	}
}

func main() {
	parent := context.Background()
	myCtx := NewMyContext(parent)

	childCtx := myCtx.WithValue(parent, "key", "value")

	val := myCtx.Value("key")
	if val != "value" {
		panic("unexpected value")
	}

	fmt.Println("Value in parent context:", val)

	childVal := childCtx.Value("key")
	if childVal != "value" {
		panic("unexpected value in child context")
	}

	fmt.Println("Value in child context:", childVal)
}

选做++：实现，或封装社区的 timewheel

作业内容

使用 benchmark 或 pprof 比较大量 timer 存活时，内置 timer 和 timewheel 的性能差异。不要求提交代码，只需要性能对比报告 markdown

赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

Python后端开发，业余前端，自学CV中