2

我有以下NSDictionary结构：

// level
0    1    2    3

// elements
a1 - b1 - c1 - d111.1
             - d111.2
             - d111.3
          c2 - d112.1
             - d112.2
          c3 - d113.1

考虑到数据文件将包含 2000-5000 个元素。什么是只计算第 3 级（a1=0）上的孩子的快速方法？需要明确的是：我不想包括在计数中：a1，b1，c1-c3，只有 d*。

这是你可以用 NSPredicate 做的事情吗？

还是老式（但昂贵）的 for 循环方法（eeks）？

// pseudo-code
count=0
for (a in root)
 for (b in a)
   for (c in b)
     for (d in c)
       count++

谢谢。

4

3 回答 3

1

正如@Hot 所说： 

int count = 0;
   for (NSArray *a in root)
      for (NSArray *b in a)
         for (NSArray *c in b)
            count += c.count;

仅仅通过关卡直到最后一个级别，然后只使用计数，实际上并没有太多开销。

于 2013-01-05T23:07:13.797 回答
1

使用类别的解决方案。

@implementation NSDictionary (RecursiveCount)
- (NSUInteger)recursiveCount {
    return self.allValues.recursiveCount;
}
@end

@implementation NSArray (RecursiveCount)
- (NSUInteger)recursiveCount {
    int count = 0;
    for (id object in self) {
        if ([object isKindOfClass:[NSDictionary class]] || [object isKindOfClass:[NSArray class]]) {
            count += [object recursiveCount];
        } else {
            ++count;
        }
    }
    return count;
}
@end

- (void)testRecursiveCount {
    NSDictionary *dict = @{
                           @"key1" : @[@1, @2, @3],
                           @"key2" : @{@"blah" : @[@[], @1, @[@1, @2]]},
                           @"key3" : @4,
                           @"key5" : @[@{@"blah":@[@{@1:@1}]}],
                           };
    XCTAssertEqual(dict.recursiveCount, 8, @"dictionary");

    NSArray *array = @[
                       @[@1, @2, @3],
                       @{@"blah" : @[@[], @1, @[@1, @2]]},
                       @4,
                       @[@{@"blah":@[@{@1:@1}]}],
                       ];
    XCTAssertEqual(array.recursiveCount, 8, @"dictionary");
}
于 2014-07-23T20:31:48.460 回答
0

一种方法是使用递归。这种方法不是最便宜的，但它确实具有灵活性的优势——如果结构的深度发生变化或者在编译时是未知的。

在伪代码中：

integer count ( collection , maxDepth )
    return recursiveCount ( collection , 0 , maxDepth )
end

integer recursiveCount ( collection , currentDepth , maxDepth )
    integer count = 0
    if collection is array
        count += recursiveCountArray ( collection , currentDepth , maxDepth )
    else if object is dictionary
        count += recursiveCountDictionary ( collection.values , currentDepth , maxDepth )
    else
        count += 1
    return count
end

integer recursiveCountArray ( array , currentDepth , maxDepth )
    integer count = 0
    if currentDepth < maxDepth
        for ( object in array )
            count += recursiveCount( object )
    else
        count += array.count
    return count
end

该maxDepth参数确保不会完成不必要的工作（只需在 maxDepth 时返回数组的计数，而不是像@RamyAlZuhouri 在他的评论中建议的那样在每次迭代中迭代数组并增加计数）。

在 Objective-C 中，这可以通过 C 函数来实现：

static NSUInteger _PFXRecursiveCount(id collection, NSUInteger currentDepth, NSUInteger maxDepth);
static NSUInteger _PFXRecursiveCountArray(id array, NSUInteger currentDepth, NSUInteger maxDepth);

NSUInteger PFXRecursiveCount(id collection, NSUInteger maxDepth)
{
    return _PFXRecursiveCount(collection, 0, maxDepth);
}

NSUInteger _PFXRecursiveCount(id collection, NSUInteger currentDepth, NSUInteger maxDepth)
{
    NSUInteger count = 0;
    if ([collection isKindOfClass:[NSArray class]]) {
        count = _PFXRecursiveCountArray(collection, currentDepth, maxDepth);
    } else if ([collection isKindOfClass:[NSDictionary class]]) {
        NSDictionary *dictionary = (NSDictionary *)collection;
        count = _PFXRecursiveCountArray(dictionary.allValues, currentDepth, maxDepth);
    } else {
        count = 1;
    }
    return count;
}

NSUInteger _PFXRecursiveCountArray(NSArray *array, NSUInteger currentDepth, NSUInteger maxDepth)
{
    NSUInteger count = 0;
    if (currentDepth < maxDepth) {
        for (id object in array) {
            count += _PFXRecursiveCount(object, currentDepth + 1, maxDepth);
        }
    } else {
        count += array.count;
    }
    return count;
}

这里PFX将替换为项目中使用的适当前缀。只会PFXRecursiveCount在标题中声明。

或者，这可以通过块来实现：

typedef NSUInteger (^RecursiveCountArrayBlock)(NSArray *, NSUInteger, NSUInteger);
typedef NSUInteger (^RecursiveCountBlock)(id, NSUInteger, NSUInteger);

__block __weak RecursiveCountArrayBlock _weakRecursiveCountArray = nil;
__block __weak RecursiveCountBlock _weakRecursiveCount = nil;

NSUInteger (^_recursiveCount)(id, NSUInteger, NSUInteger) = ^(id collection, NSUInteger currentDepth, NSUInteger maxDepth) {
    NSUInteger count = 0;
    if ([collection isKindOfClass:[NSArray class]]) {
        count = _weakRecursiveCountArray(collection, currentDepth, maxDepth);
    } else if ([collection isKindOfClass:[NSDictionary class]]) {
        NSDictionary *dictionary = (NSDictionary *)collection;
        count = _weakRecursiveCountArray(dictionary.allValues, currentDepth, maxDepth);
    } else {
        count = 1;
    }
    return count;
};
_weakRecursiveCount = _recursiveCount;

NSUInteger (^_recursiveCountArray)(id, NSUInteger, NSUInteger) = ^(NSArray *array, NSUInteger currentDepth, NSUInteger maxDepth) {
    NSUInteger count = 0;
    if (currentDepth < maxDepth) {
        for (id object in array) {
            count += _weakRecursiveCount(object, currentDepth + 1, maxDepth);
        }
    } else {
        count += array.count;
    }
    return count;
};
_weakRecursiveCountArray = _recursiveCountArray;

NSUInteger (^recursiveCount)(id, NSUInteger) = ^(id collection, NSUInteger maxDepth) {
    return _recursiveCount(collection, 0, maxDepth);
};

__weak __block变量 (_weakRecursiveCountArray和_weakRecursiveCount) 允许我们避免从自身内部对块的强引用。（注意：在 iOS 5 和 10.7 之前，__weak需要替换为__unsafe_unretained。） typedef 允许我们避免虚假警告（“'__weak' 仅适用于 Objective-c 对象或块指针类型；这里的类型是 'NSUInteger' （又名'无符号长'）”）。

于 2013-01-06T04:44:10.097 回答