Linmin's Data
文章 标签 分类
Linmin's Data

Contents

ARST打卡第164周[164/521]

 included in ARST
   2496 words   5 minutes 

Algorithm

lc710_黑名单中的随机数

思路: 感觉可以直接 index = rand(n - len(blacklist)), 然后构造一个没有blacklist的数组real

返回real[index]

这个方法虽然简单易懂，但是被官方的案例[[1000000000,[640145908]]hack了

被案例hack掉的代码

 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

type Solution struct {
	real     []int
	realSize int
}

func Constructor(n int, blacklist []int) Solution {
	blacklistSize := len(blacklist)
	realSize := n - blacklistSize
	if realSize < 0 {
		panic("realSize is valid. lower than zero.")
	}

	// 好像说这里panic了..[[1000000000,[640145908]]
	// 被官方案例hack了
	tmpSlice := make([]int, 0, realSize)
	// tmpSlice := make([]int, realSize)
	// blacklist = sort.IntSlice(blacklist)
	// IntSlice 只是帮 Slice处理好sort需要的方法，实际的sort还需要调用！
	sortT := sort.IntSlice(blacklist)
	sort.Sort(sortT)
	fmt.Println(sortT)
	j := 0
	for i := 0; i < n; i++ {
		if j < blacklistSize && i == sortT[j] {
			j++
			continue
		}
		tmpSlice = append(tmpSlice, i)
	}

	return Solution{real: tmpSlice, realSize: realSize}
}

func (this *Solution) Pick() int {
	i := rand.Intn(this.realSize)
	return this.real[i]
}

答案: 局部映射，就能解决问题

 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

type Solution struct {
	b2w   map[int]int
	bound int
}

func Constructor(n int, blacklist []int) Solution {
	m := len(blacklist)
	bound := n - m
	black := map[int]bool{}
	for _, b := range blacklist {
		// 只映射黑名单里面值小于 bound 的值
		if b >= bound {
			black[b] = true
		}
	}

	b2w := make(map[int]int, m-len(black))
	w := bound
	for _, b := range blacklist {
		if b < bound {
			for black[w] {
				w++
			}
			b2w[b] = w
			w++
		}
	}
	return Solution{b2w, bound}
}

func (s *Solution) Pick() int {
	x := rand.Intn(s.bound)
	if s.b2w[x] > 0 {
		return s.b2w[x]
	}
	return x
}

Review

A theory of modern Go 2017 06 09 tl;dr: magic is bad; global state is magic → no package level vars; no func init

The single best property of Go is that it is basically non-magical. With very few exceptions, a straight-line reading of Go code leaves no ambiguity about definitions, dependency relationships, or runtime behavior. This makes Go relatively easy to read, which in turn makes it relatively easy to maintain, which is the single highest virtue of industrial programming.

But there are a few ways that magic can creep in. One unfortunately very common way is through the use of global state. Package-global objects can encode state and/or behavior that is hidden from external callers. Code that calls on those globals can have surprising side effects, which subverts the reader’s ability to understand and mentally model the program.

Functions (including methods) are basically the only mechanism that Go has to build abstraction. Consider the following function definition.

1

func NewObject(n int) (*Object, error)

By convention, we expect that functions of the form NewXxx are type constructors. That expectation is validated when we see that the function returns a pointer to an Object, and an error. From this we can deduce that the constructor function may or may not succeed, and if it fails, that we will receive an error telling us why. We observe that the function takes a single int parameter, which we assume controls some aspect or capability of the returned Object. Presumably, there is some constraint on n, which, if not met, will result in an error. But because the function takes no other parameter, we expect it should have no other effect, beyond (hopefully) allocating some memory.

By reading the function signature alone, we are able to make all of these deductions, and build a mental model of this function. This process, applied repeatedly and recursively from the first line of func main, is how we read and understand programs.

Now, consider if this were the body of the function.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func NewObject(n int) (*Object, error) {
	row := dbconn.QueryRow("SELECT ... FROM ... WHERE ...")
	var id string
	if err := row.Scan(&id); err != nil {
		logger.Log("during row scan: %v", err)
		id = "default"
	}
	resource, err := pool.Request(n)
	if err != nil {
		return nil, err
	}
	return &Object{
		id:  id,
		res: resource,
	}, nil
}

The function invokes a package global database/sql.Conn, to make a query against some unspecified database; a package global logger, to output a string of arbitrary format to some unknown location; and a package global pool object of some kind, to request a resource of some kind. All of these operations have side effects that are completely invisible from an inspection of the function signature. There is no way for a caller to predict any of these things will happen, except by reading the function and diving to the definition of all of the globals.

Consider this alternative signature.

1

func NewObject(db *sql.DB, pool *resource.Pool, n int, logger log.Logger) (*Object, error)

By lifting each of the dependencies into the signature as parameters, we allow readers to accurately model the scope and potential behaviors of the function. The caller knows exactly what the function needs to do its work, and can provide them accordingly.

If we’re designing the public API for this package, we can even take it one helpful step further.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// RowQueryer models part of a database/sql.DB.
type RowQueryer interface {
	QueryRow(string, ...interface{}) *sql.Row
}

// Requestor models the requesting side of a resource.Pool.
type Requestor interface {
	Request(n int) (*resource.Value, error)
}

func NewObject(q RowQueryer, r Requestor, n int, logger log.Logger) (*Object, error) {
	// ...
}

By modeling each concrete object as an interface, capturing only the methods we use, we allow callers to swap in alternative implementations. This reduces source-level coupling(耦合) between packages, and enables us to mock out the concrete dependencies in tests. Testing the original version of the code, with concrete package-level globals, involves tedious and error-prone swapping-out of components.

If all of our constructors and functions take their dependencies explicitly, then we no longer have any use for globals. Instead, we can construct all of our database connections, our loggers, our resource pools, in our func main, so that future readers can very clearly map out a component graph. And we can very explicitly pass those dependencies to the components that use them, so that we eliminate the comprehension-subverting magic of globals. Also, observe that if we have no global variables, we have no more use for func init, whose only purpose is to instantiate or mutate package-global state. We can then look at all uses of func init with appropriate suspicion: what is this code doing? Why is it not in func main, where it belongs?

It’s not only possible, but quite easy, and actually extremely refreshing, to write Go programs that are practically free of global state. In my experience, programming in this way is not noticeably slower or more tedious than using global variables to shrink function definitions. On the contrary: when a function signature reliably and completely describes the behavior-scope of the function body, we can reason about, refactor, and maintain code in the large much more efficiently. Go kit has been written in this style since the very beginning, to its great benefit.

— – -

From this, we can develop a theory of modern Go. Based on the words of Dave “Humbug” Cheney, I propose the following guidelines:

  • No package level variables
  • No func init

There are exceptions, of course. But from these rules, the other practices follow naturally.

感想

确实，全局变量虽然可以减少定义时的代码量，但坏处是对库调用者隐藏了太多的东西，而且不利于库调用者理解都是干了啥，并且会在报错的时候，让调用者完全没有办法

而通过接口式的方式暴露出需要的参数，方便调用者可以更加方便的进行参数修改，减少代码耦合性

问题

还是不能使用单例…有人和我一样的疑问，而且是在2年前…现在还没解决，我真的挺无语的

https://forum.golangbridge.org/t/how-to-resolve-those-golang-ci-lint-issue/17168

所以我被迫提问: https://stackoverflow.com/questions/72709336/how-to-use-sync-once-in-golangci-lint-i-got-err-once-is-a-global-variable-goc

尝试以及新问题

1

var _backTask backTask //go:embed test

确实没有全局变量报错，但是出了新问题:(我之前还以为是双斜线必须和文本之间有空格的comment的那个warning，结果是另外的warning) The “embed” package must be imported when using go:embed directives.embed

stackoverflow最终结果

我好不容易回答了一个C/C++的问题，然后获得了1个赞，stackoverflow声誉达到11点，想着再问一个好问题，去达到15点，拥有投票权，结果被两个大佬批了（stackoverflow的veto(否决):This question does not show any research effort; it is unclear or not useful），说我完全可以不用这个全局检测，真的尴尬，然后声誉掉到了7点

vote: 投票 veto: 否决

不删除问题吧，我觉得有些人应该也会犯我的错，用这个留作教训

There are many cases where package-level variables are appropriate and this is one of them. Check to see if there’s a source code comment that you can use to silence the warning from the problem tool. – RedBlue 4 hours ago

You have a lot of options: 1. Do not run golangcli-lint at all. 2. Disable the noglobals rule. 3. Do not use a global. – Volker 4 hours ago

不过还好让我知道了不能全信golangci-lint中集成的一些lint，因为有些lint比较极端，看过了A theory of modern Go，其实也应该知道这不是要禁止所有的global variables…

后续更新: 第二天去看stackoverflow，发现这个提问被upvote了一下，加了10点声誉，然后问题被系统关闭了，但是自己却因为这个upvote获得的10点声誉，达到了17点声誉，从而获得了vote的权利!绝了，没想到啊!然后看到自己以前的answer被别人upvote并且comment说有趣的绕行解决方案，我感觉很开心。以后多玩玩stackoverflow，这是一个好平台，管理得很细致，nice的

Tips

Go语言类型分支（switch判断空接口中变量的类型）

Share

推荐看《黑客与画家》这本书，思考于2001，成文于2003年，翻译于2010年，但是现在看还是会被里面的观点给惊讶到，感觉很多观点放在现在都非常适用，而且在一一验证。并且打破惯性的一些偏见思维。非常好的一本书。

Updated on 2023-12-16
Read Markdown
 ARST
Back | Home