为什么要“包含头不包含尾”?

我记得有一次面试的时候,面试官让我实现一个函数,get_num(start, end),要求返回start和end之间的数字。我给出了一个包含了start不包含end的版本。面试官说这是错的,我反驳道,Python内置的range()就是这样的。记忆尤新。最近终于知道了这样做的原因。

首先从实用方面来看,这样做有很多好处。当然,我会拿Python来举例。

  • 当只有最后一个位置信息的时候,我们可以快速看到到底有几个元素。比如range(4)就是4个元素,my_list[:5]是5个元素
  • 当看到开始下标和结束下标的时候,我们一下就可以算出其中有多少个元素,例如my_list[2:11]就是9个元素
  • 我们可以使用下标将序列表示成两部分,不会重叠。例如,my_list[:x]my_list[x:]是既没有重叠也没有遗漏的两个部分

其实这个问题就像下标应该从0开始还是从1开始一样,又像先有鸡还是先有蛋一样,是很容易引起争议的问题。但是Edsger Wybe Dijkstra对这个问题给出了一个无懈可击的答案,看了之后,我觉得包含头不包含尾就应该是天经地义的!

Dijkstra教授(是的就是那个Dijkstra,以下简称教授)曾手写过一份备忘录,题目是Why numbering should start at zero,虽然题目是“为什么下标应该从0开始”,但是教授在备忘录中很可爱又认真地解释了为什么2, 3, ..., 12就应该表示为2 ≤ i < 13,其他的都是错的,都应该绑在十字架上烧死(后半句是我加的)。此备忘录笔记清洗漂亮,pdf可以在 http://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF 看到,文字版可以在 https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html 看到。

表示上面2到12之间的数据,无外乎以下四种:

a) 2 ≤ i < 13

b) 1 < i ≤ 12

c) 2 ≤ i ≤ 12

d) 1 < i < 13

首先,a)和b)有很大优势,因为a)和b)一眼就能看出元素的个数(上文也提到了);而且根据已知的推论,“两个相邻的序列”应该是,前一个序列的上界应该是后一个序列的下界,这样两个序列可以不重叠又相邻。从这两点看,a)和b)都更好。

然后,我们看下界。我们知道,存在最小的自然数,不存在最大的自然数。所以理应让下界应该是小于等于。如果是小于,那么下界就感觉不是从最小的自然数开始的,ugly!所以我们偏爱a)和c)。

最后我们来看上界。我们已经让序列从最小的自然数开始了,如果上界使用小于等于,那么如果序列收缩为空的时候,怎么表示? 2 ≤ i ≤ ? ugly!如果上界使用小于的话,我们就可以正常的表示成 2 ≤ i < 2 (不存在)了。

综上,a)得到4分,以巨大优势胜出。另外,教授提到有些人对理由充分但是没有实际应用的证据的结论感到不舒服,所以教授在REMARK提到,Xerox PARC开发的Mesa编程语言就讨论了这个问题并且强烈建议使用第一种,后三种及其的UGLY的!

最后教授引申除了为什么将0作为下标(好像教授一直在跑题哦)。我们一定确定要使用a)的表示方法,那么表示长度为N的序列如何表示呢?我们有两个选择: 0 ≤ i < N 1 ≤ i < N + 1。教授认为从0开始更好看,因为这样元素的下标就能表示在它前面的元素的个数。教授说,“这个故事告诉我们,最好将0作为一个自然数。(过了十几个世纪人们才意识到!)”

有意思的是,备忘录后面还有一段,讲了讨论这件事的起因。教授的一个数学同事(当然也是个教授,不过不是计算机的)对他的一些学生发飙了!因为数学教授发现一些年轻的搞计算机的竟然从0开始数数!这不是挑衅嘛!

教授很赞同Antony的一句话:在宗教方面,异教徒必须被烧死不是因为异教徒错了,而是因为“异教徒”有可能是正确的。

 I think Antony Jay is right when he states: “In corporate religions as in others, the heretic must be cast out not because of the probability that he is wrong but because of the possibility that he is right.”

参考资料:

  1. 本文实用角度的三个优点来自于Fluent Python一书第一章
  2. 感谢德州大学保存了教授珍贵的手稿


为什么要“包含头不包含尾”?”已经有7条评论

  1. Range 应该根据其不同的作用选择区间的闭合。比如 C++ 的 random 选择了前闭后闭的区间,因为 C++ 的 integer 是有最大元素的,选择前闭后开区间会导致 random 函数永远无法返回最大元素。从这个对 get_num 函数的描述来看,我也觉得你的面试官的看法是对的。

  2. 我刚意识到你们写的也许是 Python?如果是这样的话那么两种实现应该没区别。

    • 嗯是Python的,当时他们的东西都是Java写的但是要招一些人来用Python写一套测试的东西。

      取最大值这个问题我倒没考虑过,确实有道理。我觉得应该先保证正确再保证易用,如果用C++的话我赞成“前闭后闭”,虽然这样就不能一眼看出有多少元素,以及不好表示一个空的集合了(基本不会有这个需求吧)。

      我感觉C++本来就是实用大于可读的,毕竟rand一般都写成这样:v3 = rand() % 30 + 1985 // v3 in the range 1985-2014

Leave a comment

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