压缩算法笔记

Know how to solve every problem that has been solved.

What I cannot create I do not understand.

–Richard P. Feynman

上个月因为公司内部的比赛,被迫短时间内了解了一些压缩算法,还动手实现了一些,比如lz77,deflate,bwt,bcm等,不实践不知道,一写代码就发现有些东西你以为你懂了实际上你没懂,加上最近看了已故物理学大师理查德费曼的一系列视频,其中一个细节让我印象深刻,他去世后大家在他办公室的黑板的左上角(这样就可以防止不小心被擦掉)发现他一直保留着上面的两句话。

理查德费曼很小的时候就受到他父亲的教育,明白了知道和理解是两个概念,所以他一直能保持好奇的心态去思考每个问题。
这两句话的本质是一样的,也就是——只有自己能做出来才算真正理解了,要做到这一点就需要知道每个问题背后是如何真正被解决的,而不是只知道个结论,所以理解一个概念的最高境界就是你能教会别人这个概念。

有感于此,特撰此文记录一下这段时间研究压缩算法的过程。

阅读更多...

GopherChina2020个人总结

如果你是新入坑的gopher那么建议一定要看一下Go Programming Patterns这个演讲。本次大会讲框架的比较多,听下来感觉go-zero做的比较完善,也更适合小公司或者个人上手,而且作者比较有激情。然后推荐那个Go编译器的、TiDB遇到的问题的、还有探探的。最水的是一个老外的Go in the Cloud - Why People Choose Go for Cloud Computing。。。

由于大会第二天分了两个会场,所以一个人只能听到部分的演讲,所以我在会场1和2反复横跳,挑着听了一些。比较遗憾的是阿里的那个EDAS的没听到,据说讲的比较好。

大会的PPT可以在这个git仓库找到

现场偶遇了前同事666,一开始带着口罩还没太确认,后来坐下来发微信才确认。

  1. 探探 ttdb
    探探是本次大会的联合主办方,是一个年轻人社交的app,呃,其实他们的现场的宣传片里面好像还有60多岁的使用者。如果让你设计一个系统,扫描两个人经过的地理位置,从而进行匹配出擦肩而过的人,你会怎么设计?
    他们介绍了自己的数据库的一些实践经验:

    • sql解析上的优化,比如做谓词下推等
    • 列存储,selection阶段利用cache coherence提升性能
    • 故障检测没有选择去中心化的gossip,而是使用的中心化的超时检测,故障恢复时候避免所有请求打到一个新的从节点导致峰值,而是偶尔将请求给从节点,保持热数据。
    • 利用这个库来进行goroutine的泄漏检测。
  2. Go Programming Patterns
    这个演讲里面的内容其实是我们平时代码里面都常会用到的一些小技巧还有一些控制反转等理念,尤其建议新接触Golang的同学都可以听一下,重点体会一下看开源代码学习好的编程模式的这种理念。另外,作者应该是比较熟悉各种语言的特性,所以对Golang也有很多吐槽。

    • functional option,这个应该应用是最为广泛的pattern了,几乎各大开源项目里面都用,很好地解决了可选参数必选参数区分,内部结构封装不破坏,使用时自注释等一系列问题。
    • go generation,因为不支持泛型(至少在2021年之前),所以很多时候利用好go generation是很必要的。
    • 错误处理,这里他提到rob pike的一个上古文章建议大家看看,但是我不确定他指的是哪一篇,不过go1.13新增加了errors.IsAs 两个用来帮助处理函数,同时fmt.Errorf里面支持通过%w来wrap一下error了。
    • kubernetes visitor、装饰器、pipeline等就看ppt吧,讲的比较清楚。
  3. Grab Food
    Grab也是GopherChina的老赞助商了,Grab是东南亚的超级巨无霸,可以理解为美团+支付宝+滴滴+高德地图。
    他们先是介绍了他们的Grab-Kit服务框架,和其他框架一样,支持各种middleware,validate、trace、throttling等,还支持chaos来模拟失败(捣乱猴?)
    然后介绍了Grab Food内部的ML Pipeline:

    1. 候选集合
    2. 过滤
    3. 重排序
    4. 后排序
      先引用Google的文章列了下当前机器学习的痛点,介绍了他们的chimera系统是如何做到持续集成、持续训练、持续交付的自动化的,做到了ML-ops。并提到了他们用了一种multi arm bandit AB test来解决模型的适应性问题。
  4. go-chassis
    这个是我司的人讲的,略过。

  5. Functional options and config for APIs
    这个演讲内容和前面第二个撞车了,看前面那个就行。

  6. 百度BFE
    这个老兄的因为主要不是什么技术型的演讲,所以我没怎么听就跑了,里面介绍了一些做技术管理的东西。

  7. go-zero
    又是一个搞框架的,不过这个老兄挺有意思,他说自己70后还在笔耕不辍的写代码。他这个go-zero是他们公司内部使用过程中迭代出来的东西,不是其他一些框架可能是脱离具体业务的产物。听下来感觉go-zero的功能还是很完善的,的确一站式解决了一些开发上的boilplate代码,而且他上来就是说我希望自己团队里面风格尽量统一,所以才有的这个东西。除了这个框架本身,我印象比较深的是他其中加入的一些自己产品中的解决问题方案。

    • 面向故障编程。
    • 不要join!
    • 如何正确的设计缓存,防止缓存穿透、击穿、雪崩。
    • 负载均衡上他提到了Power of Two Choices算法,这样既可以保证尽量多的就近选择,又动态控制不会把附近的服务处理时长搞得太长。基于这两篇文章12可以仔细研究下。
    • 自适应熔断,放弃了Netflix的Hystrix,介绍了他们用的Google SRE算法,支持自定义触发条件等。
    • 自适应降载。
  8. Go+
    由于布道师许式伟本人没来,找了个人临时讲,效果就不好,没有讲清楚为Go+替代Python搞数据科学的必要性,虽然堆了一堆PPT。。。Go+的运行可以使用转换成Go语言编译运行,也可以转换成字节码直接运行,性能差一点,感觉这个很鸡肋直接python不好么。而且当前不支持interface,没有runtime优化。

  9. PingCAP-Go runtime related problems in TiDB production environment
    这个演讲中提到的问题其实在我们工作中也遇到了,演讲者是golang internals的作者。
    第一个问题是golang的goroutine调度导致时延变大,其实这个我理解并不算是问题,或者说golang的goroutine调度实现就是如此,golang不像别的语言是原生支持了协程,同时也就绑定了他的实现,很多其他语言是通过库的方式来做的协程,调度器其实是可以根据需求来换实现的。所以如果要在go里面解决调度问题,要么就只能把高优先级的给绑核了。
    第三个问题是GC的bug
    第四个是NUMA的使用的建议,GC不是NUMA aware的,在allocation里面的帮助扫描触发之后,在众核环境下表现很差。这个现在版本已经优化了。

  10. Go语言编译器简介 史斌
    这个老兄就很硬核了,是给golang提交代码最多的50人之一,拥有Go的git库的提交权限,也年年收到go官方的邀请去美国开会。
    他提到了Go语言其实用的是自举,而不是走LLVM这种通用的方案,所以很多在LLVM那边做的优化,golang的编译器都没有,需要添加(大佬你的提交就是这样来的吧)。golang从源码到汇编有48道工序,他讲的话估计三天都不够。最后他选了前端、中端、后端的优化讲了一下自己的patch,还是挺有意思。

  11. GORM 剖析与最佳实践
    这个应该是国内做的最好的golang开源项目了,作者介绍了GORM2.0的重构和设计和一些最佳实践,感兴趣的可以仔细看下,当前暂时没用之后用了再回头看看。

[桌游人生]第七期.农场主的术与道

疲劳期

时间永远是最大的敌人,无论曾经多么热爱,不得不承认总是有疲劳的那一天,盛极必衰物极必反也是这个道理。从某种意义上来说,对一件事物的热爱程度我感觉也有点像这个技术成熟度曲线

随着时间的推移,桌游玩家对桌游的热爱程度大致上和这个曲线也差不多。从一开始入坑时看着啥都新鲜,疯狂追逐新游戏;到热情渐渐冷却,发现现在的新桌游设计的套路,玩啥游戏脑海里都是一些经典老游戏的影子;然后就是一个低谷,觉得越来越少有游戏能称得上好玩。不过正是经历了这样的一个过程,洗尽铅华后,玩家反而愿意回头看看那些老游戏,那些当年由于过度追新而未来得及深究的经典——比如Agricola(农场主)。于是今天就让我们来好好聊一聊这款曾经的桌游界扛鼎之作。

农场主是一个既需要短期决策也需要长期战略的标准德式游戏,而且在两方面都做得尤为突出。和所有的传统的抽象棋类游戏一样,其实游戏在一开始都是胜负已定的,只不过游戏状态太多,计算机也无法算清每一步的决策,但是这不妨碍一代又一代的棋类大师在钻研棋艺的路上不断探索(当然最近AlphaGo给了人类当头一击)。农场主不是传统的抽象棋类,它有随机元素,也有非公开信息,但是游戏在这两方面都进行了限制,使得游戏增加重玩性的同时又不至于失控,可以说是最大程度上保留了德式游戏的灵魂。

阅读更多...
  • Copyrights © 2011-2020 仙雾

请我喝杯咖啡吧~

支付宝
微信