用堆找出最小的 N 个数
不知道为啥，突然想水一篇很水的算法文章。 今天整理 MySQL 的笔记，看到了这样一句话： MySQL 在执行 ORDER BY x LIMIT n 这类语句，且 LIMIT 的数量有限时（比如只需要 3 条数据），MySQL 会尽量通过堆来构建优先队列，减少排序所需的时间。 这是堆的一个经典应用：从海量数据中找出最大（小）的 n 个数。 之前只用堆写过堆排，没有用堆处理过在线算法，所以就写了写。 用一句话概括这个算法：要找最小的数，就要构建大顶堆。 在处理数据时，我们会构建一个大顶堆 H，那么 H[0] 的值也就是当前数据中最小的 N 个数中的最大值，也就是第 N 小的数。 当处理新的数时，如果这个数小于堆顶的数，那么就把它变成堆顶，然后再对堆进行维护，以保证有序。 此算法的时间复杂度为 O(Ml..
更多《流畅的 Python》阅读笔记
去年就想看《流畅的 Python》这本书，今年终于看完了。 《流畅的 Python》是一本深入讲解 Python 语言的书，非常值得一读。去年看到同事在看，就一直想看，陆陆续续看了很久没什么进度，这个月一努力，把这本书看完了。 这次脑洞一开，觉得既然学的是 Python，那我为什么不用 Python 做笔记呢？于是就选用了 Jupyter Notebook 来做笔记载体。一个文档里既可以写 Markdown，又可以运行 Python 代码，简直完美。 所以，这本书的笔记就这么写出来了。内容不算少，所以烦请移步我的 GitHub Repo.
更多Python Hacking: “高级”偏函数
本文讲解了一个需求的解决方案，而这个奇葩需求你在 99.93% 场景下都不会遇到，就算遇到了，也一定有其它更简单的解决方案。 0. 引言 >>> print((lambda x:None).__code__.__doc__) code(argcount, kwonlyargcount, nlocals, stacksize, flags, codestring, constants, names, varnames, filename, name, firstlineno, lnotab[, freevars[, cellvars]]) Create a code object. Not for the faint of heart. 1. 需求 mock.patch 对象在..
更多
Python 函数式编程：不可变数据结构
本文原载于 opensource.com，由本人翻译，翻译作品原载于 linux.cn。翻译及转载基于 CC-BY-NC-SA 协议。具体创作参与信息可见文章最后部分。 不可变性可以帮助我们更好地理解我们的代码。下面我将讲述如何在不牺牲性能的条件下来实现它。 在这个由两篇文章构成的系列中，我将讨论如何将函数式编程方法论中的思想引入至 Python 中，来充分发挥这两个领域的优势。 本文（也就是第一篇文章）中，我们将探讨不可变数据结构的优势。第二部分会探讨如何在 toolz 库的帮助下，用 Python 实现高层次的函数式编程理念。 为什么要用函数式编程？因为变化的东西更难推理。如果你已经确信变化会带来麻烦，那很棒。如果你还没有被说服，在文章结束时，你会明白这一点的。 我们从思考正方形和矩形开始。..
更多