cocoa - NSDictionary、NSArray、NSSet 和效率

Question

我有一个文本文件，大约有 200,000 行。每条线代表一个具有多个属性的对象。我只搜索对象的属性之一(唯一 ID)。如果我要查找的唯一 ID 与当前对象的唯一 ID 相同，我将读取该对象的其余值。

现在，每次我搜索一个对象时，我只是逐行读取整个文本文件，为每一行创建一个对象，然后看看它是否是我正在寻找的对象 - 这基本上是最低效的方法进行搜索。我想将所有这些对象读入内存，以便以后可以更有效地搜索它们。

问题是，执行此类搜索的最有效方法是什么？ 200,000 个条目的 NSArray 是执行此操作的好方法吗(我对此表示怀疑)？ NSSet 怎么样？使用 NSSet 是否可以只搜索对象的一个​​属性？

感谢您的帮助!

-- 瑞

Answer 1

@yngvedh 是正确的，因为 NSDictionary 的查找时间为 O(1)(正如映射结构所预期的那样)。然而，经过一些测试，您可以看到 NSSet 的查找时间也为 O(1)。这是我为此所做的基本测试:http://pastie.org/933070

基本上，我创建 1,000,000 个字符串，然后计算从字典和集合中检索 100,000 个随机字符串所需的时间。当我运行几次时，该集实际上看起来更快......

dict lookup: 0.174897
set lookup: 0.166058
---------------------
dict lookup: 0.171486
set lookup: 0.165325
---------------------
dict lookup: 0.170934
set lookup: 0.164638
---------------------
dict lookup: 0.172619
set lookup: 0.172966

就您的具体情况而言，我不确定这是否是您想要的。您说您希望将所有这些对象都存储在内存中，但是您真的需要它们全部，还是只需要其中的一些对象？如果是后者，那么我可能会通读该文件并创建一个对象 ID 到文件偏移映射(即，记住每个对象 ID 在文件中的位置)。然后，您可以查找所需的内容，并使用文件偏移量跳转到文件中的正确位置，解析该行，然后继续。这是 NSFileHandle 的工作。