The world is waiting for you

  • Like many others, this is Yet Another Personal Blog. I blog my thoughts about coding, traveling and exploring fun details in life.
  • I’ve used Hexo, Wordpress, Ghost 4.x and decided to turn back to static site generators. Now I’m happily hosting my site here with Hugo&PaperMod.
  • For any questions or if you think we share something, feel free to reach me by Telegram or Email, Twitter is fine but I’m not using it a lot. Anyway, enjoy it here, welcome.

Sourcecode of Python Heap Queue

Heap 作为一种重要的数据结构,有许多应用场景,比如优先级队列,每次出队的都是最大值或者最小值的元素。很多语言都集成了相关实现,比如 Java 的 PriorityQueue,而 Python 提供了 heapq 模块。 因为 Heap 通常用数组而不是链表存储,所以 Python 里面的 Heap 实质上就是一个列表,而 heapq 提供的几个函数也是以列表对象作为参数的: from heapq import heappush, heappop, heappify, heapreplace, heappushpop heap = [] heappush(heap, 1) item = heap[0] # 第一个元素代表堆顶元素 heappop(heap) heapify([3, 2, 1, 5, 6, 4]) # 把普通列表转化为堆结构 [1, 2, 3, 4, 5, 6] heapreplace([3, 4, 5], 1) # 直接将堆顶元素 3 替换为 1,最后堆结构为 [1, 4, 5] heappushpop([3, 4, 5], 1) # 先将 1 插入堆中,再 pop 出堆顶元素,最后堆结构为 [3, 4, 5] 为什么 heapq 提供的是最小堆而不是更常见的最大堆呢?这就得从源码中找答案了。...

November 29, 2021 · 4 min

SourceCode of Python OrderedDict

LRUCache 是一种经典的缓存机制,它的基本思路是按照最近使用的时间对元素排序,在清理时优先把搁置最久的删除掉。 如果不想给每个缓存元素都记录一个时间戳的话,可以应用哈希链表来简单地实现 LRU 算法。也就是对一个哈希表中的所有元素增加指针,从而串起一个双链表,这样既可以快速 get value,又可以通过把最近使用过的元素放到头部来维护顺序,删除的时候从末尾开始就好了。 手写双链表并不困难,但是借助 OrderedDict 的话,可以写出非常简短的代码: from collections import OrderedDict class LRUCache: def __init__(self, capacity): self.capacity = capacity self.hashtable = OrderedDict() def get(self, key: int) -> int: if key in self.hashtable: self.hashtable.move_to_end(key, last=False) return self.hashtable[key] return -1 def put(self, key: int, value: int) -> None: self.hashtable[key] = value self.hashtable.move_to_end(key, last=False) if len(self.hashtable) > self.capacity: self.hashtable.popitem() 其中最神奇的就是 move_to_end 和 popitem 方法(后者默认是弹出最后面的元素)的使用,这也得益于 OD 可以保证 key-value pair 的顺序。那么 OD 是如何做到的呢?其实还是双链表,下面是它的 Python 实现:...

November 28, 2021 · 3 min

Numeric Strings in Python

Python 的字符串自带了三种判断字符是否为数字的方法,但实际用处却相差很多。 TL;DR 三种方法 isdecimal < isdigit < isnumeric,即包含的范围越来越大 除了 ASCII 字符以外,对于 Unicode 的字符也都覆盖在内 三种方法对于小数点和负号都会返回 False 三种方法对于空字符串都会返回 False 比较简便判断数字字符串的方法:直接使用 float 方法并检测 ValueError Decimal & Digit & Numeric 对于 isdecimal, isdigit 和 isnumeric 三种方法,目的并不是判断字符串是不是一个有效数字,而是针对每一个字符的校验: isdecimal: 判断字符串中的字符是否都为 Decimal,也就是在 Unicode 中类别为 Nd 的字符 isdigit: 除了 isdecimal 包含的范围之外,还会判断字符是否都为 Digit,即 Unicode 的 Numeric_Type 为 Digit 或 Decimal isnumeric: 除了 isdigit 包含的范围之外,还会判断字符是否都为 Numeric,即 Numeric_Type 为 Numeric 所以这三种方法覆盖的字符范围,每一个都是前一个的超集。对于超出 ASCII 字符之外的效果,比如: “0123456789” 这种 Full-width 字符串 isdecimal 会判定为 True,后两个方法也一样 “⓪①②③④⑤⑥⑦⑧⑨” 这种 Circled-digit 字符串 isdecimal 判定 False,但 isdigit 和 isnumeric 为 True “一二三四五六七八九十壹貳參肆伍陸柒捌玖拾” 这种中文数字字符串只有 isnumeric 才会判定为 True 总之这几种方法有更广泛的用途,根本不是为了简单的 ASCII 数字字符串的判断。即使用来做判断的话,局限性也非常大,因为如果包含小数点和负号,三个方法都会返回 False....

November 21, 2021 · 1 min

From Wireshark to Linux Capabilities

Tcpdump 和 Wireshark 是抓包必备的程序,但是由于需要截取网络数据包,所以在 Linux 下必须以 root 的身份来运行。每次都 sudo 执行不方便也并不安全(对 Wireshark 来说捉包只是一小部分功能),解决方案当然有,在寻找的过程中我了解到了 Capabilities 的冰山一角。 TL;DR 可以通过设置 Setuid 以 root 身份执行,但如此以来赋予了过高的权限(也没有必要)。 Linux 下用 Capabilities 把系统权限划分成多个条目,以此实现细粒度地提升程序的执行能力。 Setuid 先盗一张图复习下 Linux File Permission 的基础知识: 除了 rwx 之外还存在三种特殊类型,即是为了在更高权限下运行程序: Setuid: 程序的运行者不再是执行者,而是变成文件的所有者 Setgid: 程序的运行群组变成了文件的所在群组,如果给目录设置,那么其中新建的文件所有群组会变成目录的群组而不是执行者的群组 Sticky bit: 针对目录设置,目录下的文件只有所有者和 root 能够重命名、移动和删除 在 Linux 中 sudo 是 Setuid 最好的例子,而 crontab 和 tmp/ 分别是 Setgid 和 Sticky bit 的典型应用。 在命令行中测试: # Setuid ➜ ~ umask -S u=rwx,g=rx,o=rx ➜ ~ umask # 掩码是 022,所以默认文件的权限是 666-022=644,而目录则是 777-022=755 022 ➜ ~ touch foo....

November 21, 2021 · 3 min

Overflow in Python

犹记得在 Java 中,int 占用 4 bytes 所以大小限制在 -2^32 和 2^32 -1 之间,如果考虑到溢出的情况,就要用 long 类型来转换。 但是在 Python 中似乎从来没有考虑过类似的问题,也不记得 int 是占几个字节,那么是说 Python 的数字永远不会溢出吗?不可能吧。 答案是对于 int 类型来说,可以认为不会;而 float 类型则需要注意溢出的情况。 首先说 int 类型,打印 sys.maxsize 可以看到 Python 会根据系统是 32 位还是 64 位来确定一个上限值,这点与 Java 等语言一致。不同的是我们仍然可以使用比这个上限大(得多)的整数,因为 Python 支持的是 Arbitrary-precision arithmetic。也就是说为了突破 CPU 字长带来的运算限制,通过在软件层面模拟计算过程,是可以完成更高位数和精度的运算的。比如在公钥加密的场景下,经常需要对上百位的整数进行运算,这时候就需要在软件层面支持。 这确实说明我们可以使用任意长度的 int 数字,只要不超出内存限制的话。因为如果给 Python 解释器分配了 2GB 内存,但是 2 * 1024 * 1024 * 1024 * 8 这么多位也不够表达的话,还是会出错的,只是并非 Overflow,而是 MemoryError. 再说 float. 打印 sys.float_info.max 可以看到 float 的上限值,如果超出之后是会报错的,即 OverflowError....

November 12, 2021 · 1 min