CS-Wiki CS-Wiki
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
  • 唠唠嗑儿

    • 日月既往,不可复追,暑期实习结束!
    • 颜值党的生产力工具推荐
    • 寒门博士的北大八年
    • 咱普通人努力的意义是什么
    • 2021 最后一个月,心有所期,全力以赴
    • GitHub 上只卖 5 美元的脚本,却给我带来了一年数十万元报酬
    • TikTok 前端程序员新加坡纪行
    • 近况
    • 县城再无清华北大
    • 又一个网友做测评做疯了
    • 无序扩张的互联网垄断和社会主义重锤
    • 爽文一篇:没有先例那就给我开先例!十天时间拿到 n+1 赔偿
    • 图灵奖巨佬解惑,为什么把 0 作为第一个元素下标,而不是直观的 1?
    • 面试官再跟你说中国没有根服务器,雪人计划让他了解下
  • 读书笔记

  • 210-唠唠嗑儿
  • 唠唠嗑儿
小牛肉
2023-01-18

图灵奖巨佬解惑,为什么把 0 作为第一个元素下标,而不是直观的 1?

很多小伙伴初学编程的时候一定都被元素下标折磨过,为什么很多编程语言要把 0 作为第一个下标索引,而不是直观的 1 呢?

这个问题 Dijkstra 已经解答过了,没错,就是你知道的 Dijkstra,Dijkstra 最短路径算法,荷兰语全名是 Edsger Wybe Dijkstra,于 1972 年获得了图灵奖,除了上面说的最短路径算法,还有众所周知的信号量和 PV 原语、银行家算法等也是这位巨佬提出的。

原文在这里:https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html,感兴趣的小伙伴可以去看下全文,下面我总结几段核心的观点:

首先来看个案例,如何用一个不等式(或者说表达式)来表示 [2,3,4,5,6,7,8,9,10,11,12] 这个连续的整数序列(一共 11 个数)?

假设 i 是一个整数,那么我们能够迅速的写出如下四个符合上述连续序列的不等式:

1)2 <= i < 13

2)1 < i <= 12

3)2 <= i <= 12

4)1 < i < 13

以上四个不等式均满足要求,那是否有理由选择其中的一种而不是另一种?

Dijkstra 说有的,选 1 和 2,因为这俩不等式有个很突出的有点,就是不等式边界的差(不等式右边 - 不等式左边)正好等于连续序列的长度

这里可以排除掉 3 和 4,那么 1 和 2 该如何选出最优的表示?

1 和 2 不等式的区别就在于:

  • 1 不等式左边(下界)等于序列中的最小值,不等式右边(上界)大于序列中的最大值
  • 2 不等式左边(下界)小于序列中的最小值,不等式右边(上界)等于序列中的最大值

对于第 2 个不等式来说,下界小于序列中的最小值,这会出现一个问题,比如我们的连续序列是 [0,1,2,3,4]

那么按照第 2 个不等式的写法,不等式的左边就是 -1,-1 是非自然数,而我们需要表示的连续序列是自然数序列,所以第 2 个不等式很不优雅:我们需要用一个 非自然数 来作为 全是自然数的序列 的下界

因此,综上所述,不等式 1 是最优雅的选择。

那么,选出一个看着非常顺眼的不等式来表达长度为 N 的连续序列之后,下一个令人烦恼的问题是该为起始元素分配什么下标值?

遵循不等式 1 的规则:

  • 当从下标 1 开始时,下标范围 1 ≤ i < N+1
  • 当从下标 0 开始时,下标范围 0 ≤ i < N

哪个更优雅?

Dijkstra 是这样解释的:从下标 0 开始能够给出更好的不等式,因为元素的下标就等于序列中它前面的元素数(或者说 “偏移量”)。

问题解决!文末贴上巨佬 Dijkstra 的手稿:

🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~

帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10
爽文一篇:没有先例那就给我开先例!十天时间拿到 n+1 赔偿
面试官再跟你说中国没有根服务器,雪人计划让他了解下

← 爽文一篇:没有先例那就给我开先例!十天时间拿到 n+1 赔偿 面试官再跟你说中国没有根服务器,雪人计划让他了解下→

最近更新
01
02
线上环境 CPU 使用率飙升如何快速排查?
03-05
03
面试官再跟你说中国没有根服务器,雪人计划让他了解下
02-23
更多文章>
Theme by Vdoing | Copyright © 2019-2023 飞天小牛肉 | 皖ICP备2022008966号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式