TimSort 深度解剖:Python 与 Java 默认排序的精妙设计
为什么 Python 和 Java 不约而同选择了同一个排序算法?TimSort 对真实数据的哪些特征做了针对性优化,使它在工程实践中击败了教科书算法?
发布来自土法炼钢兴趣小组的知识、笔记、进展和应用。主题包括数据结构和算法、编程语言、网络安全、密码学等。
为什么 Python 和 Java 不约而同选择了同一个排序算法?TimSort 对真实数据的哪些特征做了针对性优化,使它在工程实践中击败了教科书算法?
Rust 的 sort_unstable 和 C++ Boost.Sort 背后的 pdqsort 如何做到在几乎所有数据分布上都表现优异?模式自适应意味着什么?
当数据量超过内存容量时,排序算法面临全新的挑战。从败者树到异步 I/O,外部排序的工程实现远比教科书描述的复杂。
当单核性能到达瓶颈,排序如何利用多核 CPU 和 GPU 的并行能力?从排序网络的理论优雅到工业级并行排序的工程妥协。
12 种排序算法在 7 种数据分布、4 种数据规模下的全面对比。用实测数据回答'什么时候该用什么排序'这个永恒的问题。
Go 的 map 用的是什么哈希表?Rust 的 HashMap 呢?Python 的 dict 呢?它们分别选了三条完全不同的路线——链式哈希、Swiss Table、开放寻址。选择背后的 trade-off 远比你想象的深。
传统哈希表的 O(1) 查找是'期望'——运气不好时,线性探测可能走 50 步。Cuckoo Hashing 给出了'确定性' O(1):最多查 2 次(或 d 次)就知道元素在不在。这个保证对网络设备中的精确匹配至关重要。
std::unordered_map 慢在哪里?每次查找跟着指针跳来跳去,缓存全部打飞。Google 的 Swiss Table 用 SSE2 一条指令并行比较 16 个槽位,把哈希表的探测从'逐个比较'变成了'批量筛选'。这篇文章从控制字节的位级设计讲到完整 C 实现,拆解这个替换了 Google 全部 C++ 哈希表的方案。
编译器怎么在 O(1) 时间内判断一个标识符是不是关键字?用哈希表?但普通哈希表有冲突,最坏情况退化成链表。完美哈希给出了确定性答案:对已知的 n 个键,构造一个完全无冲突的哈希函数,查找时间严格 O(1),空间 O(n)。这是静态字典问题的终极解法。
RSA 的安全性始于一个问题:如何快速找到大素数?
一个两千年前的算法,仍然是现代密码学的基石。
LLL 算法是密码分析中最强大的工具之一。
有限域是密码学和纠错编码共同的数学基础。
椭圆曲线密码学的数学核心,比你想象的更优雅。
每个正则表达式引擎背后,都有一个 DFA 最小化算法在工作。