算法时间复杂度分析
时间复杂度通常用大 O 符号描述。定义了函数的极限特征，被用于描绘算法效率。O 定义了函数增长率的上限。
常用的 O 符号的量级以及它们所对应需要的操作数的关系。
NSArray, NSSet, NSOrderedSet 和 NSDictionary
基础集合类是iOS 应用的基本组成部分。在本文中，对 (NSArray, NSSet,NSMapTable, NSHashTable, NSPointerArray) 进行一个效率的分析细节，并讨论其使用场景。
可变性
大多数的集合类存在两个版本:可变和不可变(默认)。
最大的好处是线程安全。不可变的集合是线程安全的，可以同时在多个线程中迭代。我们的 API 不应该暴露一个可变的集合。而是在内部使用一个可变的集合，而在访问时返回一个不可变的对象副本。
需要注意的是，一些集合类，如 NSHashTable，NSMapTable 和 NSPointerArray 默认就是可变的，它们并没有对应的不可变的类。它们用于类的内部使用，基本找不到需要它们的不可变版本的应用场景。
NSArray
NSArray 作为存储对象的有序集合，拥有语法糖符号 @[...]。 NSArray 实现了 objectAtIndexedSubscript:，因此可以使用类 C 的语法 array[0] 来代替原来的 [array objectAtIndex:0]。
/*
提供对下标的支持的方法。是编译器使用的方法，可以使用类 C 的语法 array[0] 。
对于NSArray ，它与-objectAtIndex：完全相同。是一个不同的方法的原因是,其他类也可以实现这一接口，以便支持下标访问，
*/
- (ObjectType)objectAtIndexedSubscript:(NSUInteger)idx
方法列表
NSArray
normal
@property (readonly) NSUInteger count; // 数量
/*
返回一个新数组，该数组是调用方法数组的副本，并在末尾添加了元素.
如果anObject为nil，则引发NSInvalidArgumentException。
*/
- (NSArray<ObjectType> *)arrayByAddingObject:(ObjectType)anObject;
- (NSArray<ObjectType> *)arrayByAddingObjectsFromArray:(NSArray<ObjectType> *)otherArray;
//返回一个NSString对象，该对象是在数组的元素之间插入给定分隔符的结果。
- (NSString *)componentsJoinedByString:(NSString *)separator;
// 返回数组中是否存在给定的对象。
- (BOOL)containsObject:(ObjectType)anObject;
@property (nullable, nonatomic, readonly) ObjectType firstObject; //第一个元素
@property (nullable, nonatomic, readonly) ObjectType lastObject; //最后一个元素
- (NSEnumerator<ObjectType> *)objectEnumerator;// 枚举遍历器
- (NSEnumerator<ObjectType> *)reverseObjectEnumerator;// 数组反转
// 写入本地
- (BOOL)writeToURL:(NSURL *)url error:(NSError **)error API_AVAILABLE(macos(10.13), ios(11.0), watchos(4.0), tvos(11.0));
/*
将选择器标识的消息发送到数组中的每个对象，从第一个对象开始，一直到数组的最后一个对象。
如果aSelector为NULL，则此方法引发NSInvalidArgumentException。
*/
- (void)makeObjectsPerformSelector:(SEL)aSelector
- (void)makeObjectsPerformSelector:(SEL)aSelector withObject:(nullable id)argument;
// 遍历数组
// 数组中的每个对象执行block，从第一个对象开始，一直到数组到最后一个对象。
- (void)enumerateObjectsUsingBlock:(void (NS_NOESCAPE ^)(ObjectType obj, NSUInteger idx, BOOL *stop))block
// 此方法同步执行。默认从第一个对象开始，到最后一个对象,通过opts参数,可以改成并发和逆序
- (void)enumerateObjectsWithOptions:(NSEnumerationOptions)opts usingBlock:(void (NS_NOESCAPE ^)(ObjectType obj, NSUInteger idx, BOOL *stop))block
// 给定枚举的索引值
- (void)enumerateObjectsAtIndexes:(NSIndexSet *)s options:(NSEnumerationOptions)opts usingBlock:(void (NS_NOESCAPE ^)(ObjectType obj, NSUInteger idx, BOOL *stop))block
取元素/取下标
- (ObjectType)objectAtIndex:(NSUInteger)index;// 根据下标取元素
// 返回包含在self中的第一个对象，该对象也包含在otherArray中。
- (nullable ObjectType)firstObjectCommonWithArray:(NSArray<ObjectType> *)otherArray;
// 将指定范围内的对象复制到objects,但需要手动管理内存。
- (void)getObjects:(ObjectType _Nonnull __unsafe_unretained [_Nonnull])objects range:(NSRange)range;
// 获得范围的元素
- (NSArray<ObjectType> *)subarrayWithRange:(NSRange)range;
/*
返回给定对象的最低索引。
从索引0开始，调用每个元素的isEqual：方法，直到找到匹配项或到达数组末尾为止。 如果isEqual :（在NSObject协议中声明）返回YES，则认为对象相等。
*/
- (NSUInteger)indexOfObject:(ObjectType)anObject;
- (NSUInteger)indexOfObject:(ObjectType)anObject inRange:(NSRange)range;// 获得范围内对象的下标
- (NSUInteger)indexOfObjectIdenticalTo:(ObjectType)anObject;// 根据指针比较是否相等
- (NSUInteger)indexOfObjectIdenticalTo:(ObjectType)anObject inRange:(NSRange)range;// 根据指针比较范围内对象是否相等
// 返回包含给定索引集指定的索引元素的数组
- (NSArray<ObjectType> *)objectsAtIndexes:(NSIndexSet *)indexes;
//返回指定索引处的对象。 您不需要直接调用此方法。 而是在使用下标通过索引访问对象时调用此方法。
- (ObjectType)objectAtIndexedSubscript:(NSUInteger)idx;
// 数组中 ,block返回yes的第一个对象的索引。
- (NSUInteger)indexOfObjectPassingTest:(BOOL (NS_NOESCAPE ^)(ObjectType obj, NSUInteger idx, BOOL *stop))predicate;
- (NSUInteger)indexOfObjectWithOptions:(NSEnumerationOptions)opts passingTest:(BOOL (NS_NOESCAPE ^)(ObjectType obj, NSUInteger idx, BOOL *stop))predicate;
- (NSUInteger)indexOfObjectAtIndexes:(NSIndexSet *)s options:(NSEnumerationOptions)opts passingTest:(BOOL (NS_NOESCAPE^)(ObjectType obj, NSUInteger idx, BOOL *stop))predicate;
// 返回在给定块中通过测试的数组中对象的索引。
- (NSIndexSet *)indexesOfObjectsPassingTest:(BOOL (NS_NOESCAPE ^)(ObjectType obj, NSUInteger idx, BOOL *stop))predicate;
- (NSIndexSet *)indexesOfObjectsWithOptions:(NSEnumerationOptions)opts passingTest:(BOOL (NS_NOESCAPE ^)(ObjectType obj, NSUInteger idx, BOOL *stop))predicate;
- (NSIndexSet *)indexesOfObjectsAtIndexes:(NSIndexSet *)s options:(NSEnumerationOptions)opts passingTest:(BOOL (NS_NOESCAPE ^)(ObjectType obj, NSUInteger idx, BOOL *stop))predicate
排序
/*
在数组排序后使用 sortedArrayHint 并持有它。，提供给sortedArrayUsingFunction：context：hint：时，可加快数组的排序。
hinted sort 方式在你有一个已排序的大数组 (N 个元素) 并且只改变其中一小部分（P 个添加和删除，这里 P远小于 N）时，会非常有效。你可以重用原来的排序结果，然后在 N 个老项目和 P 个新项目进行一个概念上的归并排序。
*/
@property (readonly, copy) NSData *sortedArrayHint;
// 数组的排序
- (NSArray<ObjectType> *)sortedArrayUsingFunction:(NSInteger (NS_NOESCAPE *)(ObjectType, ObjectType, void * _Nullable))comparator context:(nullable void *)context;
- (NSArray<ObjectType> *)sortedArrayUsingFunction:(NSInteger (NS_NOESCAPE *)(ObjectType, ObjectType, void * _Nullable))comparator context:(nullable void *)context hint:(nullable NSData *)hint;
- (NSArray<ObjectType> *)sortedArrayUsingSelector:(SEL)comparator;
//排序
/*
typedef NSComparisonResult (^NSComparator)(id obj1, id obj2);
a < b then return NSOrderedAscending. The left operand is smaller than the right operand.
a > b then return NSOrderedDescending. The left operand is greater than the right operand.
a == b then return NSOrderedSame. The operands are equal.
typedef NS_CLOSED_ENUM(NSInteger, NSComparisonResult) {
NSOrderedAscending = -1L,
NSOrderedSame,
NSOrderedDescending
};
*/
- (NSArray<ObjectType> *)sortedArrayUsingComparator:(NSComparator NS_NOESCAPE)cmptr.
- (NSArray<ObjectType> *)sortedArrayWithOptions:(NSSortOptions)opts usingComparator:(NSComparator NS_NOESCAPE)cmptr
/*
typedef NS_OPTIONS(NSUInteger, NSBinarySearchingOptions) {
NSBinarySearchingFirstEqual = (1UL << 8),
NSBinarySearchingLastEqual = (1UL << 9),
//返回索引，您应在该索引处插入对象以维护排序后的数组。
NSBinarySearchingInsertionIndex = (1UL << 10),
};
使用给定的NSComparator，将obj在指定范围内与数组中的元素进行比较，返回该索引。
数组中的元素必须已经使用比较器cmp进行了排序。如果数组未排序，则结果不确定。
*/
`谓词`
- (NSArray<ObjectType> *)filteredArrayUsingPredicate:(NSPredicate *)predicate;
// 二分查找
- (NSUInteger)indexOfObject:(ObjectType)obj inSortedRange:(NSRange)r options:(NSBinarySearchingOptions)opts usingComparator:(NSComparator NS_NOESCAPE)cmp
比较
/*
比较数组是否相等
如果两个数组容纳相同数量的对象，并且每个数组中相同索引的对象满足isEqual：则它们的内容相同。
*/
- (BOOL)isEqualToArray:(NSArray<ObjectType> *)otherArray;
// 比较两个数组的不同相关的api
- (NSOrderedCollectionDifference<ObjectType> *)differenceFromArray:(NSArray<ObjectType> *)other withOptions:(NSOrderedCollectionDifferenceCalculationOptions)options usingEquivalenceTest:(BOOL (NS_NOESCAPE ^)(ObjectType obj1, ObjectType obj2))block;
- (NSOrderedCollectionDifference<ObjectType> *)differenceFromArray:(NSArray<ObjectType> *)other withOptions:(NSOrderedCollectionDifferenceCalculationOptions)options;
// Uses isEqual: to determine the difference between the parameter and the receiver
- (NSOrderedCollectionDifference<ObjectType> *)differenceFromArray:(NSArray<ObjectType> *)other;
- (nullable NSArray<ObjectType> *)arrayByApplyingDifference:(NSOrderedCollectionDifference<ObjectType> *)difference;
NSMutableArray
元素的添加/删除/替换
- (void)addObject:(ObjectType)anObject;
- (void)insertObject:(ObjectType)anObject atIndex:(NSUInteger)index;
- (void)removeLastObject;
- (void)removeObjectAtIndex:(NSUInteger)index;
- (void)replaceObjectAtIndex:(NSUInteger)index withObject:(ObjectType)anObject;
- (void)addObjectsFromArray:(NSArray<ObjectType> *)otherArray;
- (void)exchangeObjectAtIndex:(NSUInteger)idx1 withObjectAtIndex:(NSUInteger)idx2;
- (void)removeAllObjects;
- (void)removeObject:(ObjectType)anObject inRange:(NSRange)range;
- (void)removeObject:(ObjectType)anObject;
- (void)removeObjectIdenticalTo:(ObjectType)anObject inRange:(NSRange)range;
- (void)removeObjectIdenticalTo:(ObjectType)anObject;
- (void)removeObjectsInArray:(NSArray<ObjectType> *)otherArray;
- (void)removeObjectsInRange:(NSRange)range;
- (void)replaceObjectsInRange:(NSRange)range withObjectsFromArray:(NSArray<ObjectType> *)otherArray range:(NSRange)otherRange;
- (void)replaceObjectsInRange:(NSRange)range withObjectsFromArray:(NSArray<ObjectType> *)otherArray;
- (void)setArray:(NSArray<ObjectType> *)otherArray; // 设置元素
/*
将提供的数组中的对象插入到指定索引处的接收数组中。
索引中的位置数必须等于对象数
*/
- (void)insertObjects:(NSArray<ObjectType> *)objects atIndexes:(NSIndexSet *)indexes;
- (void)removeObjectsAtIndexes:(NSIndexSet *)indexes;
- (void)replaceObjectsAtIndexes:(NSIndexSet *)indexes withObjects:(NSArray<ObjectType> *)objects;
- (void)setObject:(ObjectType)obj atIndexedSubscript:(NSUInteger)idx API_AVAILABLE(macos(10.8), ios(6.0), watchos(2.0), tvos(9.0));
排序
- (void)sortUsingFunction:(NSInteger (NS_NOESCAPE *)(ObjectType, ObjectType, void * _Nullable))compare context:(nullable void *)context;
- (void)sortUsingSelector:(SEL)comparator;
- (void)sortUsingComparator:(NSComparator NS_NOESCAPE)cmptr API_AVAILABLE(macos(10.6), ios(4.0), watchos(2.0), tvos(9.0));
- (void)sortWithOptions:(NSSortOptions)opts usingComparator:(NSComparator NS_NOESCAPE)cmptr API_AVAILABLE(macos(10.6), ios(4.0), watchos(2.0), tvos(9.0));
性能
NSArray 内部是一个类簇的方式,基于存储对象的数量，使用各种内部的变体。
Computational Complexity
The access time for a value in the array is guaranteed to be at worst O(lg N) for any implementation, current and future, but will often be O(1) (constant time).
Linear search operations similarly have a worst case complexity of O(N*lg N), though typically the bounds will be tighter, and so on.
Insertion or deletion operations will typically be linear in the number of values in the array, but may be O(N*lg N) clearly in the worst case in some implementations.
There are no favored positions within the array for performance; that is, it is not necessarily faster to access values with low indices, or to insert or delete values with high indices, or whatever.
计算复杂度
对于当前和将来的任何实现，对于值的访问时间复杂度均保证为最差O（lg N），但通常为O（1）（恒定时间）。
线性搜索操作类似地具有最坏情况下的复杂度O（N * lg N），尽管通常范围会更严格，依此类推。
插入或删除操作通常在数组中的数量上是线性的，但是在某些实现中，在最坏的情况下显然可以是O（N * lg N）。
在数组中，没有对于性能上特别有优势的数据位置，也就是说，为了更快地访问到元素而将其设为在较低的 index 上，或者在较高的 index 上进行插入和删除，或者类似的一些做法，是没有必要的。
筛选
- (void)filteringArrayBenchmark {
[@[@(10000),@(10000000)] enumerateObjectsUsingBlock:^(NSNumber * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
NSUInteger const numberOfEntries = [obj unsignedIntegerValue];
printf("操作数量: %g [run %tu]", (double)numberOfEntries, idx+1);
NSMutableArray *randomArray = [NSMutableArray array];
// 添加元素
for (NSUInteger idx = 0; idx < numberOfEntries; idx++) {
[randomArray addObject:[NSString stringWithFormat:@"%tu", arc4random_uniform(500000)]];
}
// 筛选的block
BOOL (^testObj)(id obj) = ^BOOL(id obj) {
return [obj integerValue] < 10;
};
double filter1 = PerformAndTrackTime(^{
NSIndexSet *indexes = [randomArray indexesOfObjectsWithOptions:0 passingTest:^BOOL(id obj, NSUInteger idx, BOOL *stop) {
return testObj(obj);
}];
__unused NSArray *filteredArray1 = [randomArray objectsAtIndexes:indexes];
});
double filter1_rec = PerformAndTrackTime(^{
NSIndexSet *indexes = [randomArray indexesOfObjectsWithOptions:NSEnumerationConcurrent passingTest:^BOOL(id obj, NSUInteger idx, BOOL *stop) {
return testObj(obj);
}];
__unused NSArray *filteredArray1 = [randomArray objectsAtIndexes:indexes];
});
double filter2 = PerformAndTrackTime(^{
__unused NSArray *filteredArray2 = [randomArray filteredArrayUsingPredicate:[NSPredicate predicateWithBlock:^BOOL(id obj, NSDictionary *bindings) {
return testObj(obj);
}]];
});
double filter3 = PerformAndTrackTime(^{
NSMutableArray *mutableArray = [NSMutableArray array];
[randomArray enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
if (testObj(obj)) {
[mutableArray addObject:obj];
}
}];
__unused NSArray *filteredArray3 = [mutableArray copy];
});
double filter4 = PerformAndTrackTime(^{
NSMutableArray *mutableArray = [NSMutableArray array];
for (id obj in randomArray) {
if (testObj(obj)) {
[mutableArray addObject:obj];
}
}
__unused NSArray *filteredArray4 = [mutableArray copy];
});
double filter5 = PerformAndTrackTime(^{
NSMutableArray *mutableArray = [NSMutableArray array];
NSEnumerator *enumerator = [randomArray objectEnumerator];
id obj = nil;
while ((obj = [enumerator nextObject]) != nil) {
if (testObj(obj)) {
[mutableArray addObject:obj];
}
}
__unused NSArray *filteredArray5 = [mutableArray copy];
});
double filter6 = PerformAndTrackTime(^{
NSMutableArray *mutableArray = [NSMutableArray array];
for (NSUInteger idx = 0; idx < randomArray.count; idx++) {
id obj = randomArray[idx];
if (testObj(obj)) {
[mutableArray addObject:obj];
}
}
__unused NSArray *filteredArray6 = [mutableArray copy];
});
printf("\n");
printf("NSMutableArray indexesOfObjects遍历筛选 : %f [ms]\n", filter1/1E6);
printf("NSMutableArray indexesOfObjects-recursive遍历筛选 : %f [ms]\n", filter1_rec/1E6);
printf("NSMutableArray filteredArrayUsingPredicate遍历筛选 : %f [ms]\n", filter2/1E6);
printf("NSMutableArray enumerateObjectsUsingBlock 遍历筛选 : %f [ms]\n", filter3/1E6);
printf("NSMutableArray for in 遍历筛选 : %f [ms]\n", filter4/1E6);
printf("NSMutableArray objectEnumerator 遍历筛选 : %f [ms]\n", filter5/1E6);
printf("NSMutableArray objectAtIndex 遍历筛选 : %f [ms]\n", filter6/1E6);
printf("\n");
}];
}
在iphone8plus上的运行结果
操作数量: 10000 [run 1]
NSMutableArray indexesOfObjects遍历筛选 : 2.986958 [ms]
NSMutableArray indexesOfObjects-recursive遍历筛选 : 1.873833 [ms]
NSMutableArray filteredArrayUsingPredicate遍历筛选 : 3.088208 [ms]
NSMutableArray enumerateObjectsUsingBlock 遍历筛选 : 2.953792 [ms]
NSMutableArray for in 遍历筛选 : 2.677917 [ms]
NSMutableArray objectEnumerator 遍历筛选 : 2.750583 [ms]
NSMutableArray objectAtIndex 遍历筛选 : 2.863250 [ms]
操作数量: 1e+07 [run 2]
NSMutableArray indexesOfObjects遍历筛选 : 2805.612250 [ms]
NSMutableArray indexesOfObjects-recursive遍历筛选 : 1845.823625 [ms]
NSMutableArray filteredArrayUsingPredicate遍历筛选 : 3068.554292 [ms]
NSMutableArray enumerateObjectsUsingBlock 遍历筛选 : 2938.240167 [ms]
NSMutableArray for in 遍历筛选 : 2679.789917 [ms]
NSMutableArray objectEnumerator 遍历筛选 : 2750.049750 [ms]
NSMutableArray objectAtIndex 遍历筛选 : 2836.580167 [ms]
indexesOfObjectsWithOptions:passingTest: 必须每次都执行一次 block 因此比传统的使用 NSFastEnumeration 技术的基于 for 循环的枚举要稍微低效一些。但是如果使用NSEnumerationConcurrent开启了并发，那么前者的速度则会大大的提高。但 NSEnumerationConcurrent 只对大量的对象有意义，如果你的集合中的对象数量很少，用哪个方法就真的无关紧要。甚至 NSEnumerationConcurrent 上额外的线程管理实际上会使结果变得更慢。
苹果拥有快速枚举 NSFastEnumeration,通过 countByEnumeratingWithState:objects:count: 返回一个数据块。该数据块被解析成 id 类型的 C 数组。这就是更快的速度的原因；迭代一个 C 数组要快得多，而且可以被编译器更深一步的优化。
是否使用arrayWithCapacity:
- (void)arrayAddBenchmark{
[@[@(10000), @(100000), @(1000000), @(10000000), @(20000000)] enumerateObjectsUsingBlock:^(NSNumber *entriesNumber, NSUInteger runCount, BOOL *stop) {
NSUInteger entries = entriesNumber.unsignedIntegerValue;
printf("操作数量: %g [run %tu]", (double)entries, runCount+1);
printf("\n");
double array_add_time = 0,array_add_with_capacity_time = 0;
const NSUInteger skipCount = 1;
@autoreleasepool {
NSMutableArray *array = [NSMutableArray array];
NSNull *null = NSNull.null;
array_add_time = PerformAndTrackTime(^{
for (NSUInteger idx = 0; idx < entries; idx++) {
[array addObject:null];
}
for (NSUInteger idx = 0; idx < entries; idx+=skipCount) {
array[idx] = EntryForIDX(idx);
}
});
}
@autoreleasepool {
NSMutableArray *array = [NSMutableArray arrayWithCapacity:entries];
NSNull *null = NSNull.null;
array_add_with_capacity_time = PerformAndTrackTime(^{
for (NSUInteger idx = 0; idx < entries; idx++) {
[array addObject:null];
}
for (NSUInteger idx = 0; idx < entries; idx+=skipCount) {
array[idx] = EntryForIDX(idx);
}
});
}
if (array_add_time) printf("NSMutableArray 添加元素 : %f [ms]\n", array_add_time/1E6);
if (array_add_with_capacity_time) printf("NSMutableArray Capacity 添加元素: %f [ms]\n", array_add_with_capacity_time/1E6);
printf("\n");
}];
}
在iphone8plus上的运行结果
操作数量: 10000 [run 1]
NSMutableArray 添加元素 : 1.612833 [ms]
NSMutableArray Capacity 添加元素: 1.559083 [ms]
操作数量: 100000 [run 2]
NSMutableArray 添加元素 : 13.779000 [ms]
NSMutableArray Capacity 添加元素: 12.043000 [ms]
操作数量: 1e+06 [run 3]
NSMutableArray 添加元素 : 127.659917 [ms]
NSMutableArray Capacity 添加元素: 122.622458 [ms]
操作数量: 1e+07 [run 4]
NSMutableArray 添加元素 : 1322.217333 [ms]
NSMutableArray Capacity 添加元素: 1276.152750 [ms]
操作数量: 2e+07 [run 5]
NSMutableArray 添加元素 : 2645.455667 [ms]
NSMutableArray Capacity 添加元素: 2527.032500 [ms]
初始化NSArray的时候，可以选择指定数组的预期大小。在检测的时候，结果是有10%左右的时间差别,并且使用 arrayWithCapacity: 仍然好处，它可以作为一种隐性的文档来帮助你理解代码.
NSDictionary
NSDictionary存储任意的对象键值对。 键是被拷贝的并且需要是不变的。如果在一个键在被用于在字典中放入一个值后被改变的话，那么这个值就会变得无法获取了。
在 NSDictionary 中键是被 copy 的，但是在使用一个 toll-free 桥接的 CFDictionary 时却只会被 retain。CoreFoundation 类没有通用的拷贝对象的方法，因此这时拷贝是不可能的(*)。这只适用于你使用 CFDictionarySetValue() 的时候。
如果你是通过 setObject:forKey 来使用一个 toll-free 桥接的 CFDictionary 的话，苹果会为其增加额外处理逻辑，使得键被拷贝。但是反过来这个结论则不成立 — 使用已经转换为 CFDictionary 的 NSDictionary 对象，并用对其使用 CFDictionarySetValue() 方法，还是会导致调用回 setObject:forKey 并对键进行拷贝。
(*)其实有一个现成的键的回调函数 kCFCopyStringDictionaryKeyCallBacks 可以拷贝字符串，因为对于 ObjC对象来说， CFStringCreateCopy() 会调用 [NSObject copy]，我们可以巧妙使用这个回调来创建一个能进行键拷贝的 CFDictionary。
方法列表
NSDictionary
normal
@property (readonly) NSUInteger count;
- (BOOL)writeToURL:(NSURL *)url error:(NSError **)error
取值
- (nullable ObjectType)objectForKey:(KeyType)aKey;
- (NSEnumerator<KeyType> *)keyEnumerator;
@property (readonly, copy) NSArray<KeyType> *allKeys;
/*
返回一个新数组，包含字典中给定对象的所有匹配项对应的键。
将向字典中的每个对象发送isEqual：消息，以确定是否相等
*/
- (NSArray<KeyType> *)allKeysForObject:(ObjectType)anObject;
@property (readonly, copy) NSArray<ObjectType> *allValues;
- (BOOL)isEqualToDictionary:(NSDictionary<KeyType, ObjectType> *)otherDictionary;
// 返回一个枚举器对象，使您可以访问字典中的每个值。
- (NSEnumerator<ObjectType> *)objectEnumerator;
/*
概要
以数组形式返回字典中与指定键对应的对象集。
返回数组和keys数组中的对象具有一对一的对应关系，因此返回数组中的对象与keys中的键相对应。
如果在字典中找不到对应于给定键的对象，则将标记对象放置在返回数组的相应元素中。
*/
- (NSArray<ObjectType> *)objectsForKeys:(NSArray<KeyType> *)keys notFoundMarker:(ObjectType)marker;
//通过引用返回字典中键和值的C数组。
- (void)getObjects:(ObjectType _Nonnull __unsafe_unretained [_Nullable])objects andKeys:(KeyType _Nonnull __unsafe_unretained [_Nullable])keys count:(NSUInteger)count
- (nullable ObjectType)objectForKeyedSubscript:(KeyType)key
- (void)enumerateKeysAndObjectsUsingBlock:(void (NS_NOESCAPE ^)(KeyType key, ObjectType obj, BOOL *stop))block;
- (void)enumerateKeysAndObjectsWithOptions:(NSEnumerationOptions)opts usingBlock:(void (NS_NOESCAPE ^)(KeyType key, ObjectType obj, BOOL *stop))block;
// 通过测试的keys
- (NSSet<KeyType> *)keysOfEntriesPassingTest:(BOOL (NS_NOESCAPE ^)(KeyType key, ObjectType obj, BOOL *stop))predicate
- (NSSet<KeyType> *)keysOfEntriesWithOptions:(NSEnumerationOptions)opts passingTest:(BOOL (NS_NOESCAPE ^)(KeyType key, ObjectType obj, BOOL *stop))predicate
排序相关
// 返回排序的key
- (NSArray<KeyType> *)keysSortedByValueUsingSelector:(SEL)comparator;
- (NSArray<KeyType> *)keysSortedByValueUsingComparator:(NSComparator NS_NOESCAPE)cmptr
- (NSArray<KeyType> *)keysSortedByValueWithOptions:(NSSortOptions)opts usingComparator:(NSComparator NS_NOESCAPE)cmptr
NSMutableDictionary
元素的添加/删除
- (void)removeObjectForKey:(KeyType)aKey;
- (void)setObject:(ObjectType)anObject forKey:(KeyType <NSCopying>)aKey;
- (void)addEntriesFromDictionary:(NSDictionary<KeyType, ObjectType> *)otherDictionary;
- (void)removeAllObjects;
- (void)removeObjectsForKeys:(NSArray<KeyType> *)keyArray;
- (void)setDictionary:(NSDictionary<KeyType, ObjectType> *)otherDictionary;
- (void)setObject:(nullable ObjectType)obj forKeyedSubscript:(KeyType <NSCopying>)key
/*
共享键字典始终是可变的，即使对它们执行了”copy”命令后也是。这个行为文档中并没有说明，但很容易被测试:
id sharedKeySet = [NSDictionary sharedKeySetForKeys:@[@1, @2, @3]]; // 返回 NSSharedKeySet
NSMutableDictionary *test = [NSMutableDictionary dictionaryWithSharedKeySet:sharedKeySet];
test[@4] = @"First element (not in the shared key set, but will work as well)";
NSDictionary *immutable = [test copy];
NSParameterAssert(immutable.count == 1);
((NSMutableDictionary *)immutable)[@5] = @"Adding objects to an immutable collection should throw an exception.";
NSParameterAssert(immutable.count == 2);
*/
/*
使用此方法可以创建要传递给+ dictionaryWithSharedKeySet：的密钥集。共享键集会复用对象，以节省内存。
`sharedKeySetForKeys:` 中会计算一个最小完美哈希，这个哈希值可以取代字典查找过程中探索循环的需要，因此使键的访问更快。
键是从数组复制的，并且必须是可复制的。
如果array参数为nil或不是NSArray，则引发异常。
如果键数组为空，则返回一个空键集。
键数组可能包含重复项，这些重复项将被忽略（未定义使用每个重复对中的哪个对象）。
至于哈希的任何用法，建议键具有-hash的分布良好的实现，并且哈希码必须满足hash / isEqual：invariant。
允许使用具有重复的哈希码的键，但它们会导致性能降低并增加内存使用率。
*/
+ (id)sharedKeySetForKeys:(NSArray<KeyType <NSCopying>> *)keys
/*
创建一个可变字典，该字典针对处理一组已知键进行了优化。
仍然可以将不在键集中的键设置到字典中，但是这种用法不是最佳的。
与任何词典一样，键必须是可复制的。
如果键集为nil，则引发异常。
如果键集不是+ sharedKeySetForKeys：返回的对象，则会引发异常。
*/
+ (NSMutableDictionary<KeyType, ObjectType> *)dictionaryWithSharedKeySet:(id)keyset
性能
Computational Complexity
The access time for a value in the dictionary is guaranteed to be at worst O(N) for any implementation, current and future, but will often be O(1) (constant time).
Insertion or deletion operations will typically be constant time as well, but are O(N*N) in the worst case in some implementations.
Access of values through a key is faster than accessing values directly (if there are any such operations). Dictionaries will tend to use significantly more memory than a array with the same number of values.
计算复杂度
对于当前和将来的任何实现，对于字典中的值的访问时间都保证为最差的O（N），但通常为O（1）（恒定时间）。
插入或删除操作通常也将是常数时间，但是在某些实现中，在最坏的情况下为O（N * N）。
通过键访问值比直接访问值（如果有任何此类操作）要快。 对于同样数目的值，字典需要花费比数组多得多的内存空间。
筛选
- (void)filteringDictionaryBenchmark {
@autoreleasepool {
// Create random dictionary
NSUInteger const numberOfEntries = 1000000;
NSMutableDictionary *randomDict = [NSMutableDictionary dictionary];
for (NSUInteger idx = 0; idx < numberOfEntries; idx++) {
randomDict[@(idx)] = [NSString stringWithFormat:@"%tu", arc4random_uniform(500000)];
}
BOOL (^testObj)(id obj) = ^BOOL(id obj) {
return [obj integerValue] < 10;
};
double filter1 = PerformAndTrackTimeMultiple(^{
NSSet *matchingKeys = [randomDict keysOfEntriesWithOptions:0 passingTest:^BOOL(id key, id obj, BOOL *stop) {
return testObj(obj);
}];
NSArray *keys = matchingKeys.allObjects;
NSArray *values = [randomDict objectsForKeys:keys notFoundMarker:NSNull.null];
__unused NSDictionary *filteredDictionary = [NSDictionary dictionaryWithObjects:values forKeys:keys];
}, 3);
double filter2 = PerformAndTrackTimeMultiple(^{
NSArray *keys = [randomDict keysOfEntriesWithOptions:NSEnumerationConcurrent passingTest:^BOOL(id key, id obj, BOOL *stop) {
return testObj(obj);
}].allObjects;
__unused NSDictionary *filteredDictionary2 = [NSDictionary dictionaryWithObjects:[randomDict objectsForKeys:keys notFoundMarker:NSNull.null] forKeys:keys];
}, 3);
double filter3 = PerformAndTrackTimeMultiple(^{
NSMutableDictionary *mutableDictionary = [NSMutableDictionary dictionary];
[randomDict enumerateKeysAndObjectsUsingBlock:^(id key, id obj, BOOL *stop) {
if (testObj(obj)) {
mutableDictionary[key] = obj;
}
}];
__unused NSDictionary *filteredDictionary3 = [mutableDictionary copy];
}, 3);
double filter4 = PerformAndTrackTimeMultiple(^{
NSMutableDictionary *mutableDictionary = [NSMutableDictionary dictionary];
for (id key in randomDict) {
id obj = randomDict[key];
if (testObj(obj)) {
mutableDictionary[key] = obj;
}
}
__unused NSDictionary *filteredDictionary4 = [mutableDictionary copy];
}, 3);
double filter5 = PerformAndTrackTimeMultiple(^{
NSMutableDictionary *mutableDictionary = [NSMutableDictionary dictionary];
id __unsafe_unretained *objects = (id __unsafe_unretained *)malloc(sizeof(id) * numberOfEntries);
id __unsafe_unretained *keys = (id __unsafe_unretained *)(malloc(sizeof(id) * numberOfEntries));
[randomDict getObjects:objects andKeys:keys count:numberOfEntries];
for (int i = 0; i < numberOfEntries; i++) {
id obj = objects[i];
id key = keys[i];
if (testObj(obj)) {
mutableDictionary[key] = obj;
}
}
free(objects);
free(keys);
__unused NSDictionary *filteredDictionary5 = [mutableDictionary copy];
}, 3);
double filter6 = PerformAndTrackTimeMultiple(^{
NSMutableDictionary *mutableDictionary = [NSMutableDictionary dictionary];
NSEnumerator *enumerator = [randomDict keyEnumerator];
id key = nil;
while ((key = [enumerator nextObject]) != nil) {
id obj = randomDict[key];
if (testObj(obj)) {
mutableDictionary[key] = obj;
}
}
__unused NSDictionary *filteredDictionary6 = [mutableDictionary copy];
}, 3);
printf("\n");
printf("keysOfEntriesWithOptions 遍历筛选 : %f [ms]\n", filter1/1E6);
printf("keysOfEntriesWithOptions (concurrent)遍历筛选 : %f [ms]\n", filter2/1E6);
printf("enumerateKeysAndObjectsUsingBlock 遍历筛选 : %f [ms]\n", filter3/1E6);
printf("NSFastEnumeration 遍历筛选 : %f [ms]\n", filter4/1E6);
printf("getObjects 遍历筛选 : %f [ms]\n", filter5/1E6);
printf("NSEnumeration 遍历筛选 : %f [ms]\n", filter6/1E6);
printf("\n");
}
}
在iphone8plus的测试结果
keysOfEntriesWithOptions 遍历筛选 : 307.779542 [ms]
keysOfEntriesWithOptions (concurrent)遍历筛选 : 223.535639 [ms]
enumerateKeysAndObjectsUsingBlock 遍历筛选 : 309.204486 [ms]
NSFastEnumeration 遍历筛选 : 317.227111 [ms]
getObjects 遍历筛选 : 288.647764 [ms]
NSEnumeration 遍历筛选 : 323.622139 [ms]
为什么 NSFastEnumeration 这么慢？迭代字典通常需要键和值两者，快速枚举只能枚举键，我们必须每次都自己获取值。
使用基于 block 的 enumerateKeysAndObjectsUsingBlock: 更高效，因为两者都可以更高效的被提前获取。
测试的胜利者是通过 keysOfEntriesWithOptions:passingTest: 和 objectsForKeys:notFoundMarker: 的并发迭代。
是否使用dictionaryWithCapacity:
操作数量: 10000 [run 1]
NSMutableDictionary 添加元素 : 3.873083 [ms]
NSMutableDictionary Capacity 添加元素: 2.943917 [ms]
操作数量: 100000 [run 2]
NSMutableDictionary 添加元素 : 36.855000 [ms]
NSMutableDictionary Capacity 添加元素: 24.019042 [ms]
操作数量: 1e+06 [run 3]
NSMutableDictionary 添加元素 : 695.076292 [ms]
NSMutableDictionary Capacity 添加元素: 519.170500 [ms]
操作数量: 1e+07 [run 4]
NSMutableDictionary 添加元素 : 6845.641125 [ms]
NSMutableDictionary Capacity 添加元素: 5434.460917 [ms]
操作数量: 2e+07 [run 5]
NSMutableDictionary 添加元素 : 15726.239792 [ms]
NSMutableDictionary Capacity 添加元素: 10676.138667 [ms]
差距还是蛮大的
NSSet
NSSet 和它的可变变体 NSMutableSet 是无序对象集合。检查一个对象是否存在通常是一个 O(1) 的操作，使得比 NSArray 快很多。
NSSet 只在被使用的哈希方法平衡的情况下能高效的工作；如果所有的对象都在同一个哈希筐内，NSSet 在查找对象是否存在时并不比 NSArray 快多少。
NSSet 还有变体 NSCountedSet，以及非 toll-free 计数变体 CFBag / CFMutableBag。
NSSet 会 retain 它其中的对象，但是根据 set 的规定，对象应该是不可变的。添加一个对象到 set 中随后改变它会导致一些奇怪的问题并破坏 set 的状态。
NSSet 的方法比 NSArray 少的多。没有排序方法，但有一些方便的枚举方法。重要的方法有 allObjects，将对象转化为 NSArray，anyObject 则返回任意的对象，如果 set 为空，则返回 nil。
方法
NSSet
normal
@property (readonly) NSUInteger count;
// 确定集合中是否存在给定对象，如果存在则返回该对象。
- (nullable ObjectType)member:(ObjectType)object;
- (BOOL)containsObject:(ObjectType)anObject;
// 存在交集
- (BOOL)intersectsSet:(NSSet<ObjectType> *)otherSet;
// 相等
- (BOOL)isEqualToSet:(NSSet<ObjectType> *)otherSet;
//子集
- (BOOL)isSubsetOfSet:(NSSet<ObjectType> *)otherSet;
- (void)makeObjectsPerformSelector:(SEL)aSelector
- (void)makeObjectsPerformSelector:(SEL)aSelector withObject:(nullable id)argument
// 返回添加元素后的集合
- (NSSet<ObjectType> *)setByAddingObject:(ObjectType)anObject
- (NSSet<ObjectType> *)setByAddingObjectsFromSet:(NSSet<ObjectType> *)other
- (NSSet<ObjectType> *)setByAddingObjectsFromArray:(NSArray<ObjectType> *)other
取值
- (NSEnumerator<ObjectType> *)objectEnumerator;
@property (readonly, copy) NSArray<ObjectType> *allObjects;
- (nullable ObjectType)anyObject;
- (void)enumerateObjectsUsingBlock:(void (NS_NOESCAPE ^)(ObjectType obj, BOOL *stop))block;
- (void)enumerateObjectsWithOptions:(NSEnumerationOptions)opts usingBlock:(void (NS_NOESCAPE ^)(ObjectType obj, BOOL *stop))block
- (NSSet<ObjectType> *)objectsPassingTest:(BOOL (NS_NOESCAPE ^)(ObjectType obj, BOOL *stop))predicate
- (NSSet<ObjectType> *)objectsWithOptions:(NSEnumerationOptions)opts passingTest:(BOOL (NS_NOESCAPE ^)(ObjectType obj, BOOL *stop))predicate
NSMutableSet
- (void)addObjectsFromArray:(NSArray<ObjectType> *)array;
// 删除不是另一个给定集中成员的每个对象。
- (void)intersectSet:(NSSet<ObjectType> *)otherSet;
// 删除另一个给定集中,自己也拥有的每个对象（如果存在）
- (void)minusSet:(NSSet<ObjectType> *)otherSet;
- (void)removeAllObjects;
// 添加另一个给定集中的每个对象（如果不存在）。
- (void)unionSet:(NSSet<ObjectType> *)otherSet;
- (void)setSet:(NSSet<ObjectType> *)otherSet;// 设置
性能
苹果在 CFSet 头文件中没有提供任何关于算法复杂度的注释
@autoreleasepool {
NSMutableArray *array = [NSMutableArray array];
NSNull *null = NSNull.null;
array_add_time = PerformAndTrackTime(^{
for (NSUInteger idx = 0; idx < entries; idx++) {
[array addObject:null];
}
for (NSUInteger idx = 0; idx < entries; idx+=skipCount) {
array[idx] = EntryForIDX(idx);
}
});
array_rac_time = PerformAndTrackTime(^{
[randomAccessNumbers enumerateObjectsUsingBlock:^(NSNumber *number, BOOL *stop) {
__unused NSUInteger idx = number.unsignedIntegerValue;
__unused id object = array[idx];
}];
});
}
@autoreleasepool {
NSMutableSet *set = [NSMutableSet set];
set_add_time = PerformAndTrackTime(^{
for (NSUInteger idx = 0; idx < entries; idx++) {
[set addObject:EntryForIDX(idx)];
}
});
set_rac_time = PerformAndTrackTime(^{
[randomAccessNumbers enumerateObjectsUsingBlock:^(NSNumber *number, BOOL *stop) {
__unused NSUInteger idx = number.unsignedIntegerValue;
[set anyObject];
}];
});
}
在iphone8plus的测试结果
操作数量: 1e+06 [run 3]
Adding to NSMutableSet: 252.297583 [ms]
Adding to NSMutableArray: 132.914042 [ms]
Random Access for NSMutableArray: 1.833125 [ms]
Random Access for NSMutableSet: 1.272875 [ms]
是否使用setWithCapacity:
- (void)performanceOfInitWithCountOnSet {
NSUInteger const numberOfEntries = 1000000;
NSUInteger const runCount = 5;
printf("操作数量: %g [run %tu]", (double)numberOfEntries, runCount);
printf("\n");
// 先生成字符串,防止产生性能差异
NSMutableSet *randomSet = [NSMutableSet setWithCapacity:numberOfEntries];
for (NSUInteger idx = 0; idx < numberOfEntries; idx++) {
[randomSet addObject:EntryForIDX(idx)];
}
double no_count = PerformAndTrackTimeMultiple(^{
NSMutableSet *randomSet = [NSMutableSet set];
for (NSUInteger idx = 0; idx < numberOfEntries; idx++) {
[randomSet addObject:EntryForIDX(idx)];
}
}, 5);
double with_count = PerformAndTrackTimeMultiple(^{
NSMutableSet *randomSet = [NSMutableSet setWithCapacity:numberOfEntries];
for (NSUInteger idx = 0; idx < numberOfEntries; idx++) {
[randomSet addObject:EntryForIDX(idx)];
}
}, 5);
if (no_count) printf("NSMutableSet 添加元素 : %f [ms]\n", no_count/1E6);
if (with_count) printf("NSMutableSet Capacity 添加元素: %f [ms]\n", with_count/1E6);
}
在iphone8plus的测试结果
操作数量: 1e+06 [run 5]
NSMutableSet 添加元素 : 273.441375 [ms]
NSMutableSet Capacity 添加元素: 207.630833 [ms]
NSOrderedSet
NSOrderedSet 看上去综合了 NSArray 和 NSSet 两者的好处，对象查找，对象唯一性，和快速随机访问。
NSOrderedSet 有着优秀的 API 方法，使得它可以很便利的与其他 set 或者有序 set 对象合作。合并，交集，差集，就像 NSSet 支持的那样。它有 NSArray 中除了比较陈旧的基于函数的排序方法和二分查找以外的大多数排序方法。毕竟 containsObject: 非常快，所以没有必要再用二分查找了。
NSOrderedSet 的 array 和 set 方法分别返回一个 NSArray 和 NSSet，这些对象表面上是不可变的对象，但实际上在 NSOrderedSet 更新的时候，它们也会更新自己。如果你在不同线程上使用这些对象并发生了诡异异常的时候，知道这一点是非常有好处的。本质上，这些类使用的是 __NSOrderedSetSetProxy 和 __NSOrderedSetArrayProxy。
性能
@autoreleasepool {
NSMutableOrderedSet *orderedSet = [NSMutableOrderedSet orderedSet];
ordered_set_add_time = PerformAndTrackTime(^{
for (NSUInteger idx = 0; idx < entries; idx++) {
[orderedSet addObject:EntryForIDX(idx)];
}
});
ordered_set_rac_time = PerformAndTrackTime(^{
[randomAccessNumbers enumerateObjectsUsingBlock:^(NSNumber *number, BOOL *stop) {
__unused NSUInteger idx = number.unsignedIntegerValue;
__unused id object = [orderedSet objectAtIndex:idx];
}];
});
}
在iphone8plus的测试结果
操作数量: 1e+06 [run 3]
Adding to NSMutableArray: 132.914042 [ms]
Adding to NSMutableSet: 252.297583 [ms]
Adding to NSMutableOrderedSet: 351.321708 [ms]
Random Access for NSMutableArray: 1.833125 [ms]
Random Access for NSMutableSet: 1.272875 [ms]
Random Access for NSMutableOrderedSet: 1.749375 [ms]
NSHashTable
NSHashTable 效仿了 NSSet，但在对象/内存处理时更加的灵活。可以通过自定义 CFSet 的回调获得 NSHashTable 的一些特性，哈希表可以保持对对象的弱引用并在对象被销毁之后正确的将其移除,这个类没有相应的不可变版本。
NSHashTable 有 ObjC 和原始的 C API，C API 可以用来存储任意对象
方法
create instance
// 每种类别的选项互斥，只能每种类别选择一个。
typedef NS_OPTIONS(NSUInteger, NSPointerFunctionsOptions) {
//Memory Options（内存语义管理选项）
NSPointerFunctionsStrongMemory //默认值，强引用成员
NSPointerFunctionsZeroingWeakMemory // 已废弃，在 GC 下，弱引用指针，防止悬挂指针
NSPointerFunctionsOpaqueMemory // 在指针去除时不做任何动作
NSPointerFunctionsMallocMemory // free() will be called on removal, calloc on copyIn
NSPointerFunctionsMachVirtualMemory //使用可执行文件的虚拟内存
NSPointerFunctionsWeakMemory // 弱引用成员
//Personaility Options(对象处理选项-如何进行哈希算法，判定等同性，描述)
NSPointerFunctionsObjectPersonality //使用NSObject的hash、isEqual、description，默认
NSPointerFunctionsOpaquePersonality //使用偏移后指针，进行hash和直接比较等同性
NSPointerFunctionsObjectPointerPersonality //和上一个相同，多了description方法
NSPointerFunctionsCStringPersonality //使用c字符串的hash和strcmp比较，%s作为decription
NSPointerFunctionsStructPersonality // 使用内存的hash和memcmp
NSPointerFunctionsIntegerPersonality //使用偏移量作为hash和等同性判断
// Copy Options（对象拷贝选项）
NSPointerFunctionsCopyIn //通过NSCopying方法，复制后存入
};
- (instancetype)initWithOptions:(NSPointerFunctionsOptions)options capacity:(NSUInteger)initialCapacity
+ (NSHashTable<ObjectType> *)hashTableWithOptions:(NSPointerFunctionsOptions)options;
// NSPointerFunctions可以被用在 NSHashTable，NSMapTable和 NSPointerArray 中，定义了对存储在这个集合中的对象的获取和保留行为。
- (instancetype)initWithPointerFunctions:(NSPointerFunctions *)functions capacity:(NSUInteger)initialCapacity;
+ (NSHashTable<ObjectType> *)weakObjectsHashTable//返回一个新的哈希表，用于存储对其内容的弱引用。
存储相关 和set的方法类似
@property (readonly) NSUInteger count;
- (nullable ObjectType)member:(nullable ObjectType)object;
- (NSEnumerator<ObjectType> *)objectEnumerator;
- (void)addObject:(nullable ObjectType)object;
- (void)removeObject:(nullable ObjectType)object;
- (void)removeAllObjects;
@property (readonly, copy) NSArray<ObjectType> *allObjects; // convenience
@property (nullable, nonatomic, readonly) ObjectType anyObject;
- (BOOL)containsObject:(nullable ObjectType)anObject;
- (BOOL)intersectsHashTable:(NSHashTable<ObjectType> *)other;
- (BOOL)isEqualToHashTable:(NSHashTable<ObjectType> *)other;
- (BOOL)isSubsetOfHashTable:(NSHashTable<ObjectType> *)other;
- (void)intersectHashTable:(NSHashTable<ObjectType> *)other;
- (void)unionHashTable:(NSHashTable<ObjectType> *)other;
- (void)minusHashTable:(NSHashTable<ObjectType> *)other;
// 包含哈希表成员的集合。
@property (readonly, copy) NSSet<ObjectType> *setRepresentation;
性能
在iphone8plus的测试结果
操作数量: 1e+06 [run 3]
Adding to NSMutableSet: 252.297583 [ms]
Adding to NSHashTable: 240.465333 [ms]
Random Access for NSMutableSet: 1.272875 [ms]
Random Access for NSHashTable: 0.622708 [ms]
containsObject: for NSMutableSet: 2.146917 [ms]
containsObject: for NSHashTable: 2.073917 [ms]
NSFastEnumeration for NSMutableSet: 18.474125 [ms]
NSFastEnumeration for NSHashTable: 20.027208 [ms]
NSMapTable
NSMapTable 和 NSHashTable 相似，但是效仿的是 NSDictionary。可以分别控制键和值的对象获取/保留行为。存储弱引用是 NSMapTable 最有用的特性
创建时的选项除了使用 NSPointerFunctionsCopyIn，任何的默认行为都会 retain (或弱引用)键对象而不会拷贝它，这与 CFDictionary 的行为相同而与 NSDictionary 不同。当你需要一个字典，它的键没有实现 NSCopying 协议的时候（比如像 UIView），这会非常有用。
NSMapTable 没有下标访问,因为下标访问需要一个 id<NSCopying> 作为 key，对 NSMapTable 来说这不是强制的。如果不通过一个非法的 API 协议或者移除 NSCopying 协议来削弱全局下标，是没有办法给它增加下标的。
方法
create instance
- (instancetype)initWithKeyOptions:(NSPointerFunctionsOptions)keyOptions valueOptions:(NSPointerFunctionsOptions)valueOptions capacity:(NSUInteger)initialCapacity;
- (instancetype)initWithKeyPointerFunctions:(NSPointerFunctions *)keyFunctions valuePointerFunctions:(NSPointerFunctions *)valueFunctions capacity:(NSUInteger)initialCapacity;
+ (NSMapTable<KeyType, ObjectType> *)mapTableWithKeyOptions:(NSPointerFunctionsOptions)keyOptions valueOptions:(NSPointerFunctionsOptions)valueOptions;
+ (NSMapTable<KeyType, ObjectType> *)strongToStrongObjectsMapTable
+ (NSMapTable<KeyType, ObjectType> *)weakToStrongObjectsMapTable
+ (NSMapTable<KeyType, ObjectType> *)strongToWeakObjectsMapTable
+ (NSMapTable<KeyType, ObjectType> *)weakToWeakObjectsMapTable
normal
@property (readonly, copy) NSPointerFunctions *keyPointerFunctions;
@property (readonly, copy) NSPointerFunctions *valuePointerFunctions;
@property (readonly) NSUInteger count;
取值/赋值
- (nullable ObjectType)objectForKey:(nullable KeyType)aKey;
- (void)removeObjectForKey:(nullable KeyType)aKey;
- (void)setObject:(nullable ObjectType)anObject forKey:(nullable KeyType)aKey;
- (NSEnumerator<KeyType> *)keyEnumerator;
- (nullable NSEnumerator<ObjectType> *)objectEnumerator;
- (void)removeAllObjects;
- (NSDictionary<KeyType, ObjectType> *)dictionaryRepresentation;
性能
操作数量: 1e+06 [run 3]
Adding to NSMutableDictionary: 455.056208 [ms]
Adding to NSMapTable: 391.094500 [ms]
Random Access for NSMutableDictionary: 2.079417 [ms]
Random Access for NSMapTable: 2.577792 [ms]
NSPointerArray
NSPointerArray类是一个稀疏数组，与 NSMutableArray 相似，但可以存储 NULL 值，并且 count 方法会包括NULL。
你可以通过 allObjects 将一个 NSPointerArray 转换成常规的 NSArray。这时所有的 NULL 值会被去掉，只有真正存在的对象被加入到数组 — 因此数组的对象索引很有可能会跟指针数组的不同。注意：如果向指针数组中存入任何非对象的东西，执行 allObjects 会造成 EXC_BAD_ACCESS 崩溃，因为它会一个一个地去 retain ”对象”。
方法
create instance
- (instancetype)initWithOptions:(NSPointerFunctionsOptions)options NS_DESIGNATED_INITIALIZER;
- (instancetype)initWithPointerFunctions:(NSPointerFunctions *)functions NS_DESIGNATED_INITIALIZER;
+ (NSPointerArray *)pointerArrayWithOptions:(NSPointerFunctionsOptions)options;
+ (NSPointerArray *)pointerArrayWithPointerFunctions:(NSPointerFunctions *)functions;
+ (NSPointerArray *)strongObjectsPointerArray API_AVAILABLE(macos(10.8), ios(6.0), watchos(2.0), tvos(9.0));
+ (NSPointerArray *)weakObjectsPointerArray API_AVAILABLE(macos(10.8), ios(6.0), watchos(2.0), tvos(9.0));
normal
@property (readonly, copy) NSPointerFunctions *pointerFunctions;
@property NSUInteger count;
元素操作
- (nullable void *)pointerAtIndex:(NSUInteger)index;
@property (readonly, copy) NSArray *allObjects;
- (void)addPointer:(nullable void *)pointer;
- (void)removePointerAtIndex:(NSUInteger)index;
- (void)insertPointer:(nullable void *)item atIndex:(NSUInteger)index;
- (void)replacePointerAtIndex:(NSUInteger)index withPointer:(nullable void *)item;
- (void)compact; // 移除 NULLs
性能
操作数量: 100000 [run 2]
Adding to NSMutableArray: 12.129708 [ms]
Adding to NSPointerArray: 33877.992042 [ms]
Random Access for NSMutableArray: 0.064375 [ms]
Random Access for NSPointerArray: 0.218417 [ms]
NSPointerArray 需要的时间比 NSMutableArray 多了超过 2500 倍(!) 。
NSCache
NSCache默认为可变并且线程安全的。这使它很适合缓存那些创建起来代价高昂的对象。它自动对内存警告做出反应并基于可设置的”成本”清理自己。与 NSDictionary 相比，键是被 retain 而不是被 copy 的。
NSCache 的回收方法是不确定的，在文档中也没有说明。向里面放一些类似图片那样超大的对象并不是一个好主意，有可能它在能回收之前就更快地把你的 cache 给填满了。可以使用自定义的基于 LRU 的链表缓存
可以对 NSCache 进行设置，这样它就能自动回收那些实现了 NSDiscardableContent 协议的对象。实现了该属性的一个比较常用的类是 NSPurgeableData，
性能
相比 NSMutableDictionary ，NSCache 加入线程安全必然会带来一些消耗。自定义一个的线程安全的字典的子类 ,它通过 OSSpinLock 实现同步的访问。
操作数量: 1e+06 [run 3]
Adding to NSMutableDictionary: 538.419708 [ms]
Adding to ThreadSafeMutableDictionary: 667.958417 [ms]
Adding to NSCache: 2115.131667 [ms]
Random Access for NSMutableDictionary: 2.567792 [ms]
Random Access for ThreadSafeMutableDictionary: 3.498500 [ms]
Random Access for NSCache: 4.889792 [ms]
因为 NSCache 要多维护一个决定何时回收对象的成本系数。因此要慢一些.
NSIndexSet
有些场景下 NSIndexSet (和它的可变变体，NSMutableIndexSet) 真的非常出色，对它的使用贯穿在 Foundation 中。
它用一种非常高效的方法存储一组无符号整数的集合，尤其是如果只是一个或少量范围的时候。
正如 set 这个名字已经暗示的那样，每一个 NSUInteger 要么在索引 set 中，要么不在。如果你需要存储非唯一的数时，最好使用 NSArray。
性能
- (void)testIndexSetAndSetPerformance {
[@[@(10000), @(100000), @(1000000), @(10000000), @(20000000)] enumerateObjectsUsingBlock:^(NSNumber *entriesNumber, NSUInteger runCount, BOOL *stop) {
@autoreleasepool {
NSUInteger entries = entriesNumber.unsignedIntegerValue;
NSLog(@"操作数量: %g [run %tu]", (double)entries, runCount+1);
NSLog(@"\n");
NSMutableSet *randomAccessNumbers = [NSMutableSet set];
for (NSUInteger accessIdx = 0; accessIdx < entries/100; accessIdx++) {
[randomAccessNumbers addObject:@(arc4random_uniform((u_int32_t)entries))];
}
// 添加
NSMutableIndexSet *indexSet = [NSMutableIndexSet indexSet];
double indexSetPerf = PerformAndTrackTime(^{
[randomAccessNumbers enumerateObjectsUsingBlock:^(NSNumber *number, BOOL *stop) {
[indexSet addIndex:number.unsignedIntegerValue];
}];
});
// 查找
double setIndexRAC = PerformAndTrackTime(^{
[randomAccessNumbers enumerateObjectsUsingBlock:^(NSNumber *number, BOOL *stop) {
[indexSet containsIndex:number.unsignedIntegerValue];
}];
});
// 添加
NSMutableSet *set = [NSMutableSet set];
double setPerf = PerformAndTrackTime(^{
[randomAccessNumbers enumerateObjectsUsingBlock:^(NSNumber *number, BOOL *stop) {
__unused NSUInteger index = number.unsignedIntegerValue;
[set addObject:number];
}];
});
// 查找
double setRAC = PerformAndTrackTime(^{
[randomAccessNumbers enumerateObjectsUsingBlock:^(NSNumber *number, BOOL *stop) {
__unused NSUInteger index = number.unsignedIntegerValue;
[set containsObject:number];
}];
});
NSLog(@"添加: NSIndexSet: %f [ms]. NSSet: %f [ms]", indexSetPerf/1E6, setPerf/1E6);
NSLog(@"随机访问: NSIndexSet: %f [ms]. NSSet: %f [ms]", setIndexRAC/1E6, setRAC/1E6);
NSLog(@"\n");
}
}];
}
操作数量: 2e+07 [run 5]
添加: NSIndexSet: 13991.324625 [ms]. NSSet: 58.806875 [ms]
随机访问: NSIndexSet: 46.383500 [ms]. NSSet: 27.283792 [ms]
网友评论