混沌周刊 #15 | 技多不压身

各位好。

几天前在V2EX看到一个问题:如何写一个正则表达式,来匹配仅有偶数个0和奇数个1的字符串?这个问题没有「那么难」,但也不好一下子就想出来。答案其实是:

^(0(11)*0)*(1|01(11)*0)(0(11)*0)*((1|01(11)*0)(0(11)*0)*(1|01(11)*0)(0(11)*0)*)*$

看起来很复杂,但这个正则表达式其实是构造出来的,我写了一个解释:

如果让 X=(0(11)*0), Y=(1|01(11)*0),那么整个其实是X*YX*(YX*YX*)* (开头结尾的符号省略了,不影响理解),而这个的意思其实是出现奇数个 Y 间隔任意个 X.

为什么 X 可以随意出现呢?因为 X 一定代表了偶数多个 0 和 1,无论是我们想要的奇数个 1 还是偶数个 0,减去偶数个 0 和偶数个 1 都没关系。Y 也不难理解了,因为穷举了所有奇数个 1 出现的情况。奇数个 1 出现奇数次还是奇数,所以满足要求。

好吧,我知道在工作上写这样的正则可能会被打死(多数正则其实也是某种Write-only的东西)。不过这不影响正则的重要性。Go语言之父Rob Pike还有过「不会正则和浮点数就不该写生产代码」的言论。正则表达式,是每个程序员工作中都可能用到的工具:即使生产代码里没有,开发过程中也常常做查找和批量替换,正则可以极大提高你的工作效率。

我以前第一次学会正则,是看的互联网上叫《正则表达式30分钟入门》的一篇教程。如果你自认为对正则还很不熟悉,强烈推荐一读。常见的编辑器如Visual Studio Code和Vim,都支持带捕获的正则查找和替换。更进一步,几乎所有的常用语言都支持正则表达式查找替换。如果你经常用Vim的命令如 :%s/\(\d\+\)/\1. /g,来做替换,那么也能很快上手sed这个在命令行做替换的工具。

说到sed,其实经过Unix和后来的GNU的发展,现代Shell包含了大量在极有效率的命令行工具:递归按条件找到文件并统一做某种操作的find,可以用一行命令发送API请求的curl,方便对多列文件进行处理的awk,支持无限精度计算的bc,从各种地方搜索正则表达式的grep等等。而且这些命令可以通过本身就很强大的Shell连接到一起,用数行命令完成难以想象的需求。而它们也不需要你深入掌握,用到的时候看一看文档就可以。

毕竟,懒惰是程序员的三大美德之一

🧩 沉下去的浮点数

说回Rob Pike的名言。人们对正则表达式关注得更多,而对浮点数可能只有一个粗浅的印象,认为其像一头形状狰狞,难以驾驭的怪兽,只有在回答「为什么0.1+0.2不等于0.3」这种问题的时候才会想起它。深究浮点数又是要求深入的数学知识,连What Every Computer Scientist Should Know About Floating-point Arithmetic都如此地长。不过这不妨碍我在这里列出一些你可能不知道的小问题:

  • 浮点数在计算机内部是用二进制表示的,因此一些在十进制里可以精确表示的数,在二进制里其实是无限循环小数,之前那个0.1+0.2的问题即来自于此;
  • 在一些场合,为了避免以上问题,人们需要以十进制存储的浮点数,一些硬件和语言支持此类型,通常称为Decimal;
  • 浮点数之所以称为「浮点」,因为其值是由指数 (exponent) 和尾数 (mantissa) 共同决定的,当某个值最小的有效数字位超过了尾数的最小位,该数即会无法精准表示,而这和浮点数的实际值是小还是大,有没有小数位,并没有关系,比如1241523563262624633是一个整数,也小于64位浮点数的最大值,但却不是一个可以精确表示的数,在一个典型的JavaScript环境里,它会被约化为1241523563262624500;
  • 因为有一个独立的位表示符号,浮点数存在两种0的表示,-0和0;
  • 由于以上若干原因,实际的浮点数运算并不遵循我们小学学到的结合律和分配律;
  • 浮点数存在自己的一套异常机制,因此严格而言,浮点运算是存在副作用的;
  • 浮点数存在一些特殊的值,比如1.0/0.0=Infinity,0.0/0.0=NaN,但由于它们并不是「一个值」,所以不能直接使用等号判断,而得用特殊的函数,比如JavaScript中的isNaN
  • 实际上,也不应该用等号判断大多数浮点数是否相等,常见的方法是比较差的绝对值是否「足够小」。

如果帮到你了,我很乐意听到一声谢谢 🙂

🌍 来自网络

  • 单元测试很重要。C++的单元测试框架里,比较常见的是Google的Google Test,而它对于C而言,似乎还是大了一点。我找到了一个非常轻便的C单元测试工具ctest,只有一个头文件,包含之后用它提供的宏就可以。
  • 对于某些领域外的人来说,「数字化转型」是一个有些陌生的概念。但对驱动着人类生活的大型传统公司来说,这也许很重要。又一场深刻的变革。
  • 每个人写的代码都要处理非预期的情况。常见的语言们提供了多种机制处理这些情况:异常、Result<T>、返回值、断言,还有其他。喵神以前一篇介绍Swift中Error的文章详细分析了这几种错误处理机制的适用场景和区别。虽然讲述的语言是Swift,但相信对所有语言都有帮助。
  • Richard Hipp (SQLite作者) 参与的一期播客,介绍了SQLite是如何成功的。
  • 我们都想要业余项目,不是么?这里有一些建议,有关如何让它们的成功率高一点,更容易坚持下来。

今天就到这里。预祝各位假期愉快。


2 comments

    • 浮点数的等号就是等号而已,比较的是两个浮点数的二进制表示是否完全一致。多数时候不应用等号表示,是因为运算可能会带来舍入误差,导致这个数可能永远也不会到达那个精确值。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注