使用Objective-C对int数组进行排序 - 优化

Question

今天早上,我偶然发现了这个线程为什么处理排序数组比处理未排序数组更快？并发现它真的很有趣!

我想在Objective-C中试一试,在实现它时,我遇到了整数数组的问题.因此,以下问题.

让我们考虑一个arraySize整数数组,用0到256之间的随机值初始化:

int data[arraySize];
for (int c = 0; c < arraySize; ++c)
{
    data[c] = arc4random() % 256;
}

我想对这个数组进行排序,并将结果存储在另一个整数数组中.在C++中我们可以做类似的事情:

std::sort(data, ...);

在Java中,我们将使用:

Arrays.sort(data);

在Objective-C中,我这样做了:

int sortedData[arraySize];
NSArray* sortedArray = [NSArray array];
// Initialize the array to sort.
for ( int i = 0 ; i < arraySize ; ++i )
{
    sortedArray = [sortedArray arrayByAddingObject:[NSNumber numberWithInt:data[i]]];
}
// Sort the array.
sortedArray = [sortedArray sortedArrayUsingSelector:@selector(compare:)];
// Copy the array back into a int[] array.
for (int c = 0; c < arraySize; ++c)
{
    sortedData[c] = [sortedArray[c] intValue];
}

它有效,但在我看来这是一个真正的痛苦,它根本没有优化!我怎么能改善这个？

Answer 1

"非优化"语句仅适用于您拥有的代码.Apple的框架经过高度优化,你不应该再猜测Apple,他们已经第二次猜到了你.

首先,将方法用于创建它们的目的.你创建未排序数组的方式只会浪费内存.在循环的每一步中,你都在创建一个新的数组实例,最后,你最终会得到256(或原始整数数组的数量)数组,这只是多余的.

所以,如果你真的非常想使用Objective-C解决这个问题,你可以使用一个可变数组,你只需要一个NSMutableArray:

int array[256];
// populate the C array here

NSMutableArray *objcArray = [NSMutableArray array];
for (int i = 0; i < sizeof(array) / sizeof(*array); i++) {
    [objcArray addObject:[NSNumber numberWithInt:array[i]];
}

[objcArray sortUsingSelector:@selector(compare:)];

顺便说一下,NSMutableArray这里不需要两个循环(一个用于填充C数组,一个用于将其转换为一个).你可以写

const size_t size = 256;
NSMutableArray *objcArray = [NSMutableArray array];
for (int i = 0; i < size; i++) {
    [objcArray addObject:[NSNumber numberWithInt:arc4random_uniform(256)];
}

[objcArray sortUsingSelector:@selector(compare:)];

但是,您并不需要Objective-C来对整数数组进行排序.您可以简单地编写一个C函数(或者如果您需要,使用Objective-C方法)来对就地整数数组进行排序,这可以更有效或更快:

#include <math.h>
#include <stdlib.h>
#include <unistd.h>

int compare(const void *first, const void *second)
{
    return *(const int *)first - *(const int *)second;
}

- (void)sortArray:(int *)array ofSize:(size_t)sz
{
    qsort(array, sz, sizeof(*array), compare);
}

然后像这样使用它:

int array[256];
for (int i = 0; i < sizeof(array) / sizeof(*array); i++) {
    array[i] = arc4random_uniform(256);
}

[self sortArray:array ofSize:sizeof(array) / sizeof(*array)];

另外,请阅读有关数组的内容.真的好文章.