4

我有一个 Objective-C 应用程序，我试图在对具有相同排序值的数组元素进行分组时对 NSArray 进行排序。理想情况下，我会生成一个新的集合数组，其中新数组中的每个集合都包含一个或多个原始数组元素，并且每个集合中的所有元素都具有相同的排序值。它的工作方式类似于Ruby“块”方法

举个例子，假设我有一个 NSArray，其中包含排序值等于以下内容的项：

[1, 3, 5, 7, 9, 8, 5, 3, 2, 4, 3, 6]

我希望新数组包含 9 个集合，其排序值如下所示：

[ (1), (2), (3, 3, 3), (4), (5, 5), (6), (7), (8), (9) ]

在 Ruby 中，我可以先对数组进行排序，然后将其分块以获得我想要的。我试图在Objective-C中提出一种合理有效的方法。

我可以设置一个字典，其中包含每个可能的排序值作为键，NSSet 作为每个键的值。然后，我可以遍历初始数组，计算每个项目的排序值，为该排序值找到合适的键，并随时更新它的集合。我终于可以对该字典的内容进行排序以获得排序集的列表。

我可以做到这一切，但似乎应该有一个更好的方法，我错过了。此外，我排序的值实际上可能是浮点值，因此将它们用作字典中的键可能价值有限。

谁能想到一个更聪明的方法来做到这一点？我在这里遗漏了一些明显的东西吗？

4

2 回答 2

3

如果您只需要对象出现的次数，那么库尔特的答案就很好了。但是，如果您确实需要分块，则应该可以：

NSArray *original = @[@1, @3, @5, @7, @9, @8, @5, @3, @2, @4, @3, @6];
NSMutableArray *chunked = [NSMutableArray array];

NSNumber *current = nil;
for (NSNumber *number in [original sortedArrayUsingSelector:@selector(compare:)]) {
    if (![number isEqual:current]) {
        [chunked addObject:[NSMutableArray arrayWithObject:number]];
        current = number;
    } else {
        [[chunked lastObject] addObject:number];
    }
}

NSLog(@"%@", chunked);

除非我遗漏了什么，否则这在计算上并不复杂，并且应该比 Tim 的原始方法更有效（不需要字典、集合或散列）。涉及一种排序（在快速枚举中，容器 - 之后的部分in- 仅评估一次），并且您迭代排序数组一次。NSMutableArray插入O(1)在任一端，所以最坏的情况应该是O(n)因为迭代。

实际上：经过进一步审查，以下代码对于大量数字的运行速度要快得多。它稍微复杂一些，但运行效率更高。

NSArray *original = @[@1, @3, @5, @7, @9, @8, @5, @3, @2, @4, @3, @6];
NSMutableArray *chunked = [NSMutableArray array];

NSCountedSet *countedSet = [[NSCountedSet alloc] initWithArray:original];
for (NSNumber *number in countedSet) {
    NSMutableArray *chunk = [NSMutableArray array];
    NSUInteger count = [set countForObject:number];
    for (NSUInteger i = 0; i < count; i++) {
        [chunk addObject:number];
    }

    [chunked addObject:chunk];
}

[chunked sortUsingComparator:^(NSArray *a1, NSArray *a2) {
    return [a1[0] compare:a2[0]];
}];

NSLog(@"%@", chunked);

使用10000000随机数，第一个实现大约在几12.27秒钟内运行，而第二个实现在0.92几秒钟​​内运行。去搞清楚。

第二种方法的缺点是它创建的块都是同一个对象的副本。如果这给您带来了问题（在一般情况下，内存管理可能有问题，或者如果您的对象在某种意义上可以被认为是“平等的”，即使它们的所有属性都不完全如此），那么使用第一个方法。否则，这对你会更好。

补充说明：进一步思考，我知道这两种方法之间的时间差异有些可疑，我是对的。如果您的数据集有很多变化（重复数字很少），方法 2 的运行速度会慢得多；数字的变化对方法 1 的影响不大。对于许多重复的数字，方法 2 会很快，但如果您的数据集是完全随机的，您最好使用方法 1。

这是我用来测试这两个的代码：http: //pastebin.com/9syEyiyM

于 2013-09-08T01:24:51.287 回答
1

为什么不使用一个NSCountedSet来存储所有键和每个键的计数？

NSArray *sourceArray = @[ @1, @3, @5, @7, @9, @8, @5, @3, @2, @4, @3, @6 ];
NSCountedSet *countedSet = [[NSCountedSet alloc] initWithArray:sourceArray];

NSArray* sortedKeys = [[countedSet allObjects] sortedArrayUsingSelector:@selector(compare:)];
for (NSNumber *key in sortedKeys) {
    NSUInteger count = [countedSet countForObject:key];
    NSLog(@"Key: %@ count: %ld", key, (unsigned long)count);
}
于 2013-09-08T01:09:59.013 回答