苟利国家生死以,岂因祸福避趋之

Panda Home

如何将递归转成迭代

要理解递归,先得理解递归 发现问题 函数的递归调用是码农在日常工作中不可或缺的利器,在某些问题上,函数递归可以提供更为简洁的代码实现和更为直观的阅读理解,比如说我们很熟悉的树形结构的遍历。 然而,当函数调用的层数过多的时候,就可能导致著名的 Stack Overflow 错误,而栈空间一般是由编译器( C/C++ 等)或者 Java 虚拟机( Java 系语言)来管理,对程序员是不可见的,当然我们可以通过配置参数来调整程序的栈空间大小,但不免麻烦,并且递归层数一增加,栈很可能又要溢出。 尾递归是一个常用的优化方法,很多语言在执行的时候会识别这种优化,因为递归函数调用是一个函数的最后一步,所以在递归调用之前,就可以把当前函数调用从栈中弹出,再把新的函数调用压栈,这样就不会因为递归深度的增加吃掉栈空间了。 但尾递归并不是很容易就能实现的,用二叉树的中序遍历举例,它的递归版本非常简单直观,

布隆过滤器简介

发布于 # 聊聊技术
标签: # 布隆过滤器 # 大数据 # Bloomfilter # Java # Go # Python
布隆过滤器简介
Photo by Thomas Martinsen on Unsplash

在日常写码中,我们经常能遇到判断一个元素是否在一个给定的集合中的需求。听起来这种问题很简单,用哈希集合就能轻松搞定,用 Python 表示的话,很容易写出如下的代码, >>> my_set = set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]) >>> 1 in my_set True >>> 11 in my_set False 并且我们知道在集合中查询的时间复杂度是常数级。然而,如果集合上了规模,我们就不得不考虑这样一个集合将要占用多少空间了。假如里面存的都是整数,按一个整数四个字节计算,十亿个整数就要用掉大约 4GB 的内存,这个大小光是程序启动时从外存加载数据的时间就够程序喝一壶的。 那么如何解决这个问题呢? 当然,如果我们确实希望精确地知道一个元素是否在这规模大小为十亿的集合中,哈希集合的使用还是不可避

记一次 Airflow 性能调优

本文基于运行在 Google Cloud Composer 上的 Airflow 1.10.15 。 TL;DR 复制一份参数计算表格,填入 Airflow 集群的配置,将最下方给出的参数结果应用到自己的集群上,稍等片刻即可生效。 问题产生 Airflow 用得久了,上面跑的 DAG 越来越多,并且随着业务量增加,每个 DAG 中需要执行的任务数量也越来越大,这时很容易遇到任务节点之间延迟过大的问题,具体表现为在上游节点执行完成之后,要等很久它的直接下游节点才会被 scheduler 安排到队列里等待执行。在我们的生产环境中,根据甘特图显示,最严重的时候两个相邻节点的执行需要等待 40 分钟之久,而任务的本身运行时间仅仅需要五六分钟左右,这样的性能对于数据离线分析来说是不可接受的,因此花了两天的工夫进行性能调优,借鉴了大量文档和前人经验。为了避免再次掉坑里,就决定写篇短文来记录一下这次调优

我的 2020

发布于 # 随便聊聊
标签: # 2020 # 年终总结 # 谈笑风生
我的 2020
From https://christmasstockimages.com/free/new_year/slides/2020_new_year.htm

谈笑风生又一年 又到一年年底了, 2020 对所有人来说都是不平凡的一年,从年初的美国刺杀苏莱曼尼、科比坠机,到年底的特朗普下台、中欧投资协定谈判的完成,贯穿其中的则是人类的公敌——新冠病毒。至于其他的事件诸如加州山火都是小事。 但既然题目叫『我的 2020 』,这里就不再谈论这些大家已经耳熟能详的各种事件,只是简单记录一下自己这一年的变化。 工作 由于新冠疫情的爆发,公司于三月初开始全员在家搬砖,可以说这个决定来得正是时候。去年年底公司被收购,在大概两个月的过渡期之后,原公司的各种硅谷标配福利被母公司砍得所剩无几,最明显的就是每天的免费午餐不再提供了,公司周边的馆子动辄十几块一顿,作为穷苦人家实在吃不起,正发愁以后如何找借口午饭之后再去上班,恰好公司下令全员居家,自己做比下馆子可便宜多了,虽然麻烦些,但趁着做饭吃饭收拾的时间正好能从繁忙的工作中休息一下。 聊完了午饭的问题,在居家工作

八皇后问题

最近 Netflix 又出品了一部新剧,并在豆瓣上获得了 9.0 的高分,叫《后翼弃兵》。讲的是从小在孤儿院长大的主角拥有着不凡的国际象棋天赋,在她的天赋被发现挖掘之后一路走到了国际象棋世界冠军的故事。说到国际象棋,作为一名程序员,自然而然就想到了计算机的经典问题——八皇后问题。 所谓八皇后问题,就是在 8×8 的国际象棋棋盘上放置八个皇后,使得彼此之间不会互相攻击。一个皇后的攻击范围是皇后所在的行、列、和两条对角线上的所有位置,可以看成是加强版的中国象棋中的『車』,这就要求每两个皇后不能在同一行,不能再同一列,并且不能再同一条对角线上。维基百科上给出了一些可行解,例如下图所示,棋盘上有八个皇后,而这八个皇后互相攻击不到对方。 <figure> <figcaption> 八皇后问题的一个可行解 </figcaption> </figure>