Как я могу ускорить этот алгоритм добавления грубой силы в Objective-C?

Основываясь на идее @torquestomp, вот некоторый код C, который мне удалось быстро собрать. Для сетки из 48 чисел (в диапазоне от 1 до 21) при поиске цели меньше 203 выполнение почти никогда не занимает больше нескольких сотых секунды. Время выполнения будет увеличиваться, если вы допускаете более длинные решения (более 5 или 6 чисел). Обратите внимание, что я не полностью протестировал эту функцию. Сообщаемое время указано на Mac. На iPhone они будут медленнее.

Редактировать: если вы сортируете список чисел в порядке убывания, вы должны сначала найти «оптимальные» (меньшее количество чисел в сумме) решения.

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;
}

Некоторые примеры результатов:

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

Это известно как проблема с суммой подмножеств, и известно, что она является NP-сложной, поэтому вам не повезло, если вы ищете действительно эффективное решение. NP-сложный означает, что не существует известного полиномиального (то есть быстрого) решения относительно размера входных данных (количества чисел в сетке). Понимание нотации «большое О» является рудиментарным для того, чтобы воспользоваться этим знанием, так что кажется, что это хорошее место для начала.

Однако, поскольку вы используете только положительные целые числа, а целевое число всегда находится в диапазоне [3,102], с помощью динамического программирования доступно решение с псевдополиномиальным временем. Как уже упоминал @Shark, это, вероятно, то, на чем вы действительно хотите сосредоточиться сейчас - если вы не понимаете основ рекурсивного решения проблем, сразу же решать известную NP-сложную проблему - не лучшая идея. ;)

В псевдокоде вы хотите сделать что-то вроде этого:

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

Этот обобщенный алгоритм выполняется за время O(N*M) для положительных целых чисел, где N — количество чисел в сетке, а M — максимально возможная цель. Для N = 48 и M = 102 это должно работать лучше, чем алгоритм O (N ^ 5), который вы сейчас используете.

Вы также можете попробовать создать набор, содержащий все комбинации дополнений, и проверить, входит ли ваш целевой номер в этот набор (список). Создание такого набора заняло бы много времени, но это дало бы вам преимущество поиска более чем одной цели по одному и тому же набору в O(logn), что сделало его более эффективным для выполнения нескольких запросов к вашей сетке.

Вместо повторного добавления чисел и повторной генерации набора каждый раз, когда вы хотите проверить новую цель по одной и той же сетке чисел.