Author: 逸飞

Web Cron 市场调研

因为实现了 sche 的语法,感觉完爆 cron,所以调研了一下 web cron,不过似乎市场不大。这个算是 unboundlling AWS 的一种,但是功能太简单了,直接用 AWS 也不复杂。而且竞争对手太多了。。

Heroku 真的是个很有意思的服务,解决了很多痛点,但是项目还是挺大的。不过值得思考的是,为什么 Heroku 做起来了,而 Google App Engine 凉了?是因为 GAE 超前时代太多了吗?

Sche.io 还没有被注册,可惜 99 刀太贵了,不然先注册一把。

  1. Indie Hacker 上有人有类似的想法。https://www.indiehackers.com/forum/cloud-based-cron-job-should-i-built-it-c46f58e66f
  2. Hacker News 上的评论大多是正面的,但是也不知道会不会付费。https://news.ycombinator.com/item?id=17346616
  3. 直接用 aws lambda 就行了。。https://gist.github.com/milesw/83332215df29fa25239712cd1ba273d9
  4. 这个 Cronhub 号称挣钱了。但是没看出哪里有意思或者可复制来。https://www.indiehackers.com/@tigran/cronhub-2nd-month-report-9e474add23

提到的一些痛点:

  1. 如何做好授权?
  2. 不一定所有服务都暴露了外部 http 接口
  3. 对于长时间执行的任务怎么办
  4. 能否直接 ssh 上去执行任务呢?
  5. 能否提供 API 让用户通过代码上传任务

如果真要做的话,应该把监控、日志统计等都做了。做到比 AWS、Azure、Heroku 的调度功能更加方便。

比较有意思的思考

网站的监控是一个挺大的领域

  1. 包括网站的功能监控,比如 Pingdom,HyperPing,PagerDuty,DataDog 等等
  2. 网站的用户监控,Google Analytics 和一系列的工具

关于 Heroku vs App Engine

这篇文章说的不错。Google 的第一个问题在于没有把用户放在心里,而是在 Demo 甚至 Show off 自己的 Infra。比如说:

  • 在 GAE 上用户需要大幅度修改自己的代码才能运行
  • 没有 SQL,只能用 Google 自己的 BigTable
  • 不支持最最最流行的 PHP

等等。。

而在 Heroku 上,用户可以随意使用已经很熟悉的 Postgres/Mongo/Redis/MySQL 等等数据库,也就是说迁移到 Heroku 几乎不费任何代价,而且还不用关心负载平衡、监控等运维细节。

另一方面,Heroku 最开始支持的是 Ruby on Rails,而这个社区在当时是非常活跃,而且乐于传教的。

最后一点,Google App Engine 甚至比 Heroku 贵不少。。说好的大厂不差钱呢?

sche – 一种人类能够看懂的 cron 语法

在 Linux 系统上,我们一般使用 cron 来设置定时任务,然而 cron 的语法还是有些佶屈聱牙的,几乎每次要修改的时候都需要查一下文档才知道什么意思,以至于有 crontab.guru 这种网站专门来解释 cron 的语法。

想象一下,能不能有一种让人一眼就能看懂的语法来表达周期性的调度操作呢?比如说这样:

every 10 minutes         , curl apple.com
every hour               , echo 'time to take some coffee'
every day at 10:30       , eat
every 5 to 10 minutes    , firefox http://news.ycombinator.com
every monday             , say 'Good week'
every wednesday at 13:15 , rm -rf /
every minute at :17      , ping apple.com
every 90 minutes         , echo 'time to stand up'

这样的配置文件是不是很容易懂呢?如果要写成 crontab 的格式大概是这样的:

*/10 * * * *    curl apple.com
0 * * * *       echo 'time to take some coffee'
30 10 * * *     eat
*/7 * * * *     firefox http://news.ycombinator.com  # 实际上是不对的,因为 cron 没法随机
0 0 * * MON     say 'Good week'
15 13 * * WED   rm -rf /
# every minute at :17  无法实现,因为 cron 中没有秒
0 0-21/3 * * *  echo 'time to stand up'  # 需要两条命令来完成每隔 90 分钟的操作
30 1-22/3 * * * echo 'time to stand up'

可以很明显看出,cron 的语法可读性还是差一些的,关键是维护起来更是像读天书一样。幸运的是,我在周末刚刚做了一个小工具,虽然还比较粗糙,但是也已经可以解析上面这种可读性比较好的语法。下面简单介绍一下如何使用:

介绍 sche

sche 是一个 Python 程序,所以可以使用 pip 直接安装:

pip install sche

安装之后,就会得到一个 sche 命令,帮助文件如下:

-> % sche -h
usage: sche [-h] [-f FILE] [-t]

A simple command like `cron`, but more human friendly.

The default configuration file is /etc/schetab, syntax goes like:

    # (optional) set time zone first
    timezone = +0800

    # line starts with # is a comment
    every 60 minutes, echo "wubba lubba dub dub"

    # backup database every day at midnight
    every day at 00:00, mysqldump -u backup

    # redirect logs so you can see them
    every minute, do_some_magic >> /some/output/file 2>&1

optional arguments:
  -h, --help            show this help message and exit
  -f FILE, --file FILE  configuration file to use
  -t, --test            test configuration and exit

我们只需要把需要执行的命令放到 /etc/schetab 文件下就好了,这里显然是在致敬 /etc/crontab。比如说:

-> % cat /etc/schetab
timzone = +0800
every 5 seconds, echo "wubba lubba dub dub"
every 10 seconds, date

-> % sche
wubba lubba dub dub
Tue Sep  1 22:15:01 CST 2020
wubba lubba dub dub
wubba lubba dub dub
Tue Sep  1 22:15:11 CST 2020
wubba lubba dub dub
wubba lubba dub dub
Tue Sep  1 22:15:21 CST 2020
wubba lubba dub dub

如何让 sche 像 cron 一样作为一个守护进程呢?秉承 Unix 一个命令只做一件事的哲学,sche 本身显然是不提供这个功能的,可以使用 systemd 实现,几行配置写个 unit 文件就搞定了。

sche 的来源

sche 是 schedule — 另一个 Python 库的一个 fork, schedule 支持这样的 Python 语句:

schedule.every(10).minutes.do(job)
schedule.every().hour.do(job)
schedule.every().day.at("10:30").do(job)
schedule.every().monday.do(job)
schedule.every().wednesday.at("13:15").do(job)
schedule.every().minute.at(":17").do(job)

然而我的需求是把时间配置独立出来,能够像 cron 一样存到一个文本文件里,而不是写成 Python 代码,于是提了一个 PR,增加了 when 这个方法来解析表达式。同时我还强烈需求时区支持,然而原版的 schedule 也不支持。所以就创建了一个 fork.

sche.when("every wednesday at 13:15").do(job)
sche.timezone("+0800").every().day.at("00:00").do(job)

最后,原生的 cron 命令实际上(至少我)已经极少用了,然而 crontab 的语法流传还是非常广的,在所有需要定时任务的地方,几乎都能看到 cron 的身影,比如说 Kubernetes job 等等,如果能够使用一种让正常人能随时看懂的语法,感觉还是很有意义的。

参考

  1. https://schedule.readthedocs.io/en/stable/
  2. https://crontab.guru/
  3. https://stackoverflow.com/q/247626/1061155

Python 3 中的 dataclass

在 Python 中,如果要为一个类添加一些数据成员的话,需要做的事情还挺多,比如说编写 __init__,
__str__ 这些函数,代码都是重复的,没啥意义。在 Python 3.7 中,终于添加了一个语法糖,叫做
dataclass. 下面我们就来看一下吧~

# 注意!包名叫 dataclasses, 多了个 es
from dataclasses import dataclass

@dataclass
class InventoryItem:
    """Class for keeping track of an item in inventory."""
    name: str
    unit_price: float
    quantity_on_hand: int = 0

    def total_cost(self) -> float:
        return self.unit_price * self.quantity_on_hand

上面的代码就相当于以前的:

def __init__(self, name: str, unit_price: float, quantity_on_hand: int=0):
    self.name = name
    self.unit_price = unit_price
    self.quantity_on_hand = quantity_on_hand

def __repr__(self):
    ...

def __eq__(self):
    ...

...

我们知道,在 Python 的默认参数中,使用 mutable(可变) 的对象是一种常见的坑,在 dataclass 中当然也存在
了,还好标准库中给我们提供了一个方法。

# 会报错
@dataclass
class Request:
    headers: dict = {}

# 相当于
class Request:
    def __init__(self, headers={}):
        self.headers = headers


# 正确的写法
from dataclasses import field

@dataclass
class Request:
    headers: dict = field(default_factory=dict)

字典这种类型是比较容易想起来不能直接做参数的,比较坑的是对于其他的自定义对象,Python 解释器并不会提
示有问题,比如说这样:

# 千万别这么做
@dataclass
class Request:
    headers: Headers = Headers()

这时候坑爹的事情就发生了,每次创建新的 Request 对象引用的都是同一个 Headers 对象,也就是在声明这个类
的同时产生的这个 Headers 对象!原因也很简单,就像是上面的 dict 一样,这个 Headers 并不是在 init 函数
中,所以只会产生一次。所以,需要牢记的是:dataclass 中的所有对象默认值就相当于函数的默认参数,永远不
要传递一个 mutable 就好了。

# 上面的例子相当于
class Request:
    def __init__(self, headers=Headers()):
        self.headers = headers

# 正确的做法
@dataclass
class Request:
    headers: Headers = field(default_factory=Headers)

dataclasses 模块中还提供了 asdict 方法,这样就可以方便地转换为 json 对象啦。

from dataclasses import asdict


@dataclass
class Request:
    url: str = ""
    method: str = ""

req = asdict(Request())

参考资料

  1. https://docs.python.org/3/library/dataclasses.html

创业公司应该选择无聊的技术

感想

昨天又重新读了一下 Boring Technology 和 Boring Company 两篇文章,得出对于创业公司技术选型的一些想法。

  1. 创业必须是老鸟,老鸟已经知道了足够的技术,有足够的技术可供选择,才能有全局思考选择最合适的少数几个技术。
  2. 什么是 Boring Technology?Boring 也不能无脑,Oracle 和 MySQL 都已经足够成熟且无聊了,但是 Oracle 显然不是未来的方向,所以我们肯定要选择 MySQL。
  3. 对于新手来说,显然是不适合创业的。别扯啥比尔盖茨和扎克博格的例子,人家高中水平比不少五年工作经验的人都高。新手还需要足够的时间了解足够的技术知识。就像文中说的一样,每个人的精力是有限的,创业不能把精力都放在技术选型上,更多地是实现商业逻辑。
  4. 作为一个技术人员,或者说技术公司,还是应该固定地花费时间去学习新技术或者更基础的底层技术,比如 20%时间、串讲或者黑客马拉松。否则的话,因为对于技术的追求被压抑了,可能反倒倾向于在生产环境中引入各种 fancy 的新技术而引起问题。
  5. 总体来说,还是哪句话:不要因为手里拿着锤子就看哪里都是钉子。但是工具箱里一定要有锤子,不然看到钉子了你就傻眼了。锤子应该放在工具箱里,需要的时候用一下,而不是一直攥在手里。
  6. 运维团队的一个核心 KPI 就是组织开发人员增加一些功能重复的组件,比如 Python vs Ruby, Redis vs Memcached, Influxdb vs Prometheus.
  7. build from what you really need

原文的一些摘抄

  • 很重要的一步是认识到注意力是非常宝贵的,人类对于细节的把控粒度是有限的。
  • 我的朋友 Andrew 每天穿着同一个牌子的黑衬衫。他认为如果他节省下选择衣服穿的脑力,就可以存起来用到别的事情上。
  • 我们应该选择能够覆盖我们问题的最小工具集,然后把工作搞定。
  • 增加一项技术是容易的,但是和它共存很难
  • 我可以随时 brew install 一个数据库,并且开始往里写数据,但是要在生产环境运行数据库就是另一个技能了。
  • 如果你给不同的团队做出局部选择的权力,那么在你是在全局性地伤害自己。
  • 当你使用多个相同功能的服务的时候,你不只要付出多一分的维护精力,还要失去大家使用同一个平台的好处。
  • 技术对你的公司有全局影响,不应该交给单独的工程师们自己决定。
  • 如果你觉得你用现有的工具无法实现某个新功能,那么一般是你想的不够用力
  • 你可以把你觉得很难实现的功能写下来,然后就就会发现并没有那么难,至少比维护一个新的工具要简单。
  • 当然你有可能得到相反的结论,使用一个新的工具也许是值得的。
  • 如果你正在添加一项冗余的技术,那么你应该尝试着替换掉旧的工具,而不是维护两套。也应该准备着如果新的工具不好用的话,要回滚。
  • 优先做能够让你集中精力到真正重要的事情上的事情。
  • 全局思考你要做什么,选择一组最小的工具能够解决你所有问题的。
  • 有意思的是你选择的任何工具可能都不是”正确的工具”. 但是他们组合起来依然可能是正确的选择。

熟练使用你选择的工具非常重要。你应该往马斯洛需求模型的上面爬,关心大局。你不应该每天都在讨论要使用那个数据库,而应该是跟高阶的业务问题。如果你真的真么做的话,问问自己是不是哪里搞错了。

我们生活在一个创建公司的美妙年代,有那么多直接可用的工具和服务可以让我们解决时间和金钱并提高生产力。从来没有像现在这样,一个小团队(甚至一个人)可以使用简单无聊的技术来做出一点对世界有用的工具来。

大多数时候,构建和交付的最大障碍来自想得过多。如果这样怎么办,那样怎么办。天啊,你根本不重要。每个人都很忙的。没人关心你和你创造的东西,知道你证明你值得别人的注意力。即使你把第一次产品发布搞砸了,几乎不会有人注意到。Think big, start small, act fast. 使用无聊的技术来做一些简单的东西(甚至很丑), 只要你解决了实际问题。

你的过度思考就是我的优势所在。

最后

Boring technology 的思路和 Facebook 工程师的文章 [4] 看似是冲突的。一个强调使用各种”无聊的”的技术,而另一个则是炫耀各种高级的基础设施。其实两个并不是矛盾的,反倒是统一的。无聊的技术才是经过大规模检验的基础设施,而其他高级设施要按照自己的思路,而不是看到乱七八糟的东西为了用就用。

Happiness comes from shipping stuff. 快乐源自交付。

参考

  1. Choose Boring Technology
  2. The Boring Technology Behind a One Person Company
  3. 引入开源库的取舍
  4. FB 海归国内高管:谈谈 infra、代码管理、微服务、测试系统,以及技术人员海归能做什么

疫苗概念股研究

前期买过未名医药,但是感觉和和科兴的股权有问题就没有拿着,错过了翻倍的机会。

山东药玻早就在关注,但是没有下手,现在收益率也没过少。没有买更加小盘的正川科技,错过了翻倍机会

现在开始炒作预充针技术,因为据观察现有的疫苗都是采用预充针技术,也就是跳过了玻璃瓶的需求。

吹管充一体化

  • 人福医药
  • 东富龙
  • 楚天科技

玻璃瓶

需要中硼硅还是低硼硅玻璃?反正是特殊玻璃

  • 正川科技
  • 山东药玻

预充针材料

就是直接把药罐在注射器里面,需要特殊塑料

  • 阿科力
  • 康德莱(注射器厂商)

冷链运输

疫苗运输需要特殊温度,要求还挺严格的。

  • 澳柯玛
  • 九州通
  • 英特医疗

参考资料

  1. https://xueqiu.com/3171998589/153753646
  2. https://finance.sina.cn/stock/relnews/dongmiqa/2020-07-09/detail-iircuyvk2933260.d.html?vt=4

刷 LeetCode 的经验

最近断断续续面试了三个月,也拿了一些大厂(美团百度阿里)的 offer, 分享下刷题经验

  • 一定要使用自己最擅长的语言,不要想其他的,不要引入额外的复杂度;
  • 复习基础算法,如排序,二分查找,树的遍历等,同时做一些基础题;
  • 简单的递归,比如树的一些题目,是最容易引导你进入刷题状态的;
  • 递归是几乎所有有技巧的题目的基础,栈是递归、树是递归、回溯也是递归、动归更是递归;
  • 除了递归之外,剩下的基本是考察基础操作的题目,比如螺旋打印矩阵等等,一定要注意细节;
  • 每道题 10 分钟完全没思路就看答案;
  • 如果连续有 5 道题目看答案了,去补习知识,不要再做了;
  • 代码超过 20 行了,一般情况下说明写的有问题,直接看答案(确实有个别非常繁琐的题目,面试一般不考);
  • 开始的时候按分类刷,不要按顺序刷;
  • 如果遇到完全没有思路的题目,不要悲伤,不要觉得自己是个傻瓜。秉承「闻过则喜」的态度,试想如果是面试时候恰好考到这道题目呢?
  • 刷过了过几天又忘了也没关系,根据艾宾浩斯记忆曲线,前几天是忘得最快的时候,多看几遍;
  • 当然,死记硬背是没用的,一定要理解题目;
  • 做题的时候身边要有白纸,随时在纸上画下示意图,不要空想;
  • 做了几道同类题之后,总结做题模板,比如说 backtracking 的做题模板;
  • 后期刷熟了,不要分类刷,随机刷;
  • 已有的题库就当做例题,反复看,彻底学透。每周参加周赛,做新题,作为模拟面试。

最后一点,刷 LeetCode 其实就像是大学里的期末考试,如果你两周复习时间可以搞定一门期末考试,那么两周时间也完全能搞定 LeetCode。要做到「战略上藐视,战术上重视」。

按照考察的方面,题目大概分成两类:

  1. 递归;
  2. 其他题目。

对于递归题目,拿到题目首先要思考:

  1. 怎么才能把题目的输入规模缩小,简化为规模更小的问题
  2. 另一方面基础情形是什么

然后再考虑选用哪种实现方式,是回溯还是动归。

特别注意的地方

  • 不要沉迷于研究语言特性。

    就像上面说的,使用自己最熟悉,日常使用最多的语言。不要觉得 C++ 或者 Java 或者 Whatever 刷题最爽,或者你看的答案采用了什么语言,抓住主要矛盾,你是来刷题的,不是学习新语言的。我之前犯得错误就是边学 Rust 边刷题。

  • 不要沉迷于数论

    LeetCode 上有一些涉及到数论的题目,但是代码面试不是 ACM, 也不是你的大学期末考试。最多熟悉一下排列组合算法、全排列和欧几里得算法就行了,不要沉迷于数论。

  • 要总结自己的特殊问题

    说了这么多,都是共性的问题,但是每个人都会有自己特殊的问题。比如说我的问题就在于不太敢用字典,总觉得会让人感觉投机取巧,我一个工作四年的人,肯定是知道字典的,但是做算法题的时候总在潜意识里避免使用。实际上 LeetCode 第一题就用到了字典。

面试刷题总结(五)- 贪心算法

天字第一条:永远不要首先尝试贪心算法,并尝试证明它是对的。而要使用动态规划推出一个算法,然后可以尝试简化到贪心算法。

尤其是在面试中,基本不会出现贪心算法,太 tricky 了。如果一个面试官问了一个题目,并且他只会用贪心算法解,那么这个面试官水平也一般,这样的公司不去也罢。

相比动态规划来说,贪心算法一般来说:

  1. 要求条件更严格,也就是贪心选择条件;
  2. 时间复杂度往往更低,能达到线性时间复杂度。

贪心选择性质:每一步都选择局部最优解,而局部最优解恰好是全局最优解。贪婪一般需要预排序,证明贪婪成立可以采用数学归纳法,或者证明不会有更好的方法

区间问题

合并、排序区间也是一个常见的问题。

例题

LeetCode 56

LeetCode 57 合并区间

这道题关键之处在于合并后,把剩余的区间直接加上来,这样就不用考虑不少特殊情况了。

class Solution:
    def insert(self, intervals, newInterval):
        ans = []
        start, end = newInterval
        remainder = 0
        for x, y in intervals:
            if start <= y:
                if end < x:
                    break  # 找到了结尾了
                start = min(start, x)
                end = max(end, y)
            else:
                ans.append([x, y])
            remainder += 1
        ans.append([start, end])
        ans += intervals[remainder:]
        return ans

会议室 II

LeetCode 矩形重叠问题

参考资料

  1. 面试不会考贪心算法

UnionFind 算法

unionfind 算法是用于计算图中的节点连通性的算法。其中连同的意思是满足『自反』『对称』『传递』三个意思的连通。

class UnionFind:
    def __init__(self, count):
        self.count = count
        self.parents = list(range(count))  # 初始化时 parent 指针指向自己

    def union(self, p, q):
        """把 p, q 两个节点连通起来"""
        p_root = self.find(p)
        q_root = self.find(q)
        if p_root == q_root:
            return
        self.parents[p_root] = q_root
        self.count -= 1

    def find(self, p):
        """找到 p 节点的根节点"""
        while self.parents[p] != p:
            p = self.parents[p]
        return p

    def is_connected(p, q):
        p_root = self.find(p)
        q_root = self.find(q)
        return p_root == q_root

在上面的算法中,我们发现 union 和 is_connected 主要依赖于 find 的时间复杂度。而在树极端不平衡的情况下,是可能退化到 O(n) 的,所以不优化的前提下,时间复杂度是 O(n)。

优化1 – 保持树平衡

class UnionFind:
    def __init__(self, count):
        self.count = count
        self.parents = list(range(count))  # 初始化时 parent 指针指向自己
        self.sizes = [1] * count  # 记录每棵树的大小

    def union(self, p, q):
        """把 p, q 两个节点连通起来"""
        p_root = self.find(p)
        q_root = self.find(q)
        if p_root == q_root:
            return
        if self.sizes(p_root) > self.sizes(q_root):
            self.parents[q_root] = p_root
            self.sizes[p_root] += self.sizes[q_root]
        else:
            self.parents[p_root] = q_root
            self.sizes[q_root] += self.sizes[p_root]
        self.count -= 1

经过这个优化之后,时间复杂度就降到 O(logN) 了。

优化2 – 路径压缩

在调用 find 函数的时候,把

class UnionFind:
    def find(self, p):
        """找到 p 节点的根节点"""
        while self.parents[p] != p:
            # 神奇的路径压缩
            self.parents[p] = self.parents[self.parents[p]]
            p = self.parents[p]
        return p

Go 语言实现

type UnionFind struct {
    count int,
    parents []int,
    sizes []int
}

func NewUnionFind(n int) (*UnionFind) {
    parents := make([]int, n)
    sizes := make([]int, n)
    for i := 0; i < n; i++ {
        parents[i] = i
        sizes[i] = 1
    }
    return &UnionFind{n, parents, sizes)
}

func (uf *UnionFind) Union (p, q int) {
    pRoot := uf.Find(p)
    qRoot := uf.Find(q)
    if pRoot == qRoot {
        return
    }
    if uf.sizes[pRoot] < uf.sizes[qRoot] {
        uf.parents[pRoot] = qRoot
        uf.sizes[qRoot] += uf.sizes[pRoot]
    } else {
        uf.parents[qRoot] = pRoot
        uf.sizes[pRoot] += uf.sizes[qRoot]
    }
    uf.count -= 1
}

func (uf *UnionFind) Find(p int) int {
    while uf.parents[p] != p {
        uf.parents[p] = uf.parents[uf.parents[p]]
        p = uf.parents[p]
    }
    return p
}

func (uf *UnionFind) IsConnected(p, q int) bool {
    pRoot := uf.Find(p)
    qRoot := uf.Find(q)
    return pRoot == qRoot
}

LeetCode 题目

LeetCode 200 岛屿的数量

这个题就很简单了,简直是 UnionFind 的直接应用。

  1. Union-Find 并查集算法详解

小技巧

时间复杂度需要优化

如果你的算法和预期的时间复杂度还差一些数量级,那么考虑下是不是某个操作可以转化成 hash 查表,这样这个操作就是 O(1) 了。

如何证明算法正确

一般使用归纳法。