0

我有一个NSArray对象和一个带有双精度数的 C 数组。我想NSArray根据 C 数组值对对象进行排序。

我能想到的唯一方法如下（基于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 之间。

4

4 回答 4

1

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

之后，您应该测试当前的解决方案。在对预期数量的值进行排序时，用户是否必须等待太长时间？

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

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

首先想到的是将数组映射到字典中，对字典进行排序，然后映射回排序后的数组。

首先，获取一个映射类别（这是我在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-15T10:14:03.353 回答
1

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

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

如果您绝对不能拥有一个双精度值的属性（实际上，您总是可以使用关联对象），您可以创建一个包装器对象，其中一个属性是原始对象，一个属性是双精度值并排序一个数组。但是，这非常昂贵（大量分配），因此您肯定要先进行其他两个答案建议的分析。

于 2013-10-15T10:31:50.243 回答
1

在没有真正问题的情况下推测潜在的性能问题是没有意义的。

如果你可以用你的代码测量一个实际的问题（例如通过在 Instruments 中使用 Time Profiler），你就会知道瓶颈可能在哪里。在您的代码中，有几个地方可能会减慢排序速度（将每个数字装箱以计算NSComparisonResult来自 ARC 的保留/释放开销，仅用于访问数组中的对象，...）。

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

如果我猜测一下似乎可以提高性能的候选者，我会说应该消除两个数组的一般问题，其中元素形成一个元组而不是一个元组数组。这是一个 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-15T10:16:11.587 回答
0

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

于 2013-10-15T10:46:16.657 回答