基于C数组值排序`NSArray`

我有一个NSArray与对象和一个C数组与双打。我想根据C数组值排序NSArray对象。基于C数组值排序`NSArray`

我能想到的唯一的办法是以下（基于this SO question）：

NSArray *sortedArray; 
sortedArray = [origArray sortedArrayUsingComparator:^NSComparisonResult(id a, id b) 
{ 
    // Getting c array values at the same indices as the objects being compared 
    NSNumber *aValue = @(cArray[[origArray indexOfObject:a]]); 
    NSNumber *bValue = @(cArray[[origArray indexOfObject:b]]); 
    // Returning comparison result 
    return [aValue compare:bValue]; 
}];

但我认为indexOfObject:部分是有点昂贵。是这样吗？

如果是这样，有没有更快的方法来做到这一点？

编辑：

为了提供更多的背景下，此排序是优化算法健身评估的一部分。在我的计划中，我做了一个基本的分析，并且健身评估代码变成了瓶颈。因此，我试图优化它。

此外，阵列中元素的数量预计将从大约100到10k最大。

来源

2013-10-15 insys

没有真正的潜在性能问题，没有任何意义。

如果您可以测量您的代码的实际问题（例如通过在乐器中使用Time Profiler），您会了解瓶颈的位置。在你的代码中有几个点可能会减慢排序（装箱每个数字来计算NSComparisonResult，保留/释放ARC的开销，仅仅用于访问数组中的对象，...）。

有几种方法可以提高性能，但它们取决于实际数据（origArray中的对象数量，C数组的双精度数据源......）。

如果我猜测可能看起来是性能增强的候选人，我会说两个数组形成一个元组而不是一个元组数组应该被消除。下面是该阵列与一个小的开销排序C函数：

NSArray *sortedObjects(double valuesArray[], NSArray *objects) 
{ 
    NSUInteger count = [objects count]; 
    struct tuple { 
     double value; 
     __unsafe_unretained id object; 
    } tupleArray[count]; 

    for (NSUInteger i = 0; i < count; ++i) 
     tupleArray[i] = (struct tuple){ valuesArray[i], objects[i] }; 

    qsort_b(tupleArray, count, sizeof tupleArray[0], ^int(const void *a, const void *b) { 
     double v = ((const struct tuple *)a)->value - ((const struct tuple *)b)->value; 
     return v == 0 ? 0 : v > 0 ? 1 : -1; 
    }); 

    __unsafe_unretained id objectsArray[count]; 
    for (NSUInteger i = 0; i < count; ++i) 
     objectsArray[i] = tupleArray[i].object; 

    return [[NSArray alloc] initWithObjects:objectsArray count:count]; 
}

来源

2013-10-15 10:16:11

谢谢你的回答和清晰优雅的例子。我在我的问题中添加了一些信息以供澄清。如果我理解正确，这里的一般方法会以某种方式创建一个元组（通过结构或通过关联对象或常规对象，如@JeremyP建议的）来创建对象排序值对。 – insys

直到你知道这是一个问题之前，不要优化排序。首先你需要回答一些问题。数组中会有多少个值？用户可以等待多长时间？

之后，您应该测试当前的解决方案。排序期望值的数量时，用户是否需要等待太久？

接下来，回答其他架构问题。例如，您可以在用户正在做其他工作的同时在后台对数组进行排序吗？

如果你做了所有这些，你发现一个问题，那么你可以开始考虑如何优化。

首先想到的是将数组映射到字典中，对字典进行排序，然后映射回已排序的数组。首先得到一个映射类别（这里是我在NSArray Equivalent of Map找到的一个）。

@interface NSArray (Map) 
- (NSArray *)mapObjectsUsingBlock:(id (^)(id obj, NSUInteger idx))block; 
@end 

@implementation NSArray (Map) 
- (NSArray *)mapObjectsUsingBlock:(id (^)(id obj, NSUInteger idx))block { 
    NSMutableArray *result = [NSMutableArray arrayWithCapacity:[self count]]; 
    [self enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) { 
     [result addObject:block(obj, idx)]; 
    }]; 
    return result; 
} 
@end

一旦你有你选择的映射方法，然后运行新的排序。

// Step 1) Map into an array of a dictionaries 
NSArray *dicts = [origArray mapObjectsUsingBlock:^(id obj, NSUInteger idx) { 
    return @{ @"value": obj, @"sortValue": @(cArray[idx]) }; 
}]; 

// Step 2) Sort the dictionaries 
NSArray *sortedDicts = [dicts sortedArrayUsingComparator:^NSComparisonResult(id a, id b) 
{ 
    return [a[@"sortValue"] compare:b[@"sortValue"]]; 
}]; 

// Step 3) Map back to the sorted array 
sortedArray = [sortedDicts mapObjectsUsingBlock:^(id obj, NSUInteger idx) { 
    return obj[@"value"]; 
}];

了这一切之后，你需要重复的测试来回答这个问题，“是否有用户排序值的预期数量时等待太久？”如果答案仍然是肯定的，用户必须等待太久，那么您需要再次寻找新的解决方案。

来源

2013-10-15 10:14:03

感谢您的答案和有趣的方法。 – insys

如果是这样，有没有这样做的任何更快的方法？

那么显而易见的问题是为什么不是你的对象的双值属性？

如果绝对不能有一个属性是double值（实际上，您始终可以通过使用associated objects），您可以创建包装对象，其中一个属性是原始对象，另一个属性是双倍属性值并对这些数组进行排序。然而，这是相当昂贵的（大量分配），所以你一定要先做另外两个答案建议的分析。

来源

2013-10-15 10:31:50 JeremyP

谢谢你参考相关的对象，我没有意识到它。关于答案的第二部分，我想避免创建包装器对象，因为每次都需要使用不同的排序值排序不同的对象（因此包装器不能被缓存）。因此，我认为（正如你所指出的那样）这种方法会产生很大的开销。 – insys

另一方面，我相信它仍然会比我在问题中提出的方法更好。 – insys

如果您的单一关注点是indexOfObject:的开销，您可能需要使用indexOfObjectIdenticalTo:。它省略了每个元素的isEqual:消息，如果数组有很多元素，可能会更快。

来源

2013-10-15 10:46:16

基于C数组值排序`NSArray`

回答

相关问题