为什么要在数组O(1)中查找?

黑鬼

我相信在Ruby以外的其他语言中,数组查找为O(1),因为您知道数据从哪里开始,然后将索引乘以数组所保存的数据大小,然后访问该内存位置。

但是,在Ruby中,数组可以具有来自不同类的对象,那么它如何管理O(1)复杂度呢?

丹·伦斯基

@Neil Slater所说的,还有更多细节……

基本上有两种可行的方法来存储大小不同的异构对象的数组:

  1. 将对象存储为单链接列表或双链接列表,每个对象的存储空间前面都有指向前一个和/或后一个对象的指针。这种结构的优点是可以很容易地在任意点插入新对象而无需在数组的其余部分移动,但是巨大的缺点是,按位置查找对象通常是O(N),因为您必须从一端开始列表并逐个跳转,直到到达第n个。

  2. 存储指向各个对象的大小恒定的表或数组。由于此查找表以连续的有序布局包含大小固定的项目,因此查找单个对象的地址O(1)该表只是一个C样式的数组,即使在RISC CPU体系结构上,查找也只需要很少的一对多机器指令。

(用于存储单个对象的分配策略也很有趣且复杂,但与您的问题并不直接相关。)

诸如Perl / Python / Ruby之类的动态语言几乎都选择了#2作为通用列表/数组类型。换句话说,与在列表中的随机位置插入对象相比,它们使查找更为有效,这对于许多应用程序来说是更好的选择。

我不熟悉Ruby的实现细节,但它们可能与Pythonlist类型的实现细节非常相似,effbot.org上详细介绍了其性能和设计

本文收集自互联网,转载请注明来源。

如有侵权,请联系[email protected] 删除。

编辑于
0

我来说两句

0条评论
登录后参与评论

相关文章

来自分类Dev

为什么我需要在数组中附加一个 NUL 字符?

来自分类Dev

为什么表达式需要在数组的括号中

来自分类Dev

为什么要在固定时间内完成对数组中任何单个元素的访问(O(1))?

来自分类Dev

为什么要在数据库中创建视图?

来自分类Dev

为什么要在数据设计中维护双向指针?

来自分类Dev

为什么要在数组中为var返回一个字符串索引?

来自分类Dev

我的程序不会输出我输入要在数组中搜索的第一个值。为什么?

来自分类Dev

为什么要在数组映射回调中放入异步等待?

来自分类Dev

在数组中查找数字的最佳实践是什么?

来自分类Dev

在数组中查找元素的最佳方法是什么?

来自分类Dev

为什么 numpy.where 在尝试在数组中查找 None 元素时“== None”和“is None”的行为不同?

来自分类Dev

为什么要在选择排序算法中存储数组的长度?

来自分类Dev

为什么要在JS中推送数组引用而不是PHP

来自分类Dev

在数组中查找索引

来自分类Dev

在数组中查找模式

来自分类Dev

在数组中查找值

来自分类Dev

在数组中查找项目

来自分类Dev

在数组中查找键

来自分类Dev

在数组中查找smarty

来自分类Dev

mongodb 在数组中查找

来自分类Dev

在数组数组中查找丢失的数组

来自分类Java

为什么自动装箱在数组中不起作用?

来自分类Javascript

为什么在数组中向后迭代比向前快

来自分类Dev

为什么存储在数组中的双精度值消失了?

来自分类Dev

为什么我的变量不在数组中打印?HTML

来自分类Dev

为什么 javascript 'For' 语句不能在数组中工作?

来自分类Dev

为什么要在解决方案中添加+1

来自分类Dev

为什么要在数据库中插入JPA空值

来自分类Dev

为什么要在JavaScript中的JSON对象数组中创建额外的数组数组

Related 相关文章

  1. 1

    为什么我需要在数组中附加一个 NUL 字符?

  2. 2

    为什么表达式需要在数组的括号中

  3. 3

    为什么要在固定时间内完成对数组中任何单个元素的访问(O(1))?

  4. 4

    为什么要在数据库中创建视图?

  5. 5

    为什么要在数据设计中维护双向指针?

  6. 6

    为什么要在数组中为var返回一个字符串索引?

  7. 7

    我的程序不会输出我输入要在数组中搜索的第一个值。为什么?

  8. 8

    为什么要在数组映射回调中放入异步等待?

  9. 9

    在数组中查找数字的最佳实践是什么?

  10. 10

    在数组中查找元素的最佳方法是什么?

  11. 11

    为什么 numpy.where 在尝试在数组中查找 None 元素时“== None”和“is None”的行为不同?

  12. 12

    为什么要在选择排序算法中存储数组的长度?

  13. 13

    为什么要在JS中推送数组引用而不是PHP

  14. 14

    在数组中查找索引

  15. 15

    在数组中查找模式

  16. 16

    在数组中查找值

  17. 17

    在数组中查找项目

  18. 18

    在数组中查找键

  19. 19

    在数组中查找smarty

  20. 20

    mongodb 在数组中查找

  21. 21

    在数组数组中查找丢失的数组

  22. 22

    为什么自动装箱在数组中不起作用?

  23. 23

    为什么在数组中向后迭代比向前快

  24. 24

    为什么存储在数组中的双精度值消失了?

  25. 25

    为什么我的变量不在数组中打印?HTML

  26. 26

    为什么 javascript 'For' 语句不能在数组中工作?

  27. 27

    为什么要在解决方案中添加+1

  28. 28

    为什么要在数据库中插入JPA空值

  29. 29

    为什么要在JavaScript中的JSON对象数组中创建额外的数组数组

热门标签

归档