查找第K小的元素
这篇讲的是如何高效地从无序数组中找到第K小的元素，这是一个经典的选择问题。 文章先梳理了常规思路：最直接的是先排序再取，但复杂度O(nlogn)较高。利用选择排序或堆排序可以优化到O(kn)或O(nlogk)，而借鉴快速排序的思想——每次选择一个基准值，将数组分为两部分，然后递归地在目标区间查找——可以将平均复杂度降到O(n)。作者指出，快速排序思想的致命弱点在于基准值（pivot）选择不当会导致最坏情况O(n²)。 文章的核心在于介绍了一种能保证最坏情况也是O(n)的优化算法：**中位数的中位数（Median of Medians）**。具体做法是将数组每5个元素分为一组，先找出每组的中位数，再递归地从这n/5个中位数中找出中位数，用它作为最终基准值。这个策略能保证每次划分后，目标区间至少缩短一定比例（如30%），从而通过递推关系证明其最坏复杂度稳定在O(n)。 作者不仅给出了算法的理论分析，还附上了完整的Python实现代码，清晰地展示了如何将分组、找组中位数和主选择过程结合起来。最后，文章点出这个稳定的基准值选择策略，同样可以用来优化快速排序，将其最坏情况复杂度提升至O(nlogn)。
数论的应用-RSA公钥算法
这篇讲的是RSA公钥算法背后的数学之美。作者从伟大的数学家欧拉切入，引出了现代非对称加密的基石——RSA算法。文章首先点明了对称加密的局限，随后介绍了1976年公钥密码思想的诞生，以及1977年RSA算法的正式提出。 核心部分，文章深入浅出地拆解了RSA所依赖的数论工具：欧拉函数用于计算与某数互质的数的个数，而欧拉定理（费马小定理的推广）则为算法的数学正确性提供了保证。随后，文章分步展示了RSA密钥生成与加解密的全过程：如何选取两个大素数p和q来构造模数n，并由此推导出公钥e和私钥d；以及如何用公钥加密、私钥解密。 为了让理论落地，文中还用了一个具体数字例子（M=52, p=17, q=11, e=7, d=23）演示了整个加密解密流程，让抽象公式变得清晰可感。最终，文章回归数学原理，简要说明了为何这样构造能实现解密的正确性。 整篇文章将深奥的数论概念与实际的密码学应用串联起来，展现了从纯理论到关键技术的奇妙旅程，让你理解为什么这个看似无用的数学分支，最终能成为守护互联网安全的隐形卫士。
P和NP那些事
这篇讲的是计算机科学中P、NP、NP完全（NPC）与NP难（NP-hard）这几个核心概念。很多人误以为NP就是“非P”，文章一开始就澄清了这一点：NP（非确定性多项式时间）问题指的是那些“能在多项式时间内被验证解”的问题，而P（多项式时间）问题自然属于NP。 作者用一个生动的比喻解释了NP的核心：非确定型图灵机可以“猜”出一个解（比如哈密顿路径），然后快速验证其正确性。接着，文章引入了“规约”这一关键工具，并指出Cook发现了所有NP问题都可规约到SAT问题，由此引出NP完全问题——NP中最困难的一类，它需同时满足“是NP问题”且“所有NP问题都可规约到它”这两个条件。 文章还以SAT、2-SAT（P）与3-SAT（NPC）为例，具体说明了概念间的差异，并列举了旅行商问题等经典NPC问题。最后，作者提及了对P≠NP证明尝试的看法，认为这可能需要现有理论体系之外的突破。全文从澄清误解入手，层层拆解概念间的逻辑关系，为理解这个理论计算机科学的核心难题提供了清晰的脉络。
数据结构定义中的中(大陆地区)美差异
这篇讲的是一个挺有意思的技术概念“撞车”现象：作者在和一位清华博士讨论数据结构的选择题时，发现自己按国内教材理解的答案和标准答案大相径庭。一查权威资料才发现，原来“满二叉树”、“完全二叉树”这些基本概念，中国大陆教材的定义和美国及国际通行定义存在系统性差异。 文章核心对比了三个概念。最典型的是“满二叉树”：国内严蔚敏版教材定义为“深度为k且有2^k-1个节点的二叉树”，即每一层都完全填满；而美国NIST的定义（对应full binary tree）则是“每个节点要么是叶子，要么有两个孩子”。两者描述的结构截然不同。对于“完全二叉树”，中美定义在“最后一层节点尽可能靠左”这一点上达成了一致。另外，美国定义中的“perfect binary tree”实际上就是国内教材所说的满二叉树，只是国内很少单独提出这个术语。 作者借此指出，国内考研、等级考试广泛采用的定义与国际标准存在偏差，建议读者在学习数据结构时，多参考英文原版教材以避免概念混淆。
正则表达式 — QQ微信、优酷前端 邮箱正则表达式验证 Bug
作者从一个具体的“坑”入手，揭示了众多网站（包括优酷、QQ微信）在邮箱验证环节可能存在的通用缺陷。他发现，许多广泛流传的正则表达式无法正确匹配像 i@julying.com 这样用户名或域名仅为单个字母的合法邮箱，根源在于早期代码为了图省事，未考虑这种边界情况，而后继开发者则盲目沿用。 文章不仅指出了这个容易被忽略的验证漏洞，还分析了其“代际传递”的技术债成因。作为解决方案，作者提供了经过改进的PHP和JavaScript版邮箱正则表达式，并附上了新手实例代码，这些新表达式明确支持了对单字母部分的验证。 这篇文章的价值在于提醒开发者，处理用户输入时绝不能有侥幸心理。那些“感觉上”少见的情况，恰恰可能是系统的薄弱环节。它以小见大，强调了对所有数据可能性进行严格验证的重要性，避免重蹈类似SQL注入等历史问题的覆辙。
谈谈SVD和LSA
这篇讲的是SVD（奇异值分解）和LSA（隐含语义分析）之间的关系。作者首先拆解了LSA的核心思想：它是一种主题模型，认为词语背后由潜在主题驱动。比如“计算机”和“电脑”在传统词向量空间中无关，但在LSA看来它们同属一个主题，因此包含它们的文章也相关，这突破了表面词汇的限制。 而SVD正是实现LSA的关键数学工具。文章从特征值与特征向量这些基础概念切入，为理解SVD如何分解文档-词矩阵、提取潜在语义结构做了铺垫。作者也点出SVD的广泛应用，比如它同样是PCA（主成分分析）和图像压缩的技术基础。整篇文章从数学基础讲到实际应用，清晰地勾勒出SVD作为通用分解方法，如何催生了LSA这一文本分析利器。
Tips of Linux C programming
这篇文章分享了Linux内核和GNU C中一些不那么为人所知却非常实用的编程技巧。作者从链表的非常规定义讲起，展示了如何将链表节点嵌入到数据结构中，并利用`container_of`宏从节点地址反推出宿主结构体，这种方法比传统教科书定义更灵活优雅。 随后，文章深入到编译器与硬件层面：介绍了用`likely`/`unlikely`宏提示编译器优化分支预测，减少流水线冲刷；演示了通过内联汇编和`lock`指令前缀实现原子加法，保证多处理器环境下的数据一致性；还探讨了GNU C特有的零长度数组特性，用于在运行时动态分配结构体尾部的变长数组。最后，简短提到了三目运算符`a = x ? : y`这种简洁的省略写法。 这些技巧都源自真实的内核开发或GCC特性，能帮助C程序员写出更高效、更地道的代码。文章穿插了关键的代码片段和原理剖析，对希望提升底层编程技巧的读者很有启发。
基于用户的协同过滤和皮尔逊相关系数
这篇文章聚焦于推荐系统中的经典算法——协同过滤，并深入比较了基于用户与基于物品两种实现路径的核心差异。作者指出，从大量实验效果看，基于用户的协同过滤通常表现更优。其关键在于，这种算法的核心思想是“找到与你相似的用户，将他们喜欢的东西推荐给你”，而实现这一点的关键，就是准确计算用户之间的相关性。 文章通过一个具体的评分矩阵例子，生动展示了如何操作。例如，用户a和b对物品X、Y、Z的评分向量非常接近，因此当b未评价物品R时，系统就能将a高度评价的R推荐给b。接下来，文章深入到数学层面，解释了如何量化这种“相似性”。它首先介绍了将用户评分视为向量、计算其夹角余弦值的经典方法（即余弦相似度），随后引出了另一种更常用且效果通常更好的度量方式——皮尔逊相关系数。虽然文章片段未完全展示其公式，但明确了其目标：通过对比两个用户对相同物品的评分趋势（即协方差与各自标准差的比值）来评估线性相关程度，从而更精准地度量用户兴趣的相似性。 总体而言，这篇文章从概念到具体计算，清晰地剖析了基于用户协同过滤的算法逻辑。它不仅解释了“为什么”，更通过实例和公式指引了“怎么做”，对于想理解推荐系统核心原理的读者来说，是一篇内容扎实、脉络清晰的入门解析。
java中byte转换int时为何与0xff进行与运算
这篇文章直击一个Java初学者常见的困惑：在代码中将`byte`数组转为十六进制字符串时，为什么每个字节都要与`0xff`进行与运算，而不是直接强转为`int`？作者通过一个具体的`bytes2HexString`方法切入，引导读者思考这个看似多余的步骤。 核心答案在于Java中数据的底层表示与位扩展机制。`byte`是8位，而`int`是32位。直接将`byte`（例如值为-1，其补码为`11111111`）赋值给`int`时，会发生**符号位扩展**，即高24位全部填充符号位（1），得到`0xffffffff`，这显然不是我们想要的原始字节值。而`0xff`作为`int`常量（二进制为`00000000 00000000 00000000 11111111`），与`byte`值进行与运算，会先将`byte`提升为`int`，但运算结果能**强制清零高24位**，仅保留低8位的原始数据，确保了数值的正确性。 文章进一步回顾了计算机组成中补码的表示方法，为理解位扩展的原理提供了扎实的理论基础。最终，作者给出了明确结论：与`0xff`的与运算是处理`byte`到`int`有符号扩展问题的标准技巧，确保了数据无损转换，这一点在底层编码和通信场景中尤为重要。
原码、反码、补码相关知识总结
这篇讲的是计算机里最基础也最关键的数据表示方法：原码、反码和补码。它清晰地拆解了三者的定义和转换规则。比如，正数的原码、反码、补码都一样，而负数的反码是原码符号位外各位取反，补码则是在反码基础上加1。 文章的核心价值在于，它不仅仅罗列知识，更解释了技术演进的逻辑：为什么计算机会从原码发展到补码？作者通过具体的运算例子指出，原码和反码在处理带符号数的加减运算时，会遇到诸如“-0”带来的结果错误和实现复杂性等问题。 补码的巧妙之处在于它用“10000000”表示-128，统一了零的表示（[+0]补=[-0]补=00000000），从而让加减运算可以统一用加法器处理，极大地简化了硬件设计。文章也点明了补码的表示范围（如8位整数为-128到127），并解释了这个范围为何不对称。 对于想理解计算机底层如何处理数字的读者，这篇文章把“为什么用补码”这个经典问题讲得很透彻。
跨越千年的RSA算法
作者从古希腊几何学中“可公度线段”的概念出发，讲述了数论中一系列精妙思想的演进。文章首先通过欧几里得求最大公度单位的直观例子，自然引出“辗转相除法”这一核心算法，并证明其效率。随后，以正方形边长与对角线不可公度的发现为例，揭示了无理数在古希腊时期就已出现的历史趣闻。 作者进而将话题转向数论中更深入的概念——互质与中国剩余定理。文中用生活中的公交车班次例子，生动解释了互质与最小公倍数的关系，并引出了《孙子算经》中的经典问题，展示了中国剩余定理的雏形与魅力。 这篇长文并非对教科书内容的简单复述，而是作者基于为《程序员》杂志撰写文章时积累的大量素材与个人思考，重新梳理的一条连贯知识脉络。他以牺牲部分严谨性为代价，力求用更直观、可读的方式，展现从古典数论走向现代公钥加密（如RSA算法）的奇妙旅程。
寄存器分配初探–问题描述( Register Allocation – The Problem )
这篇讲的是编译器如何解决“无限变量”与“有限寄存器”之间的根本矛盾。作者从程序员声明的逻辑变量出发，指出实际CPU的物理寄存器数量极其有限，因此必须由编译器决定在特定时刻将哪些变量放入寄存器。这直接关系到程序性能，因为访问内存比访问寄存器慢了100到1000倍。文章用延迟对比数据清晰地说明，优秀的寄存器分配策略能最大限度减少访存，是生成高效代码的关键。这也是一个经典的资源映射问题，其思想甚至能迁移到操作系统页着色等领域。作为系列文章的开篇，本文聚焦于问题定义和背景，为后续探讨图着色、线性扫描等具体算法做好了铺垫。
关于大区间过滤优化内存设计
这篇讲的是在检索场景下，如何优化“大区间过滤”时的内存结构设计。作者指出，传统做法中以 docId 为下标存储域值的方式存在内存浪费，尤其在域值（如日期类型）重复率很高的场景下。 核心方案是引入两个互补的数组：第一个数组以域 Term 的遍历位置（Position）为下标，直接存储对应的域值，这利用了域值在遍历过程中天然有序的特点；第二个数组则以 docId 为下标，存储该文档在第一个数组中的对应位置。这样一来，大量重复的域值（例如“20101202”）在第一个数组中只存储一次，通过第二个数组的间接映射，就能为每个 docId 快速定位到其域值。 作者通过示意图和实际业务分析说明，对于时间这类重复率极高的域，该设计能显著压缩内存占用。整个方案的精髓在于通过空间换时间的思想，巧妙地将高重复的域值“去重”存储，并用一次额外的间接查找换取整体内存效率的提升。
基数估计算法概览
这篇讲的是如何在海量数据中，高效估算不同元素的个数——也就是基数估计。 文章从一个经典场景切入：面对一个大到无法放入内存、且含有大量重复项的数据集，怎样才能快速知道里面有多少不同的数据项？作者首先介绍了一种直观但粗糙的思路：通过哈希将数据映射成均匀分布的随机数，再利用集合中的最小值来反推基数。这个方法虽然简单，但准确度不稳定。 真正的突破来自概率算法。文章重点介绍了Flajolet等学者发展的方法：通过一个良好的哈希函数，将任意数据转化为均匀分布的序列。算法巧妙的观察点在于，考察每个哈希值的二进制表示前导零的长度。在均匀分布下，最长前导零的长度与集合基数存在明确的统计关系。这避免了直接存储所有元素，只需记录一个极小的状态信息。 从最初的Probabilistic Counting，到LogLog，再到近似最优的HyperLogLog算法，文章勾勒出这类算法的发展脉络。HyperLogLog通过分桶统计和调和平均数，极大地提升了估计精度，并已成为Redis等系统中处理UV统计等场景的标准方案。 对于任何需要在大规模数据流上进行实时去重计数的工程师来说，理解这些算法的原理与取舍都非常有价值。
正态分布的前世今生(四)
这篇讲的是正态分布为何能在数学中占据如此核心的地位。作者没有从复杂的公式入手，而是追溯其源头，揭示出一个优美的现象：从一些简单明了的初始准则出发，数学家与物理学家们竟屡屡被引领到正态分布的门前。 文章重点介绍了高斯在1809年的一条经典推导路径：他以“误差分布导出的极大似然估计等于算术平均值”为核心准则，从一个看似合理的测量原理出发，推导出了正态分布的概率密度函数。这仅仅是四条著名“小径”中的第一条，物理学家Jaynes在其著作中总结了四条通往正态分布的不同路径。 文章穿插了高尔顿对正态分布的诗意赞美，以及数学家将其视为“概率论初恋情人”的生动比喻，将冰冷的数学定理赋予了温度与美感。它想告诉我们，正态分布之所以无处不在，或许正是因为它背后蕴含的多种深刻而简洁的原理，如同“条条曲径通正态”。阅读它，就像跟随历史上的智者，一起欣赏通往真理的“条条曲径”。
爱喝啤酒的程序员是如何学习数据结构的
这篇文章从程序员形象的演变切入，探讨了一种颇具创意的数据结构学习方式。背景是传统程序员常被贴上木讷、逻辑化的标签，但随着“Brogrammer”文化的兴起，喝酒、听摇滚等生活元素逐渐融入编程世界。作者通过一系列啤酒杯排列的图片，生动展示了如何用日常物品来可视化抽象的数据结构概念。 具体来说，文章用啤酒杯模拟了二叉树的层级分支、不平衡树的偏斜状态、重新平衡树的调整过程，以及数组、矩阵、链接表、稀疏矩阵、堆和栈等结构。例如，数组用一排整齐的杯子表示线性存储，矩阵则通过网格状的杯子排列展现二维特性。这种方法不仅幽默风趣，还巧妙地将复杂逻辑转化为直观图像，帮助记忆和理解。 核心观点在于，技术学习不必局限于刻板形式，可以结合个人兴趣如啤酒，用视觉化和生活化的方式降低门槛。文章启发读者尝试更灵活的学习路径，将日常元素转化为工具，让枯燥的知识点变得生动可感。
MinHash原理与应用
这篇讲的是MinHash算法，一种基于Jaccard相似度的高效降维技术，专门用于处理大数据集的相似度计算问题。作者从Jaccard Index的定义出发，解释了直接计算集合交集和并集在海量数据下计算资源消耗过大，几乎不可行。MinHash的核心原理是通过随机哈希函数将集合元素映射为哈希值，并取最小哈希值作为签名，因为两个集合的最小哈希值相等的概率正好等于它们的Jaccard相似度，从而将高维数据降维为固定长度的签名向量。 文章进一步展示了MinHash的实际应用，比如在Mahout中用于聚类，以及在一个推荐系统案例中：针对几十万优质用户推荐给几千万普通用户，先用MinHash按相同哈希值个数排序筛选出备选集，再计算余弦相似度取TOPN。这种方法虽然在计算量上仍非最优，但在可接受时间范围内，效果接近两两计算余弦相似度的最优解，尤其适合集合量级差异较大的场景，如大规模用户推荐。
趣题：证明所有乘积的总和与分拆的方式无关
这篇讲的是一个看似简单却意味深长的数学趣题：如何将一堆硬币不断分成两堆并累加每步两堆数量的乘积。作者从经典的“1000枚硬币”问题切入，指出其核心在于证明所有乘积之和恒为一个定值。 证明过程很有启发性。一种思路是数学归纳法，通过构造一种特殊分法先得到公式n(n-1)/2，再归纳证明其普适性。但文章最精彩的部分在于给出了一个“秒杀”视角：每次分堆计算乘积，实质是在统计这一步中被分开的硬币对数量。所有可能的C(n,2)对硬币最终都会被分开，因此总和必然是固定的n(n-1)/2，与具体分法无关。 随后，作者将问题从离散的硬币巧妙地推广到连续的线段分割。当线段被无限细分时，如何求乘积之和的极限？文章通过构造等腰直角三角形进行几何解释：每次分割产生的乘积对应三角形内一个矩形的面积，而所有细分步骤的矩形面积总和，最终会无限逼近整个三角形的面积n²/2。 从组合计数到几何直观，文章展示了如何为同一个问题找到不同层次的优雅解法。这种思维的跃迁，或许比最终的公式更能体现数学之美。
JsonCpp使用优化
这篇讲的是如何为高性能需求场景优化JsonCpp库。作者从项目实战中发现，尽管JsonCpp接口简洁，但在频繁操作JSON数据时性能不尽如人意。文章深入分析了其内部实现，指出operator[]函数开销较大以及std::map查找效率不如哈希表等瓶颈，并尝试修改源码未果。 因此，作者将重点放在了可观测的优化手段上。通过编写基准测试程序，他对比了三种不同使用方式的性能差异：默认的append、复用Value对象并用下标赋值、以及使用StaticString避免拷贝。测试表明，后两种方法能带来一倍以上的性能提升。 更进一步，作者调整了JsonCpp的编译选项，加入“O2”优化参数，使性能再次显著提高。他还尝试在源码中为Value类新增setValue函数，绕过标准接口的类型转换开销，最终让处理耗时从最初的约4900微秒降至约570微秒，配合静态链接还能略有增益。 文章通过具体代码和实测数据，展示了从编译器、使用模式到源码级的多层次优化路径，为需要压榨JsonCpp性能的开发者提供了清晰可复现的实践参考。
讨论：一则并行聚合计算方案的设计
这篇讲的是作者在构建一个实时数据看板时遇到的并行聚合计算难题。场景很具体：一个最多10万元素的数据集，每秒会收到数百到数千次字段修改（远多于增删操作），系统需要实时计算并维护多达50条聚合规则（如求和、平均、加权平均）在最多5层分组下的完整结果树。所有数据都在内存中，要求能立刻响应任何滚动查看。 作者首先实现了一个高效的串行方案：让聚合器监听集合变动，利用更新前后的值进行差值计算，避免全量重算。但面对更高的性能需求，他开始探索并行化。简单的“每次变动后并行计算”不可行，会导致持续高负载和并发错误。他尝试借鉴Erlang的Actor模型，将每个聚合器独立为消息驱动单元，但随之带来了新问题：在传递元素属性更新消息时，是否需要携带整个元素“快照”？直接携带开销太大，不携带则可能因并发修改导致聚合计算拿到中间状态的数据。作者发现，或许只有分组字段变更时才需要快照，这大幅降低了开销。 文章详细剖析了一个从串行到并行演进中的经典权衡：如何在保证实时性的同时，平衡计算延迟、系统负载与数据一致性。作者不仅给出了清晰的问题定义，更分享了思考路径与初步尝试，为面临类似挑战的读者提供了宝贵的讨论起点。