如何在Objective-C中加速这种强力加法算法？

I'm trying to learn a little more about algorithms and have built a simple one to see, using brute force, whether a target number can be made from a grid of randomly created numbers. I've done enough to check whether five of the grid numbers added together will create the target, which should be enough for the purpose I had in mind, but the process is VERY slow, around 11 seconds on the iOS simulator. How can I speed things up here? Is there a more efficient way to do this than using all the loops I'm using? Here's all my code, GridNumber is a simple NSObject subclass that contains two integers, number and tag.

我正在尝试学习更多关于算法的知识,并建立了一个简单的算法,使用蛮力,是否可以从随机创建的数字网格中制作目标数字。我已经做了足够的工作来检查添加在一起的五个网格数是否会创建目标,这应该足够我想到的目的,但是这个过程非常慢,在iOS模拟器上大约11秒。我怎样才能加快速度呢?有没有比使用我正在使用的所有循环更有效的方法呢?这是我的所有代码,GridNumber是一个简单的NSObject子类,包含两个整数,数字和标签。

- (void)viewDidLoad
 {
      [super viewDidLoad];

      // 0. Set up target number.
      int random = arc4random() % 100 + 3;
      NSNumber *target = [NSNumber numberWithInt: random];

      // 1. Set up array of available numbers.
      NSMutableArray *grid = [[NSMutableArray alloc] init];
      for (int i = 1; i < 48; i++) {
           GridNumber *number = [[GridNumber alloc] initWithRandomIntegerAndTag: i];
           [grid addObject: number];
      }

      if ([self canTarget: target BeMadeFromGrid: grid]) NSLog(@"--- SOLVEABLE!");
      else NSLog(@"--- UNSOLVEABLE!");
 }

 - (BOOL) canTarget: (NSNumber *) target BeMadeFromGrid: (NSArray *) grid
 {
      NSLog(@"TARGET NUMBER IS: %d", target.intValue);

      // 2. See if the target already exists first.
      for (GridNumber *firstValue in grid) {
           if (firstValue.number == target.intValue) {
                NSLog(@"SOLVEABLE IN 1: Grid already contains target!");
                return YES;
           }
      }

      // 3. Add elements once, see if any of those give the result.
      for (GridNumber *firstValue in grid) {
           for (GridNumber *secondValue in grid) {
                int result = firstValue.number + secondValue.number;
                if (result == target.intValue && firstValue.tag != secondValue.tag) {
                     NSLog(@"SOLVEABLE IN 2: Adding %d and %d creates target!", firstValue.number, secondValue.number);
                     return YES;
                }
           }
      }

      // 4. Add elements twice, see if any of those give the result.
      for (GridNumber *firstValue in grid) {
           for (GridNumber *secondValue in grid) {
                for (GridNumber *thirdValue in grid) {
                     int result = firstValue.number + secondValue.number + thirdValue.number;
                     if (result == target.intValue && firstValue.tag != secondValue.tag && firstValue.tag != thirdValue.tag && secondValue.tag != thirdValue.tag) {
                          NSLog(@"SOLVEABLE IN 3: Adding %d, %d and %d creates target!", firstValue.number, secondValue.number, thirdValue.number);
                          return YES;
                     }
                }
           }
      }

      // 5. And three times..
      for (GridNumber *firstValue in grid) {
           for (GridNumber *secondValue in grid) {
                for (GridNumber *thirdValue in grid) {
                     for (GridNumber *fourthValue in grid) {
                          int result = firstValue.number + secondValue.number + thirdValue.number + fourthValue.number;
                          if (result == target.intValue && firstValue.tag != secondValue.tag && firstValue.tag != thirdValue.tag && firstValue.tag != fourthValue.tag &&
                              secondValue.tag != thirdValue.tag && secondValue.tag != fourthValue.tag && thirdValue.tag != fourthValue.tag) {
                               NSLog(@"SOLVEABLE IN 4: Adding %d, %d, %d and %d creates target!", firstValue.number, secondValue.number, thirdValue.number, fourthValue.number);
                               return YES;
                          }
                     }
                }
           }
      }

      // 6. And four times..
      for (GridNumber *firstValue in grid) {
           for (GridNumber *secondValue in grid) {
                for (GridNumber *thirdValue in grid) {
                     for (GridNumber *fourthValue in grid) {
                          for (GridNumber *fifthValue in grid) {
                               int result = firstValue.number + secondValue.number + thirdValue.number + fourthValue.number + fifthValue.number;
                               if (result == target.intValue && firstValue.tag != secondValue.tag && firstValue.tag != thirdValue.tag && firstValue.tag != fourthValue.tag &&
                                   firstValue.tag != fifthValue.tag && secondValue.tag != thirdValue.tag && secondValue.tag != fourthValue.tag && secondValue.tag != fifthValue.tag &&
                                   thirdValue.tag != fourthValue.tag && thirdValue.tag != fifthValue.tag && fourthValue.tag != fifthValue.tag) {
                                    NSLog(@"SOLVEABLE IN 5: Adding %d, %d, %d, %d and %d creates target!", firstValue.number, secondValue.number, thirdValue.number, fourthValue.number, fifthValue.number);
                                    return YES;
                               }
                          }
                     }
                }
           }
      }

      // 7. This is if it can't be made.
      return NO;
 }

3 个解决方案

#1

Based on the idea of @torquestomp, here is some C code I was able to put together quickly. For a grid of 48 numbers (in the range of 1 to 21) looking for a target less than 203 it hardly ever takes more than a few hundreths of a second to run. The runtime will increase as you allow for longer solutions (more than 5 or 6 numbers). Note that I have not fully tested this function. The times reported are on a Mac. On the iPhone they will be slower.

根据@torquestomp的想法,这里有一些C代码我可以快速组合在一起。对于一个48个数字(在1到21范围内)的网格,寻找一个小于203的目标,它几乎不需要超过几秒钟的运行时间。当您允许更长的解决方案(超过5或6个数字)时,运行时间将增加。请注意,我还没有完全测试此功能。报告的时间是在Mac上。在iPhone上,它们会变慢。

Edit: if you sort the list of numbers in descending order you should find the "optimal" (fewer numbers in sum) solutions first.

编辑:如果按降序对数字列表进行排序,则应首先找到“最佳”(总和较少的数字)解决方案。

typedef void(^execution_block_t)(void);

double time_execution(execution_block_t aBlock);
double time_execution(execution_block_t aBlock)
{
    uint64_t time0 = mach_absolute_time();
    aBlock();
    uint64_t time1 = mach_absolute_time();
    return (double)(time1 - time0)/NSEC_PER_SEC;
}

static int totalTests = 0;

int findPartialSum(int target, int *grid, int gridCount, int startIndex, int *solution, int depth, int maxDepth)
{
    for (int i=startIndex;  i<gridCount;  i++) {

        int newTarget = target - grid[i];
        totalTests++;

        if (newTarget == 0) {
            solution[depth-1] = i;
            return 1;
        }

        if (newTarget > 0 && depth < maxDepth) {
            int found = findPartialSum(newTarget, grid, gridCount, i+1, solution, depth+1, maxDepth);
            if (found > 0) {
                solution[depth-1] = i;
                return found + 1;
            }
        }
    }
    return 0;
}


int main (int argc, const char * argv[])
{
    @autoreleasepool {

        static const int gridSize = 48;
        static const int solutionSize = 5;

        int *solution = calloc(sizeof(int), solutionSize);
        int *grid     = calloc(sizeof(int), gridSize);
        int  target   = arc4random_uniform(200) + 3;

        for (int i=0;  i<gridSize;  i++)
            grid[i] = arc4random_uniform(20) + 1;

        NSMutableArray *numbers = [NSMutableArray array];
        for (int i=0;  i<gridSize;  i++)
            [numbers addObject:@(grid[i])];

        NSLog(@"\nTarget = %d\nGrid = %@", target, [numbers componentsJoinedByString:@","]);

        __block int count = 0;
        double elapsedTime = time_execution(^(void) {
            count = findPartialSum(target, grid, gridSize, 0, solution, 1, solutionSize);
        });

        NSLog(@"Looking for solution with up to %d numbers", solutionSize);
        if (count > 0) {

            [numbers removeAllObjects];
            for (int i=0;  i<count;  i++)
                [numbers addObject:@(grid[solution[i]])];

            NSLog(@"Found solution with %d numbers: %@", count, [numbers componentsJoinedByString:@","]);

        } else {
            NSLog(@"No solution found");
        }

        NSLog(@"After looking at %d possible sums",totalTests);
        NSLog(@"Elapsed time was %fs", elapsedTime);

        free(solution);
        free(grid);
    }
    return 0;
}

Some sample outputs:

一些样本输出:

Target = 159
Grid = 16,18,19,6,18,5,12,7,7,4,18,3,7,13,10,19,7,14,19,6,16,4,8,4,3,17,11,16,5,8,18,9,4,13,14,8,17,18,13,5,20,14,4,5,13,20,17,1
Looking for solution with up to 5 numbers
No solution found
After looking at 1925356 possible sums
Elapsed time was 0.014727s


Target = 64
Grid = 4,6,1,1,13,12,15,10,11,6,18,6,8,2,15,3,18,5,20,1,3,12,20,3,18,5,1,12,15,14,2,20,9,1,14,9,6,1,2,10,12,7,7,4,2,12,20,6
Looking for solution with up to 5 numbers
Found solution with 5 numbers: 4,6,18,18,18
After looking at 7271 possible sums
Elapsed time was 0.000048s

#2

This is known as the Subset-Sum Problem, and it is known to be NP-hard, so you are out of luck if you're looking for a really efficient solution. NP-hard means that there is no known polynomial-time (i.e., fast) solution with regards to the size of the input (the number of numbers in the grid). An understanding of big-Oh notation is rudimentary to taking advantage of this knowledge, so that seems like a good place to start.

这被称为子集求和问题,并且它被认为是NP难的,所以如果你正在寻找一个真正有效的解决方案,那你就不走运了。 NP-hard意味着关于输入的大小(网格中的数字的数量)没有已知的多项式时间(即,快速)解。对大喔符号的理解对于利用这些知识是不成熟的,因此这似乎是一个好的起点。

However, since you are using only positive integers, and the target number is always in the range [3,102], a pseudo-polynomial-time solution is available through the use of Dynamic Programming. As @Shark has mentioned, this is probably the thing you really want to focus on for now - if you don't understand the basics of recursive problem solving, tackling a known NP-hard problem right off the bat isn't the best idea ;)

但是,由于您只使用正整数,并且目标编号始终在[3,102]范围内,因此通过使用动态编程可以获得伪多项式时间解决方案。正如@Shark所提到的,这可能是你现在真正想要关注的事情 - 如果你不理解递归问题解决的基础知识,立即解决一个已知的NP难题并不是最好的想法;)

In pseudo-code, you want to do something like this:

在伪代码中,您想要执行以下操作:

Define array on [0,102] representing reachable numbers.  Set 0 to be reachable
for each NSNumber in grid:
    Looping upwards, for every reachable target in [3,102], set target + NSNumber to be reachable too
    If the sum exceeds 102, cut the loop
Return true if, after checking all numbers, target is reachable

This generalized algorithm runs in O(N*M) time for positive integers, where N is the number of numbers in the grid, and M is the maximum possible target. For N = 48 and M = 102, this should perform way better than the O(N^5) algorithm you are currently using

该广义算法在正整数的O(N * M)时间内运行,其中N是网格中的数字的数量,M是最大可能的目标。对于N = 48和M = 102,这应该比您当前使用的O(N ^ 5)算法更好

#3

You can also try generating a set containing all combinations of additions, and checking whether your target number is in that set (list). Generating such a set would take a long time, but that would give you the benefit of looking up more than one target against the same set in O(logn) - making it more efficient for running multiple queries against your grid.

您还可以尝试生成包含所有添加组合的集合,并检查您的目标编号是否在该集合(列表)中。生成这样的集合需要很长时间,但这样可以让您在O(logn)中针对相同的集合查找多个目标,从而更有效地针对您的网格运行多个查询。

Instead of re-adding the numbers and essentially re-generating the set every time you want to check a new target against the same grid of numbers.

每次想要针对相同的数字网格检查新目标时,不是重新添加数字而是基本上重新生成集合。

#1