2

对于检查列表中是否已存在对象，这更快且成本更低。通过使用 NSArray 包含对象或检查 NSDictionary 的键是否已存在？

NSArray containsObject 选择器是否还遍历整个数组元素？另外检查一个键是否已经存在于字典中呢？这是否需要遍历所有键。

最后，检查一个对象是否已经存在于（同一个类的）大对象列表中的最好和最快的方法是什么。

提前致谢

4

3 回答 3

5

根据 Collection Classes 的文档，NSDictionary 是基于 HashTables 的。这意味着如果您在字典中搜索一个键，所需的时间比遍历数组要少得多。

因此，搜索密钥应该是 o(1+numberofcollisions)。其中遍历数组是o(n)。您可以对数组进行快速排序，然后对其进行二进制搜索，这将使成本大大降低。但是，对于您的降压，NSDictionary（哈希表）对于搜索来说非常便宜。

来自苹果文档

在内部，字典使用哈希表来组织其存储并提供对给定相应键的值的快速访问。但是，为字典定义的方法使您免受使用哈希表、哈希函数或键的哈希值的复杂性。这些方法直接获取键，而不是它们的散列形式。

于 2012-06-12T15:22:08.893 回答
1

你在说多少价值观？速度上的差异可能无关紧要，因此使选择成为代码中最有意义的选择。事实上，这可能应该是第一要务，除非并且直到您知道存在速度问题。

短版：使用 NSDictionary 除非您有特殊需要。

于 2012-10-03T21:12:58.163 回答
0

我会说最快的方法是在插入对象时对数组进行排序：

NSMutableArray *myArray;

[myArray addObject:someCustomObject];
[myArray sortUsingComparator:^NSComparisonResult(id obj1, id obj2) {
    // custom compare code here
}];

虽然这会降低插入对象的性能，但会大大增加您的查找时间。

对 NSArray 进行二分搜索：

BOOL binarySearchContains(NSArray *sortedArray, id object, NSComparator comparisonBlock)
{
    // simple recursive helper function
    __block BOOL (^_binaryRecurse)(NSArray *, id, int lo, int hi) = ^BOOL(NSArray *array, id object, int lo, int hi)
    {
        int middleIndex = ((hi - lo) / 2) + lo;

        if (hi == lo || middleIndex < 0 || middleIndex >= [array count])
            return NO;

        int compareResult = (comparisonBlock(object, [array objectAtIndex:middleIndex]));

        if (compareResult < 0)
            return _binaryRecurse(array, object, lo, middleIndex - 1);
        if (compareResult > 0)
            return _binaryRecurse(array, object, middleIndex + 1, hi);

        return YES;
    };

    return _binaryRecurse(sortedArray, object, 0, [sortedArray count]);
}

在我的测试中，bsearch大约比-containsObject:.

于 2012-06-12T14:57:06.863 回答