在真实世界中重新实现数据结构

了解数据结构是如何实现和可以实现的肯定是每个人都感兴趣的,而不仅仅是学术界。如果语言已经提供了具有适当功能和性能特征的实现,则很可能不会重新实现数据结构,但很可能必须通过组合其他数据结构来创建自己的数据结构。。。或者,您可能需要实现与已知数据结构稍有不同的行为的数据结构。在这种情况下,您当然需要知道原始数据结构是如何实现的。或者,您可能最终需要一个不存在的数据结构,或者它提供了与现有数据结构类似的行为,但是使用它的方式要求对一组不同的函数进行优化。同样,这种情况需要您知道如何实现(和更改)数据结构,所以是的,这是有意义的。

编辑
我是 不提倡重新实现现有的数据结构 ! 别那么做。我要说的是,这些知识确实有实际应用价值。例如,您可能需要创建一个双向映射数据结构(可以通过组合两个单向映射数据结构来实现),或者您可能需要创建一个跟踪各种统计信息的堆栈(例如min、max,通过使用包含值的元素类型以及这些不同的统计数据,使用现有的堆栈数据结构。这些是一些在现实世界中可能需要实现的琐碎的例子。

我已经多次重新实现了语言的一些内置数据结构、函数和类。作为一个嵌入式开发人员,我这么做的主要原因是为了速度或效率。标准库和类型被设计成在各种情况下都很有用,但是在很多情况下,我可以创建一个定制的更专业的版本,以利用当前平台的特性和限制。如果语言没有提供一种打开和修改现有类的方法(例如,在Ruby中可以使用),那么重新实现类/函数/结构可以是唯一的方法。

例如,我工作的一个系统使用MIPS CPU,在处理32位数字时速度很快,但在处理较小的数字时速度较慢。我重新编写了几个数据结构和函数,以使用32位整数而不是16位整数,并指定字段与32位边界对齐。结果是一段代码的速度明显提高,这段代码阻碍了软件的其他部分。

尽管如此,这不是一个微不足道的过程。最后,我不得不修改使用该结构的每个函数,最后还不得不重新编写几个标准库函数。在这种情况下,收益大于工作。不过,在一般情况下,这通常是不值得的麻烦。很有可能出现难以调试的问题,而且几乎总是比看起来的要多。除非您有特定的要求或限制,现有的结构/类不符合,我建议不要重新实施它们。

正如迈克尔所说,知道 怎样 重新实现结构,即使您从未这样做过。您可能会发现未来的问题,可以通过应用现有数据结构中使用的原理和技术来解决。