NSDictionary，NSArray，NSSet和效率 [英] NSDictionary, NSArray, NSSet and efficiency

问题描述

我有一个文本文件，大约有20万行。每行代表一个具有多个属性的对象。我只搜索对象的属性（唯一ID）之一。如果我正在寻找的唯一ID与当前对象的唯一ID相同，我将读取对象的其余值。

I've got a text file, with about 200,000 lines. Each line represents an object with multiple properties. I only search through one of the properties (the unique ID) of the objects. If the unique ID I'm looking for is the same as the current object's unique ID, I'm gonna read the rest of the object's values.

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

Right now, each time I search for an object, I just read the whole text file line by line, create an object for each line and see if it's the object I'm looking for - which is basically the most inefficient way to do the search. I would like to read all those objects into memory, so I can later search through them more efficiently.

问题是，什么是最有效的方式来执行这样的搜索？是一个200,000条目NSArray是一个很好的方法来做到这一点（我怀疑）？ NSSet如何？使用NSSet，是否只能搜索对象的一个​​属性？

The question is, what's the most efficient way to perform such a search? Is a 200,000-entries NSArray a good way to do this (I doubt it)? How about an NSSet? With an NSSet, is it possible to only search for one property of the objects?

感谢任何帮助！

-Ry

推荐答案

@yngvedh是正确的，因为 NSDictionary 具有O（1）查找时间（如对于映射结构所期望的）。然而，在做了一些测试后，你可以看到 NSSet 也有O（1）查找时间。以下是我所做的基本测试： http://pastie.org/933070

@yngvedh is correct in that an NSDictionary has O(1) lookup time (as is expected for a map structure). However, after doing some testing, you can see that NSSet also has O(1) lookup time. Here's the basic test I did to come up with that: http://pastie.org/933070

基本上，我创建了1,000,000个字符串，然后是我从字典和集合中检索100,000个随机字符串所需的时间。当我运行这几次，设置实际上似乎更快...

Basically, I create 1,000,000 strings, then time how long it takes me to retrieve 100,000 random ones from both the dictionary and the set. When I run this a few times, the set actually appears to be faster...

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

b $ b

在你的特殊情况下，我不确定这些将是你想要的。你说你想要所有这些对象在内存中，但你真的需要他们，或者你只需​​要他们中的几个？如果是后者，那么我可能通过文件读取并创建一个对象ID到文件偏移映射（即，记住每个对象id在文件中）。然后你可以查找你想要的那些，并使用文件偏移量跳转到文件中的正确位置，解析该行，并继续。这是 NSFileHandle 的工作。

这篇关于NSDictionary，NSArray，NSSet和效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！