4

今朝、このスレッドに出くわしました。並べ替えられた配列を処理する方が、並べ替えられていない配列よりも速いのはなぜですか? 本当に面白いと思いました!

Objective-C で試してみたかったのですが、実装中に整数の配列をソートするという問題に直面しました。したがって、次の質問です。

arraySize0 から 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];
}

それは機能しますが、それは本当に苦痛であり、まったく最適化されていないようです! どうすればこれを改善できますか?

4

3 に答える 3

8

「最適化されていない」ステートメントは、あなたが持っているコードにのみ当てはまります。Apple のフレームワークは高度に最適化されており、Apple を再考することは想定されていません。

まず、作成された目的のためにメソッドを使用します。ソートされていない配列を作成する方法は、メモリを浪費するだけです。ループのすべてのステップで、配列の新しいインスタンスを作成しています。最終的には、256 (または元の整数配列のカウントが何であれ) の配列になります。これは余分です。

したがって、この問題を解決するためにどうしてもObjective-C を使用したい場合は、変更可能な配列を使用できます。必要なのは 1 つだけです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:)];

ところで、ここでは 2 つのループ (C 配列に入力するためのループと、それを に変換するためのループNSMutableArray) も不要です。あなたはただ書くことができます

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)];

また、配列についてこれを読んでください。本当に良い記事です。

于 2012-11-02T11:01:25.467 に答える
0

NSSortDescriptor の使用はどうですか?

NSSortDescriptor *descriptor = [[NSSortDescriptor alloc] initWithKey:@"propertieToSort" ascending:NO];
NSArray *descArray = [NSArray arrayWithObject:dateDescriptor];
representedItems = [unsortedItems sortedArrayUsingDescriptors:descArray];

これが非 NSObjects で動作するかどうかは 100% 確信が持てませんが、いつか使用したことを誓います。

于 2012-11-02T11:04:07.500 に答える
0

obj-c プロジェクトで c++ を使用できます。ファイルの名前を .mm に変更し、std.sort を使用するために #include < アルゴリズム > を追加するだけです。int データに NSNumber を使用する方が高速になると思います

于 2012-11-02T11:04:27.423 に答える