知识卡片

普通读书笔记卡 · 1292.g.1.b.1 · 生成模型:未记录

查找结构按查询与更新权衡

理解等级:中级

存在性查询回答目标是否存在;检索查询返回匹配元素;关联查找由键获得附加信息。设计接口时应明确匹配规则、重复键行为以及未找到如何表示,避免把合法值与缺失哨兵混淆。

索引或排序可加速某些查询,但建立、插入、删除和额外空间均有成本;应按查询频率、更新频率、随机访问能力和数据量一起选择结构。

112指出无序链表头插在已持有头指针时为常数操作;尾插需有尾指针,删除给定值通常先线性查找,而已持有合适节点或前驱时删除成本可以不同。数组扩容与移动也要计入总体工作量。

120指出有序数组便于二分查找,插入和删除可能移动 O(n) 元素;动态树等结构可以调整更新与查询成本,但具体界依赖平衡策略和实现。

122指出磁盘数据也可以按偏移读取,但单次随机读取、缓存与记录长度影响延迟;页式索引等结构可能减少外部存储访问,不应只比较内存中的比较次数。

130强调需要结合输入的静态或动态性质选择存储结构;查找快慢还要包括冲突处理和容量管理。

301与03468–03469图算法表强调优先队列及结构操作成本;二叉堆可取最小,但一般成员查询是线性时间,可额外维护索引或使用其他结构。不存在仅凭选择数据结构就使任意问题达到 O(n log n) 的普遍保证。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 6 处

    • · 查看原书依据

      存在性查询:C包含一个目标元素t吗? 很多时候我们只想知道一个给定集合C中是否包含一个特定的值t。如果这样的元素存在并且其值和t相等,那么这个查询的结果将是真,否则的话就是假。 检索查询:返回C中值和t匹配的元素。 当复杂的元素存储在该集合时,元素匹配的定义是基于键值或者元素的属性集合的子集匹配。例

    • · 查看原书依据

      查找次数来看,顺序查找也许是最有效的查找算法。如果n相当低效,或者你不经常执行查找操作,那么对元素排序或者使用一个复杂的数据结构将得不偿失。 如果集合是无序的,并且是以链表的形式存储的,那么插入元素是一个常数时间的操作(仅仅简单地插入到表头或者表尾)。频繁地插入到一个数组形式存储的集合需要动态的数组

    • · 查看原书依据

      添加或者移除元素,这个方法就变得非常笨拙。你可以使用很多数据结构,最著名的一个是二叉树,将在“变种”中讨论。

    • · 查看原书依据

      二级存储器中,例如在磁盘上以文件的形式。在这种情况下,第i个元素能够根据其在文件中的偏移量来存取。如果使用二级存储器,查找一个元素所需要的时间就主要是存取二级存储器所需要的开销,其他和二分查找相关的解决方案也适用。参考算法的“变种”一节,其中对这些问题进行了处理。

    • · 查看原书依据

      动态性质是非常必要的,这有助于选择合适的数据结构。

    • · 查看原书依据

      选择正确的数据结构 著名算法设计者Robert Tarjan曾经引用过这样一句话:“如果使用正确的数据结构,任何问题都能够在O(n log n)的时间内解决掉”。许多算法需要使用有限队列来存储中间过程或者下一步运算。实现优先队列最常见的要数二叉堆了,它能够在O(log n)的时间内从优先队列中将最低

    参考来源

    - 位置:《算法技术手册》第5章《概述》(spine1531;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1494.html;u108-ch05-001)。 - 结论依据:108全文实读。 - 原始内容:存在性查询:C包含一个目标元素t吗? 很多时候我们只想知道一个给定集合C中是否包含一个特定的值t。如果这样的元素存在并且其值和t相等,那么这个查询的结果将是真,否则的话就是假。 检索查询:返回C中值和t匹配的元素。 当复杂的元素存储在该集合时,元素匹配的定义是基于键值或者元素的属性集合的子集匹配。例 - 位置:《算法技术手册》第5章《驱动因素》(spine1534;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1497.html;u112-ch05-001)。 - 结论依据:112指出无序链表头插在已持有头指针时为常数操作;尾插需有尾指针,删除给定值通常先线性查找,而已持有合适节点或前驱时删除成本可以不同。数组扩容与移动也要计入总体工作量。 - 原始内容:查找次数来看,顺序查找也许是最有效的查找算法。如果n相当低效,或者你不经常执行查找操作,那么对元素排序或者使用一个复杂的数据结构将得不偿失。 如果集合是无序的,并且是以链表的形式存储的,那么插入元素是一个常数时间的操作(仅仅简单地插入到表头或者表尾)。频繁地插入到一个数组形式存储的集合需要动态的数组 - 位置:《算法技术手册》第5章《驱动因素》(spine1541;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1504.html;u120-ch05-001)。 - 结论依据:120指出有序数组便于二分查找,插入和删除可能移动 O(n) 元素;动态树等结构可以调整更新与查询成本,但具体界依赖平衡策略和实现。 - 原始内容:添加或者移除元素,这个方法就变得非常笨拙。你可以使用很多数据结构,最著名的一个是二叉树,将在“变种”中讨论。 - 位置:《算法技术手册》第5章《结论》(spine1543;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1506.html;u122-ch05-001)。 - 结论依据:122指出磁盘数据也可以按偏移读取,但单次随机读取、缓存与记录长度影响延迟;页式索引等结构可能减少外部存储访问,不应只比较内存中的比较次数。 - 原始内容:二级存储器中,例如在磁盘上以文件的形式。在这种情况下,第i个元素能够根据其在文件中的偏移量来存取。如果使用二级存储器,查找一个元素所需要的时间就主要是存取二级存储器所需要的开销,其他和二分查找相关的解决方案也适用。参考算法的“变种”一节,其中对这些问题进行了处理。 - 位置:《算法技术手册》第5章《结果》(spine1550;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1513.html;u130-ch05-001)。 - 结论依据:130强调需要结合输入的静态或动态性质选择存储结构;查找快慢还要包括冲突处理和容量管理。 - 原始内容:动态性质是非常必要的,这有助于选择合适的数据结构。 - 位置:《算法技术手册》第11章《原则:选择正确的数据结构》(spine1688;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1650.html;u301-ch05-001)。 - 结论依据:301与03468–03469图算法表强调优先队列及结构操作成本;二叉堆可取最小,但一般成员查询是线性时间,可额外维护索引或使用其他结构。不存在仅凭选择数据结构就使任意问题达到 O(n log n) 的普遍保证。 - 原始内容:选择正确的数据结构 著名算法设计者Robert Tarjan曾经引用过这样一句话:“如果使用正确的数据结构,任何问题都能够在O(n log n)的时间内解决掉”。许多算法需要使用有限队列来存储中间过程或者下一步运算。实现优先队列最常见的要数二叉堆了,它能够在O(log n)的时间内从优先队列中将最低