gpt4 book ai didi

objective-c - 我如何理解 Cocoa 库类中的性能权衡?

转载 作者:行者123 更新时间:2023-12-03 17:21:27 25 4
gpt4 key购买 nike

今天有人问我,如果该字典包含 1,000,000 个元素,那么 NSMutableDictionary 插入需要多长时间。我没有计算机科学背景,所以完全不知道。我很惊讶地发现它在(我现在理解为)O(n) 时间内完成。伟大的。太棒了。

有人怎么可能确切地知道这一点?

显然,人们可以针对每个 Cocoa 类编写数十个测试并绘制出所有时间数据。当我有几周的空闲时间时,我一定会抽出时间来解决这个问题。排除所有这些......

  • 这对于计算机科学专业的人来说是不是太明显了?背景?
  • Apple 是否发布了解释文档这个?
  • 他的知识是否意味着他是一台计算机科学专家,他自己测试发现了这一点吗?

最佳答案

您所询问的内容称为 "complexity" of an algorithm 。它与语言无关; NSDictionary 时间复杂度与任何其他关联字典(例如 C++ std::map)没有什么不同。但是,这并不意味着填充某些对象的 NSDictionary 保证能够执行 insertsearch删除操作的速度与std::map一样快;这意味着执行这些操作所花费的时间是线性 (O(n)),在最坏的情况下,与元素的数量相关( em>n O(n)) 的一部分。字典插入可能 O(1),这是常数时间(操作花费相同的时间,与字典中的元素数量无关)如果没有哈希碰撞。

NSDictionary 使用的“算法”称为 Hash Table 。哈希表通过对输入进行哈希处理(恒定时间操作)来进行插入,然后解决冲突,这是一个 O(n) 操作。希望您能够看到,在最坏的情况下,所有您的插入操作都会发生冲突,即 O(n)。

表/哈希算法当然可以专门用于减少特定数据集中的冲突,但 NSDictionary 仅使用键的对象 hash 方法 对象,如果您需要某种特化(可能不需要),您可以为您的 NSObject 子类覆盖这些对象。

由于它是一个通用字典,并不专门针对特定的数据集,因此我们不一定需要了解 NSDictionary 的实现细节(Apple 的 documentation for NSDictionary 没有提及具体细节)知道这些操作将是 O(n)。我们也不必运行“测试”来发现复杂性。

关于objective-c - 我如何理解 Cocoa 库类中的性能权衡?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25483563/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com