xcr*_*ypt 3 memory data-structures
我很确定这是一个愚蠢的新手问题,但我不知道,所以我不得不问...
为什么我们使用数据结构,如链接列表,二进制搜索树等？(当不需要动态分配时)
我的意思是:如果我们为单个对象保留一个变量,它会不会更快？这不会加快访问时间吗？例如:BST可能必须首先运行一些指针才能获得实际数据.
除了需要动态分配的时候,是否有理由使用它们？
例如:在可以使用简单(非动态)数组的情况下使用链表/ BST/std :: vector.
每次你存储的东西是被关在它自己的变量(或存储位置).数据结构将组织应用于您的数据.想象一下,如果你有10,000件事你试图跟踪.您可以将它们存储在10,000个单独的变量中.如果你这样做,那么你总是被限制在10,000种不同的东西上.如果你想要更多,你必须修改你的程序,并在每次想要增加数量时重新编译它.如果项目的顺序发生变化,您可能还必须修改代码以更改计算的完成方式,因为新的项目是在中间引入的.
使用数据结构,从简单数组到更复杂的树,哈希表或自定义数据结构,可以使代码更加有条理和可扩展.使用一个数组,可以创建数组以保存所需数量的元素,也可以在第一次创建后扩展以容纳更多元素,这样每次数据项数量发生变化时都不必重写代码.使用适当的数据结构允许您根据数据元素之间的关系而不是某些固定顺序设计算法,从而为您提供更大的灵活性.
一个简单的类比可能有助于理解.例如,您可以将所有重要文件放入单独的文件柜中来组织所有重要文件.如果你这样做,你必须记住(即硬编码)可以找到每个项目的文件柜,以便有效地使用它们.或者,您可以将每个存储在同一个文件柜中(如通用阵列).这是更好的,因为它们都在一个地方,但仍然不是最佳的,因为你每次想要找到它时都必须搜索它们.更好的是按主题组织它们,将相同的主题放在同一个文件夹中(单独的数组,不同的结构).这样,您可以查找正确主题的文件夹,然后找到您要查找的项目.根据您的需要,您可以使用不同的归档方法(数据结构/算法)来更好地组织您的信息以满足其预期用途.
我还会注意,有次当它是有意义的使用单个变量为你使用的每个数据项.通常,根据特定项目的使用,使用适当的方法将各个变量和更复杂的结构混合在一起.例如,您可以将整数集合的总和存储在变量中,而整数本身存储在数组中.虽然在引入数据结构之前不合适,但程序需要非常简单.
小智 5
抱歉，您不仅找到了一种很棒的新做事方式 ;)这种方法存在几个大问题。
如何在不要求程序员在允许的项目数量发生变化时立即大量（且非平凡地）重写大量代码的情况下做到这一点？即使您必须在编译时修复数据结构的大小（例如 C 中的数组），您也可以使用常量。然后，更改单个常量并重新编译就足以更改该大小（如果编写代码时考虑到了这一点）。使用您的方法，每次更改某些大小时，我们都必须键入数百甚至数千行。更不用说所有这些代码都非常难以阅读、编写、维护和验证。在这样的设置中，老生常谈“更多的代码行 = 更多的错误空间”被占用了 11 行。
还有一个事实是，这个数字几乎从来没有一成不变。即使它是编译时常量，仍然可能发生更改。为次要的（如果存在的话）性能提升编写数百行代码几乎是不值得的。如果每次要更改某些内容时都必须再次执行相同数量的工作，则此操作会重复三次。且不说，不可能在所有一旦有数据结构的尺寸的任何远程动态分量。也就是说，这是很少可能的。
还要考虑隐式和简洁数据结构的概念。如果您使用一组硬编码变量而不是对大小进行抽象，您仍然会得到一个数据结构。你只是让它隐含，展开在它上面运行的算法，并确定它的大小。从哲学上讲，你什么都没有改变。
但它肯定有性能优势吗？嗯，有可能，虽然它会很小。但不能保证它在那里。您可以节省一些数据空间，但代码大小会爆炸。并且每个了解内联的人都应该知道，较小的代码大小对于允许代码在缓存中的性能非常有用。此外，参数传递会导致过度复制，除非您想出一个技巧来从几个指针派生出大多数变量的位置。毋庸置疑，这将是不可移植的，即使在单个平台上也很难做到正确，并且容易被代码或编译器调用的任何更改所破坏。
最后，注意较弱的形式是，有时做。关于隐式和简洁数据结构的维基百科页面有一些例子。在较小的规模上，一些数据结构将大量数据存储在一个地方，这样可以通过较少的指针追逐来访问它并且更有可能在缓存中（例如缓存感知和缓存遗忘数据结构）。它对 99% 的代码都是不可行的，将其发挥到极致只会增加一点点好处，如果有的话。