TimSort 深度解剖:Python 与 Java 默认排序的精妙设计
为什么 Python 和 Java 不约而同选择了同一个排序算法?TimSort 对真实数据的哪些特征做了针对性优化,使它在工程实践中击败了教科书算法?
发布来自土法炼钢兴趣小组的知识、笔记、进展和应用。主题包括数据结构和算法、编程语言、网络安全、密码学等。
为什么 Python 和 Java 不约而同选择了同一个排序算法?TimSort 对真实数据的哪些特征做了针对性优化,使它在工程实践中击败了教科书算法?
当数据量超过内存容量时,排序算法面临全新的挑战。从败者树到异步 I/O,外部排序的工程实现远比教科书描述的复杂。
椭圆曲线密码学的数学核心,比你想象的更优雅。
打破 O(log n) 的壁垒——深入 Van Emde Boas 树的递归宇宙分裂、O(log log U) 全操作复杂度、以及它在操作系统调度器中的真实回响
把前几篇的算法组装起来,构建一个真正可用的向量检索系统。
你调用 kmalloc(64, GFP_KERNEL),内核在 3 微秒内给了你 64 字节。背后是两层精密的机械:伙伴系统管理物理页面,SLUB 把页面切碎成小对象。这两层如何配合?各自解决了什么问题?
你的 ext4 文件系统上有一个 1TB 的数据库文件。内核如何在 O(log n) 时间内找到文件偏移量 847,293,510,144 对应的物理磁盘块?答案藏在 extent tree 里。本文逐一拆解 ext4、XFS、btrfs、ZFS、F2FS 五种文件系统的树形结构设计。
互联网的路由表是人类建造的最大分布式数据结构。
当多线程争抢一把 mutex 保护的队列时,吞吐量随线程数增长反而下降——锁成了瓶颈。无锁队列用 CAS 循环取代互斥,换来真正的无阻塞并发,但也引入了 ABA 问题和内存回收的工程深渊。
Linux 内核如何在并发数据结构中实现读侧零开销?RCU 用一种违反直觉的方式回答了这个问题:让读者永远不等待,让写者承担一切代价。
Yann Collet 的杰作:同时赢得速度和压缩率。
搜索引擎的倒排索引压缩,是整数压缩最大的战场。
给定一个被线段划分的平面,如何快速确定一个查询点落在哪个区域?梯形分解用随机增量法构建 O(log n) 查询的优雅结构。
动态规划不只是算法竞赛的工具。从广告预算分配到 GPS 轨迹匹配,DP 的思想在工业系统中以各种形式默默运行着。
Rust 的 sort_unstable 和 C++ Boost.Sort 背后的 pdqsort 如何做到在几乎所有数据分布上都表现优异?模式自适应意味着什么?