0

一致する組み合わせの配列を生成する必要がある PhoneGap モバイル アプリケーションがあります。JavaScript 側では、組み合わせが生成される配列が少し大きくなると、すぐにコードがハングアップしました。そこで、プラグインを作成して組み合わせを生成し、javascript オブジェクトの配列をネイティブ側に渡してそこでループさせようと考えました。

驚いたことに、次のコードは 150 ミリ秒 (JavaScript) で実行されますが、ネイティブ側 (Objective-C) では約 1000 ミリ秒かかります。

これらの実行時間を短縮するためのヒントを知っている人はいますか? プレイヤーが 10 人を超えると、つまり、チームの配列の長さが 252 に等しくなると、実際に遅くなります。上記の実行時間は、10 プレイヤー / 252 チームの場合です。

JavaScript コードは次のとおりです。 

for (i = 0; i < GAME.teams.length; i += 1) {
            for (j = i + 1; j < GAME.teams.length; j += 1) {
                t1                  = GAME.teams[i];
                t2                  = GAME.teams[j];

                if ((t1.mask & t2.mask) === 0) {

                    GAME.matches.push({
                        Team1: t1,
                        Team2: t2
                    });
                }
            }
}

...そしてこれがネイティブコードです: 

NSArray *teams = [[NSArray alloc] initWithArray: [options objectForKey:@"teams"]];
NSMutableArray *t = [[NSMutableArray alloc] init];
int mask_t1;
int mask_t2;

for (NSInteger i = 0; i < [teams count]; i++) {
        for (NSInteger j = i + 1; j < [teams count]; j++) {

            mask_t1     = [[[teams objectAtIndex:i] objectForKey:@"mask"] intValue];
            mask_t2     = [[[teams objectAtIndex:j] objectForKey:@"mask"] intValue];

            if ((mask_t1 & mask_t2) == 0) {
                [t insertObject:[teams objectAtIndex:i] atIndex:0];
                [t insertObject:[teams objectAtIndex:j] atIndex:1];
                /*
                NSArray *newCombination = [[NSArray alloc] initWithObjects:
                                           [teams objectAtIndex:i],
                                           [teams objectAtIndex:j],
                                           nil];
                */
                [combinations addObject:t];
            }
        }
}

... 問題の配列 (GAME.teams) は次のようになります。 

{
    count = 2;
    full = 1;
    list =         (
                    {
            index = 0;
            mask = 1;
            name = A;
            score = 0;
        },
                    {
            index = 1;
            mask = 2;
            name = B;
            score = 0;
        }
    );
    mask = 3;
    name = A;
},
    {
    count = 2;
    full = 1;
    list =         (
                    {
            index = 0;
            mask = 1;
            name = A;
            score = 0;
        },
                    {
            index = 2;
            mask = 4;
            name = C;
            score = 0;
        }
    );
    mask = 5;
    name = A;
},
4

2 に答える 2

2

通常、パフォーマンスに問題がある場合は、Time Profiler インストゥルメントを使用してアプリをプロファイリングする必要があります。

この場合、考えられる問題がいくつか見られます。

まず、内側のループでこれを行っています。

[t insertObject:[teams objectAtIndex:i] atIndex:0];
[t insertObject:[teams objectAtIndex:j] atIndex:1];

オブジェクトの先頭にますます多くのオブジェクトを挿入しているだけですt。あなたはそれを空にすることは決してありません。それはあなたが望んでいるものではないと確信しており、おそらくパフォーマンスの問題でもあります。

2 つ目は、不必要に大量のメッセージを送信していることです。たとえば、マスクを O(N 2 ) 回抽出しています。これを最適化するには、すべてのマスクを 1 回抽出します。

NSArray *teams = [options objectForKey:@"teams"];
NSUInteger teamCount = teams.count;

int masks[teamCount];
for (NSUInteger i = 0; i < teamCount; ++i) {
    masks[i] = [[teams[i] objectForKey:@"mask"] intValue];
}

NSMutableArray *matches = [[NSMutableArray alloc] init];

for (NSUInteger i = 0; i < teamCount; ++i) {
    for (NSUInteger j = i + 1; j < teamCount; ++j) {
        if ((masks[i] & masks[j]) == 0) {
            [matches addObject:@[teams[i], teams[j]]];
        }
    }
}

あなたはまだ O(N 2 ) 回の反復を行っていますが、各反復で行う作業ははるかに少なくなります。

于 2012-10-12T03:31:39.990 に答える
1

注意すべきことの1つは、

[t insertObject:[teams objectAtIndex:i] atIndex:0];

t使用されるたびにすべての要素がシフトされます。ループで 2 回実行しているため、処理が大幅に遅くなる可能性があります。を使ったほうがいいかもしれません[t addObject: ...]。

また、 がNSMutableArray不必要にサイズ変更されている可能性があります。必要なサイズが大体わかっている場合は、特定の容量で初期化できます。

NSMutableArray *t = [[NSMutableArray alloc] initWithCapacity: size];
于 2012-10-12T03:34:40.577 に答える