6

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

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

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

谢谢你的帮助！

-- 瑞

4

3 回答 3

13

@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。

于 2010-04-24T16:53:55.657 回答
5

使用 NSDictionary 从 ID 映射到对象。即：以ID为key，以对象为value。NSDictionary 是唯一支持高效键查找的集合类。（或根本查找键）

字典是一种不同于其他集合类的集合。它是一个关联集合（在您的情况下将 ID 映射到对象），而其他集合只是多个对象的容器。NSSet 保存无序的唯一对象， NSArray 保存有序对象（可能保存重复）。

更新：

为避免在阅读条目时重新分配，请使用该dictionaryWithCapacity:方法。如果您在阅读条目之前知道（大约）条目数，则可以使用它来预先分配足够大的字典。

于 2010-04-24T10:36:02.867 回答
4

200,000 个对象听起来可能会遇到内存限制，具体取决于对象的大小和目标环境。您可能要考虑的另一件事是将数据转换为 SQLite 数据库，然后索引您要查找的列。这将在效率和资源消耗之间提供良好的折衷，因为您不必将整个集合加载到内存中。

于 2010-04-24T16:58:01.607 回答