Tip-Review-Algorithm 第三期

Tip

Amazon EC2 Mac Instances「AWS 支持macOS系统实例了」

AWS官网介绍:Develop, build, test, and sign Apple apps on Amazon EC2

AWS支持EC2 Mac实例,表示以后开发人员可以随时随地通过云端访问macOS环境。目前是由Mac Mini搭建的,支持Mojave10.14,Catalina10.15系统,将推出Big Sur11.0系统。用户指南在这里。

之前还有另外一家macOS云解决方案供应商,MacStadium

关于云端macOS持续集成的选择,PSPDF有一篇文章:Managing macOS Hardware: Virtualization or Bare Metal?

Review

What went wrong with the libdispatch. A tale of caution for the future of concurrency

摩尔定律失效的时代,CPU主频提升困难,芯片制造商更倾向于在同一块芯片上安装更多内核。开发人员需要通过多线程利用多核的优势,同时Apple 发布了libdispatch即GCD,大大降低了使用多线程的难度。但是作者tclementdev提出来,正是这种便捷,会引起一些糟糕的事情:

  1. 线程爆炸,线程数目远远大于机器内核数目。
  2. 异步调用导致的代码难以阅读和Bug调试。
  3. 将一些小任务进行异步化,派发到队列中,会造成资源浪费。

其实作者想强调的是,当多线程使用太方便时,程序员不再认真思考创建线程是否有意义,不再仔细考虑程序设计。实际上,需要仔细考虑队列,节制地使用异步操作,将线程的数量减少到一个合理的数目。

文章里提到了在Swift邮件列表中有libdispatch维护者与swift编译器工程师的讨论,(page 1, page 2) ,有一些libdispatch的使用建议和解释。作者总结在gist上,libdispatch-efficiency-tips.md

Algorithm

盛最多水的容器

描述:

给你 n 个非负整数 a1,a2,...,a``n,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai)(i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

思路:

双指针。

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
/*
* @lc app=leetcode.cn id=11 lang=cpp
*
* [11] 盛最多水的容器
*/

// @lc code=start
class Solution {
public:
int maxArea(vector<int>& height) {
int i = 0, j = height.size()-1;
int max_res = 0;
while (i<j)
{
int tmp = min(height[i], height[j]) * (j-i);
if (tmp > max_res)
{
max_res = tmp;
}
// 双指针,容积由较小值和长度决定。考虑到移动较大值是不会增加容积,故移动较小值来减小问题边界
if (height[i]<height[j])
{
i++;
} else {
j--;
}
}
return max_res;
}
};
// @lc code=end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// swift
class Solution {
func maxArea(_ height: [Int]) -> Int {
var i=0;
var j=height.count-1;
var max_res = 0;
while i<j {
let tmp = min(height[i], height[j]) * (j-i);
if tmp>max_res {
max_res = tmp;
}
if height[i]<height[j] {
i+=1;
}else {
j-=1;
}
}
return max_res;
}
}