当前位置:首页 > 新闻中心 > 公司新闻

如何设计出精巧的数据结构?

发布时间: 2021-09-22 04:51:33  来源:火狐平台开户 

  首先设计好接口,然后编写单元测试。如面对新的功能或性能需求,可重构数据结构实现,而重构的必要条件就是有单元测试。如果考虑到性能的话,当然也需要自动化的性能测试。

  想好你需要记录哪些信息,用户代码会如何用它,并检查它所对应的状态机是否完整。同时在适当情况下将复杂数据结构拆分成多个简单的数据结构

  从题目描述来看,当前的问题主要是第一种,但也无法排除题主是因为后两种原因导致了其总需要在当前数据结构上修修补补进才使得数据结构出现了冗余

  首先要说的是,冗余不见得不好,但是有成本。假如用户代码使用一个链表的时候常常需要获得当前链表的长度,那么在链表的数据结构中记录当前链表的长度就是一个好的idea。我们可以注意到,这就是一种冗余。但是相较于每次访问长度时我们都需要遍历一次链表来求得长度,这个辅助变量,也就是冗余会大大地加快运行速度。添加这个变量不好的地方就是,我们需要对插入结点,删除结点等一系列操作中维护这个变量,以使得它记录的值是对的。也就是对状态机的维护(这句有点儿不太准确)

  那么一旦添加新的成员函数,比如merge()函数合并两个链表,那么我们就需要在该函数的实现中对该冗余变量进行维护。如果一个数据结构中有m个变量,n个方法,那么就是m乘n的工作量。当m和n比较大时,这个数据结构就容易失控

  所以说,首先,我们要想好记录哪些信息,包括冗余信息,以及我们需要为这个数据结构暴露什么功能。每一份信息,也就是数据,都有清晰独立的意义,并不会轻易改变。同时功能也不能改变,毕竟功能变来变去为内部信息所制定的规则也需要变来变去,最终导致原本清晰的意义揉杂在了一起。一旦定义完毕,那么检查各个操作所可能导致的状态变化是否可以通过数据结构中的各个数据完整地表示出来

  有一种常出现的问题就是一个数据结构里面存在着太多的变量,这些变量之间有一些是紧密关联的,有一些则是完全不相关的。这时候要考虑是否将紧密关联的各变量抽取成为较小的数据结构

  一切数据结构皆CURD,目前来看主要优化R和C,也就是查找和插入,结合一些计算机底层知识你也可以做Btree(HDD)或者LSMTree(优化写),SkipList(log查询链表),RBTree(HashMap的链表之类的东西啦

  这个问题,并不是一篇文章或一本书就能说清楚的,需要对特定问题深入的分析和大量的练习,建议多看一些成熟的协议,这些协议中的数据结构基本都很精巧,总结吸收里面面对问题的设计思想和技巧。核心是:简练、清楚明白。

  比如 iCalendar RFC 5545中怎样准确标识一个事务,怎样处理一个事务的循环.....

  好的习惯是:概要设计应一定要清晰、简练,不求完备,根据问题,实现其基础目的,构建一个清晰、简练、坚实的基础数据结构,命名准确易懂,合乎逻辑。

  后续不断地补充丰满时,辅助的数据结构可能越来越多,最重要的是保持一个清晰的结构,让人清晰地理解、明白。

  有些时候难以避免重复和冗余,甚至是主动利用重复和冗余来交换速度(包括开发速度),这不可怕,关键在于结构上不能过于复杂、混乱,导致这些重复和冗余不能被快速准确地被识别和理解。

  数据结构的设计,是一个熟能生巧的过程,最开始设计的时候,因为经验的问题,往往考虑的不够全面。

  数据结构现在还是要自己设计的?我理解一般都是对现有的数据结构进行使用或者组合使用。每个数据结构都有各自的优劣,操作一般都是读取(搜索),增加元素,删除元素。各自的效率都有不同,就看自己的业务需求是怎么样,然后按需采用就可以了。估计现在已经没有人能“发明”一种全新的数据结构了。