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对象。你永远不会清空它。我很确定这不是你想要的,它也可能是一个性能问题。

其次,您发送了大量不必要的消息。例如,您要提取掩码 O(N 2 ) 次。您可以通过一次提取所有掩码来优化它。

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

需要注意的一件事是

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

导致t每次使用时都会移动所有元素。这可能会显着减慢速度,因为您在循环中执行了两次。使用它可能会更好[t addObject: ...]

此外,NSMutableArray可能会不必要地调整大小。如果您大致知道它需要多大,则可以使用特定容量对其进行初始化:

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