3

私は以前に関数をいじっていましNSArrayたが、NSArrayをランダム化する最も簡単な方法に遭遇した可能性があると思います。

NSArray *randomize(NSArray *arr)
{
    return [arr sortedArrayUsingComparator:^NSComparisonResult(id obj1, id obj2) {
        return arc4random_uniform(3) - 1; // one of -1, 0, or 1
    }];
}

これは、理論的には、NSArrayを完全にランダム化する必要があります。しかし、かなり考えた結果、NSArrayで使用されるソートアルゴリズムによっては、これが安全ではなく、理論的には無限ループになる可能性があるのではないかと考えました。

これを10〜100000のサイズのアレイでテストしたところ、線形のパフォーマンスの違い（N * (log10(N) + 2)ランダム化ごとの比較について）が見られましたが、これは悪くありません。

ただし、NSArrayが理論的にそれ自体をソートできず、アプリケーションがクラッシュする可能性がある状況はありますか？それは起こらないはずだと私には思えますが、あなたは決して知りません。

4

3 に答える 3

1

これは、基礎となるソートアルゴリズムに依存すると思います。

基になるソートがバブルソートである場合に何が起こるかを考えてください。これは、要素のペアを比較するときはいつでも、それらを交換する可能性が1/3あることを意味します（比較によって順序が狂って見える場合）。したがって、この比較関数を使用してn個の要素の配列を並べ替える場合、アルゴリズムが各ステップで終了する確率は、どの比較も「順序が正しくない」と評価されない確率と等しくなります。各比較は確率1/3で「故障」と言っているので、これは、アルゴリズムが各反復で終了する確率が（2/3）nであることを意味します。これは、アルゴリズムが終了するまでの予想される反復回数が（3/2）n = 3 n / 2nであることを意味します。。適度なサイズの配列（たとえば、n = 1000）に対してこのアルゴリズムを実行しようとすると、予想される反復回数は驚くほど膨大になります。n = 1000は、1.233840597×10176の予想される反復を与えます！このアルゴリズムは最終的には終了しますが、予想される実行時間は非常に長いため、実用的な観点からは事実上無限です。

一方、選択ソートなどの別のアルゴリズムを使用しようとすると、均一な分布が得られるとは限りません。たとえば、位置1に配置する要素を見つけるアルゴリズムの最初のパスについて考えてみます。配列内のすべての要素は（分布が本当に均一である場合）最初に配置される確率が1/nである必要があります。しかし、そうではありません。最初の要素は、何かと交換されない限り、最初の位置に保持されることに注意してください。これは、最初のスキャン中の任意の時点で比較が+1（または内部によっては-1）になった場合にのみ発生します。すべての比較が異なる値で返される確率は（2/3）n-1です。、これは1/nと同じではありません。実際、ソートが完了すると、シーケンスの最初の要素が先頭に来ることは天文学的にはありそうにありません。したがって、アルゴリズムが終了しても、均一にランダムな分布が得られる保証はありません。

クイックソート、ヒープソート、マージソートなどを使用しようとすると、アルゴリズムは最終的に終了しますが、ランダムであることが保証されているかどうかはわかりません。これが少しの間均一にランダムであるかどうかを考えてから、答えを更新します。

お役に立てれば！

于 2012-08-16T00:23:41.620 に答える
0

NSArrayが多かれ少なかれ標準の安定したマージソートアルゴリズムを使用すると仮定しましょう。マージソートは要素をそれ自体と比較しないため、コンパレータが-1と1のみを返す場合におそらく最適です。

4要素配列123 4の場合、マージソートは前半と後半をランダム化してからマージします。L = [ab] = [12]または[21]であり、R = [cd] = [34]または[43]の場合、マージ決定木（非決定が抑制されている）は次のようになります。

       [a b c d]   [a c b d]
      /           /
   [a]-------[a c]-[a c d b]
  /
[]
  \   
   [c]-------[c a]-[c a b d]
      \           \
       [c d a b]   [c a d b]

[LLRR]の形式のシーケンス（たとえば、[1 2 3 4]、[2 1 3 4]、[1 2 4 3]、[2 1 4 3]）は、合計確率1/6（各1/24）である必要があります。 ）しかし、確率は1/4です。[RRLL]も同様です。[LRLR]の形式のシーケンスは、合計確率1/6である必要がありますが、確率1/8です。[LRRL]、[RLLR]、[RLRL]についても同様です。これは均一ではありません。

さらに重要なのは、コンパレータが全順序と一致する決定論的な回答を提供するという契約に違反していることです（私が読んだドキュメントでは明らかに暗黙的ですが、この契約の類似した変形は非常に一般的です）。これは、Appleのコードが例外をスローするか、終了しないことによって、契約の終了に自由に違反できることを意味します。それは本当に永遠に実行されますか？おそらくそうではないかもしれませんが、もしそうなら、そしてあなたがAppleにバグレポートを提出したなら、彼らは笑ってあなたを驚かせるでしょう。ほとんどのプログラマーは彼らに同意すると思います。ソフトウェアライブラリの不特定の側面に依存するのは良い習慣ではありません。

于 2012-08-16T05:46:24.457 に答える
0

この問題は解決されました。http://en.wikipedia.org/wiki/Knuth_shuffle

templatetypedefもこれについてコメントしました。

フィッシャー-イェーツシャッフルamutableCopyは非常に高速で、ランダム化が優れています。小さな配列（10要素）の場合、以下に実装されているように、提案はフィッシャー-イェーツシャッフルよりもわずかに高速です。大きな配列（1000000要素）の場合、Fisher_Yatesはあなたの配列の4倍高速です。作成した可変コピーを返すことに問題がない場合は、Fisher-Yatesの方が10要素の方が高速です。

私は、小さいサイズと大きいサイズの両方で高速な優れたシャッフルアルゴを使用します。

これがプログラムです-あなたはInstrumentsの使い方を知っています！

#import <Foundation/Foundation.h>

static NSArray * imp_RandomizeUsingSortedArrayUsingComparator(NSArray * arr) {
    return [arr sortedArrayUsingComparator:^NSComparisonResult(id obj1, id obj2) {
        return arc4random_uniform(3) - 1; // one of -1, 0, or 1
    }];
}
__attribute__((__noinline__)) static void RandomizeUsingSortedArrayUsingComparator(NSArray * arr) {
    @autoreleasepool { imp_RandomizeUsingSortedArrayUsingComparator(arr); }
}

static NSArray * imp_RandomizeUsingMutableCopy(NSArray * arr) {
    if (1 >= arr.count) {
        return [arr.copy autorelease];
    }
    NSMutableArray * cp = [arr.mutableCopy autorelease];
    u_int32_t i = (u_int32_t)cp.count;
    while (i > 1) {
        --i;
        const u_int32_t j = arc4random_uniform(i);
        [cp exchangeObjectAtIndex:i withObjectAtIndex:j];
    }
    // you may not favor creating the concrete copy
    return [cp.copy autorelease];
}

__attribute__((__noinline__)) static void RandomizeUsingMutableCopy(NSArray * arr) {
    @autoreleasepool { imp_RandomizeUsingMutableCopy(arr); }
}


int main(int argc, const char * argv[]) {
    @autoreleasepool {
        NSMutableArray * filled = [NSMutableArray array];
        for (NSUInteger i = 0; i < 1000000; ++i) {
            [filled addObject:@""];
        }

        NSArray * concrete = filled.copy;
        for (NSUInteger i = 0; i < 100; ++i) {
            RandomizeUsingSortedArrayUsingComparator(concrete);
            RandomizeUsingMutableCopy(concrete);
        }
        [concrete release];
    }
    return 0;
}
于 2012-08-16T06:27:48.150 に答える