似乎计算机数据结构中存在一个明显的“技术断层”?

2020-04-15 09:01:22 +08:00
 abcbuzhiming
计算机的数据结构这个东西,看起来东西不多,但是里面有一些很突兀的存在。绝大部分书也好,教程也好,介绍数据结构的时候,套路都是 数组 链表 Map(table) ,队列,栈。然后就会出现两个画风(难度)和之前的东西截然不同的存在——树和图。
我搞这行的时间也不算短了,也接触了不少人,发现 树和图 对于大部分人来说都是难以理解的存在,包括我自己也是。不是说他们的表现形式难以理解,而是指附加其上的计算行为,很复杂,有多重变种。和在他们之前的那些数据结构比起来,感觉他们的复杂度猛然抬了个台阶起来。非常的显眼而且突兀。
我注意到这点越久,就越怀疑这两个东西存在的“合理性”,他们就像塞进耗子窝里的大象那么显眼。这中间是不是缺少了什么,我们知道计算机的一切往上追溯都来自于数学,数学能解释这两个东西如此突兀的现象吗,还是说历史埋葬了一些东西,在 树和图 之前其实存在某些“前置科技”,只是因为种种原因,“前置科技”的功能被后来者覆盖了,就消失在历史长河里了
16379 次点击
所在节点    程序员
136 条回复
XenoAmess
2020-04-15 15:18:39 +08:00
你把链,做成多子节点 不就成了树?
这是个非常自然的过程啊。
归根结底还是你归纳总结能力不足。
janxin
2020-04-15 15:27:12 +08:00
没有吧,其实是一种扩展关系
oshio
2020-04-15 16:00:45 +08:00
@ipwx 没错,教材不可能包括这些内容,但相关的资料应该还是有的。直接读论文对我来说有点太难了,对我来说科普读物就能解决大部分疑惑,比如微积分就有《微积分的历程》,就是不知道有没有类似的算法的历程这样的资料,当故事读读也挺好的。

对一个智力正常的人来说,一个东西难以理解可能是真的很难,比如说量子力学;也可能是步子迈的太大,缺乏必要的基础,比如说小学没学完就学微积分。我们教科书上的算法,基本上应该是第二类,觉得难以理解不是因为它已经达到人类智力的极限(毕竟绝大多数都是几百年前数学家研究透了的东西里面最简单的部分了),而是我们缺了一些中间过程,补上这些就能更好的理解了。
calpes
2020-04-15 16:09:43 +08:00
缺乏现实中理解指数型问题的经验。
IGJacklove
2020-04-15 16:14:10 +08:00
这两个确实一般程序员都接触不到,尤其是图,大部分程序员基本都接触不到
otakustay
2020-04-15 16:19:40 +08:00
我觉得大的断层是堆和图
然后树内部也有断层,普通树和平衡树
GrayXu
2020-04-15 16:20:25 +08:00
请问链表难道不是一种特殊的树形式?
别啥前置科技了,整的跟民科似的
GrayXu
2020-04-15 16:23:50 +08:00
翻了一遍评论,认为真的有这种断层的朋友们,你们是怎么去理解更复杂的算法和数据结构的(字典树、线段树)。。
还是多多读书和论文吧,感觉这个问题还是学的少导致的…
zzhzero
2020-04-15 16:28:56 +08:00
无外乎是顺序储存和链式储存的不同应用而已 有这种疑惑是好事 去书里面找答案吧
lidlesseye11
2020-04-15 16:52:42 +08:00
我觉得楼主所谓的断层不是数据结构,而是应用于其之上的算法

楼上那么多说“树就是进化后的链表”的,serious ?(可能 V 站真的就是大佬多吧┑( ̄Д  ̄)┍

树的结构,即使不是学计算机的,也都有“朴素”的理解。

但是一说到比如红黑树的实现,说实话我到现在也是懵逼的。。。
只是对照着定义撸出来就很麻烦了,更不要说自己证明或者“推导”出来了(此处求问大佬们有没有好的教材。。
ipwx
2020-04-15 16:59:42 +08:00
红黑树、KMP 、BM,堪称入门级数据结构和算法教材最难学会的东西。不是因为概念太难,而是因为优化到极致,所以琐碎的东西太多了。。。

概念上不就是平衡树和自动机么。。。
tairan2006
2020-04-15 19:18:41 +08:00
树退化一下就是链表啊,你这数学学的半桶水的别自己瞎想了…
levelworm
2020-04-15 20:40:06 +08:00
@ipwx 作为一个非科班也不准备靠这个吃饭纯粹自学着玩的人来说,自平衡树我觉得是一道坎,之前的都很轻松,之后的困难一些。我因为没啥需求,到现在也没学超过自平衡树。。。

我觉得这道坎可能在于智商不足。之前的结构都能理解,但是自平衡树的那些旋转,没法直观的理解,又没能力从数学上证明,所以就弃疗了。

不过好在似乎想写的东西基本上不需要什么复杂的结构和算法,都是玩具反正。
akira
2020-04-15 21:20:05 +08:00
一根树枝长了个分叉就不认识了啊。。
CoderGeek
2020-04-15 21:21:50 +08:00
说实话 我之前准备考研 树还好 图那块有点突兀 不过专心还好
msaionyc
2020-04-15 21:29:05 +08:00
多学习吧
brickxu
2020-04-15 21:32:59 +08:00
建议去离散数学中寻找你所谓的“断层”的答案。

BTW,“我搞这行的时间也不算短了”,你这句话等于把自己底裤都漏出来了。
bspp
2020-04-15 23:04:14 +08:00
@lidlesseye11 去网易云公开课搜平衡搜索树 非常好的讲解
abcbuzhiming
2020-04-15 23:34:30 +08:00
@brickxu 我没觉得露底裤有啥不行的,每个人都有自己的极限,藏着掖着反而不利于自己进步,你看我主动暴露自己的弱点不就引来了一大堆牛人吗。至少我今天真的知道了一个方向:也许离散数学里有答案
greenlake
2020-04-15 23:46:49 +08:00
我觉得计算机科学的基础研究没什么大变化,几十年前的数据结构大概就是这样了,但是应用层面大量的变化改变了我们的生活。就像基础物理一样,多少年没什么大变化,人类 60 年代还去过月球,现在呢?

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://tanronggui.xyz/t/662507

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX