Digest | Golang的3个陷阱, 子数组最大值算法

>  一份2021年03月22日的信息流提炼

### 每天学点Golang

#### 希望早点知道的Golang的3个陷阱

原文: [3 Pitfalls in Golang I Wish I Had Known Earlier](https://betterprogramming.pub/3-pitfalls-in-golang-i-wish-i-knew-3f208a8402a7)

##### 1. for-range 变异性(for-range Mutability)

我们有一个存放结构体实例的通道。我们用范围运算符在通道上迭代。你认为这段代码的输出会是什么？

```go
type A struct {
	id int
}

func main() {
	channel := make(chan A, 5)
	var wg sync.WaitGroup // 等待一个goroutine集合的完成
	
	wg.Add(1)
	go func() {
		defer wg.Done() // WaitGroup计数器减一。
		for a := range channel {
			wg.Add(1) // 计数器加1
			go func() {
				defer wg.Done()
				fmt.Println(a.id)
			}()
		}
	}()
	
	for i := 0; i < 10; i++ {
		channel <- A{id:i}
	}
	close(channel)
	wg.Wait() // 等待WaitGroup计数器为零
}
```

```text
6 \n 6 \n 6 \n 6 \n 6 \n 9 \n 9 \n 9 \n 9 \n 9
```

很奇怪，不是吗？我们希望看到的是1-9的数字（非有序）。
实际上，我们看到的是循环变量的可变性结果。
在每一次迭代中，我们都会得到一个结构体实例来工作。结构体是值类型--它们在每次迭代中被复制到for迭代变量中。这里的关键词是复制。为了避免大的内存打印，不是在每次迭代中创建一个新的变量实例，而是在循环开始时创建一个单一的实例，并在每次迭代中，将数据复制在它上面。
闭包是方程式的另一部分。在Go的闭包（和大多数语言一样）持有闭包中对象的引用（不是复制数据），所以内部的Go例程使用迭代对象的引用，这意味着所有的Go例程都得到对同一个实例的相同引用。

##### 解决方法

首先要意识到这种情况的发生。它与其他语言的行为完全不同（C#中的for-each，JS中的for-of--在这些语言中，循环变量是不可改变的）。

为了避免这个陷阱，在循环的范围内捕获变量，从而自己创建一个新的实例，然后按照自己的意愿使用它。

```go
go func() {
	defer wg.Done()
	for a := range channel {
		wg.Add(1)
		go func(item A) {
			defer wg.Done()
			fmt.Println(item.id)
		}(a) // Capture happens here
	}
}()
```

这里我们使用内部go例程的函数调用来捕获a，有效地复制它。也可以显式复制。

```go
for a := range channel {
	wg.Add(1)
	item := a // Capture happens here
	go func() {
		defer wg.Done()
		fmt.Println(item.id)
	}()
}
```

##### 2. 小心 := (作用域)

:=是相当有用的，它允许我们避免在赋值前声明变量。这实际上是当今许多类型化语言的常见做法（比如C#中的var）。它非常有用，而且能让代码更干净。

但当与Golang中的其他几个行为、作用域和多个返回值相结合时，我们可能会遇到意想不到的行为。

```go
func main() {
	var data []string
	killswitch := os.Getenv("KILLSWITCH")
  
	if killswitch == "" {
		fmt.Println("kill switch is off")
		data, err := getData() // 此时if句中的 data 是一个新变量，当作用域关闭时将被丢弃
		if err != nil {
			panic("ERROR!")
		}
		fmt.Printf("Data was fetched! %d\n", len(data))
	} 	
	
	for _, item := range data {
		fmt.Println(item) // 实际上这里没有数据输出
	}
}

func getData() ([]string, error) {
	// 模拟从一个数据源--比方说一个DB--获取数据
	return []string{"there","are","no","strings","on","me"}, nil
}
```

###### 解决办法

```go
func main() {
	var data []string
	var err error // 声明err以确保使用=代替:=。
  	killswitch := os.Getenv("KILLSWITCH")
	
	if killswitch == "" {
		fmt.Println("kill switch is off")
		data, err = getData() // 这里会赋值作用域外的变量
    ...
```

##### 3. WorkerPool. Captain WorkerPool

下面是代码例。

```go
type A struct {
	id int
}

// 在一个通道上有一个for-range循环
func main() {
	start := time.Now()
	channel := make(chan A, 100)
	var wg sync.WaitGroup
	
	wg.Add(1)
	go func() {
		defer wg.Done()
		for a := range channel {
			wg.Add(1)
			go func(a A) {
				defer wg.Done()
				process(a)
			}(a)
		}
	}()
	
	for i := 0; i < 100; i++ {
		channel <- A{id:i}
	}
	close(channel)
	
	wg.Wait()
	
	elapsed := time.Since(start)
	fmt.Printf("Took %s\n", elapsed)
}

func process(a A) {
	fmt.Printf("Start processing %v\n", a)
	time.Sleep(100 * time.Millisecond) // 每个进程运行100ms
	fmt.Printf("Finish processing %v\n", a)
}
```

如果我们串行处理，比方说10万个项目，上面的代码将运行近三个小时。

利用Go优秀的并发处理能力，为通道中的每个项目调度一个go例程。我们创建的go例程越多，创建的对象就越多，因此内存消耗也就越大。此外，go例程需要CPU的执行时间来进行实际执行，所以我们的核心越少，这些对象就会越多地留在内存中等待执行。在我们的案例中，在128MB内存的Cloud函数中，我们能够在崩溃前处理约100K项。

###### 解决办法: WorkerPool

WorkerPool允许我们管理我们的go例程数量，保持内存打印量低。让我们看看同样的例子与一个worker pool。

```go
	workerPoolSize := 100 
	....
  func() {
    defer wg.Done()
    for i := 0;i < workerPoolSize;i++ {
      wg.Add(1)
      go func() { // Go routine per worker
        defer wg.Done()

for a := range channel {
          process(a)
        }
      }()
    }
  }()
```

把通道看成一个队列，每个worker go例程都是队列的消费者。Go的通道允许多个Go例程监听同一个通道，通道中的每个项目将被处理一次。

WorkerPool让我们对代码的执行有更多的控制。它们让我们具有可预测性，因此我们可以规划和优化我们的代码和平台，以扩展到高吞吐量和大量数据。

我建议在应用程序需要对数据集进行迭代--即使是小数据集--的情况下，一定要使用worker pool。

### 每天学点算法

#### 返回每个长度为k的子数组的最大值

[iamvictorli/Daily-Coding-Problem](iamvictorli/Daily-Coding-Problem) Problem 18

这个问题由Google提出。

例如，给定数组=[10，5，2，7，8，7]，k=3，我们应该得到。[10,7,8,8]，因为：

- 10 = max(10, 5, 2)
- 7 = max(5, 2, 7)
- 8 = max(2, 7, 8)
- 8 = max(7, 8, 7)

在O(n)时间和O(k)空间内完成。

```js
/**
 * 返回每个长度为k的子数组的最大值。
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
function maxSubArrayLengthK(nums, k) {
  if (k <= 0) return [];

const result = [];

const deque = []; // deque存储数字的索引
  for (let i = 0; i < nums.length; i++) {
    // 检查deque是否为空，并删除deque之外的数字
    // 比如[5,4,3,1]k=3，当i=3时之前的Deque是[5,4,3],这时移除5
    console.log("[i]: " + i)
    if (deque.length !== 0 && deque[0] < i - k + 1) {
      console.log("shift deque before: " + deque)
      deque.shift();
      console.log("shift deque after: " + deque)
    }

// 检查deque是否为空，并从deque中取出较小或相等的数字。
    // deque[deque.length - 1] 是最后的index
    while (deque.length !== 0 && nums[i] >= nums[deque[deque.length - 1]]) {
      console.log("pop deque before: " + deque )
      deque.pop();
      console.log("pop deque after: " + deque )
    }

deque.push(i);
    if (i >= k - 1) {
      console.log("nums[deque[0]]: " + nums[deque[0]] + " deque[0]: " + deque[0])
      result.push(nums[deque[0]]);
    }
  }
  return result;
}

export default maxSubArrayLengthK;
```

###### 算法理解

※deque: 双端队列( a double-ended queue)

这里假设循环长度为3的虚拟窗口，移动步长为1。deque则是窗口内最大值位于起始位置的索引数组。每次取index=deque[0]的值存入result数组。

例：arr=[1,2,3,0] k=3

第三次循环时（i=2），window=[1,2,3], MaxArr=[3], deque=[2], arr[deque[0]] = 3

第四次循环时（i=2），window=[2,3,0], MaxArr=[3,0], deque=[2,3], arr[deque[0]] = 3

> Result = [3,3]

例：arr=[9,3,5,7] k=3

第三次循环时（i=2），window=[9,3,5], MaxArr=[9,3,5], deque=[0,1,2], arr[deque[0]] = 9

第四次循环时（i=3），window=[3,5,7], MaxArr=[7], deque=[3], arr[deque[0]] = 7

> Result = [9,7]

### 其他值得阅读

#### 高效人士需要避免的7个习惯

原文：[7 Habits I Avoid to Become Highly Productive](https://medium.com/mind-cafe/7-habits-i-avoid-to-become-highly-productive-98baed2b4b7a)

1. 注重小细节，不注重结果

2. 清晨第一件事就是检查手机

- 高效人士在让一天的需求干扰之前，就会朝着自己的目标采取措施。将早上最旺盛的精神、情感和身体能量集中在他们最优先的事情上--而不是查看Instagram或看新闻。

3. 工作期间分心

4. 工作到筋疲力尽

5. 不分轻重缓急地工作

> "重要的事情很少紧急，紧急的事情很少重要"。
   >
   > “What is important is seldom urgent and what is urgent is seldom important.” ― Dwight D. Eisenhower

6. "找 "时间做事情
7. 未能设定界限
   - 吹嘘每天工作12小时不是生产力的表现，而是界限不清的表现。但高生产力的人对自己的时间设定了界限，不会让较小的事情占用最重要的东西。

生产力是关于你创造和交付多少，而不仅仅是完成繁忙的工作。不要过度关注小细节。

### 一点收获

- "人类的思想，对于大多数人来说，不仅仅是我们进化的神经架构的个体结果，也是我们借用语言中巨大的符号和智力资源的结果。" "Human thought, for the majority, is not simply the individual outcome of our evolved neural architecture, but also the result of our borrowing of the immense symbolic and intellectual resources available in language." -- Neuroanthropology