Найдите числа, которые можно сделать с сложением и вычитанием, используя все числа

Question

Я профилировал свое приложение, и оно тратит 90% своего времени на plus_minus_variations.

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

Например:
Ввод

1, 2

Ввод

1+2=3
1-2=-1
-1+2=1
-1-2=-3

Это мой текущий код.Я думаю, что это можно было бы значительно улучшить с точки зрения скорости.

def plus_minus_variations(nums):
    result = dict()
    for i, ops in zip(xrange(2 ** len(nums)), \
            itertools.product([-1, 1], repeat=len(nums))):
        total = sum(map(operator.mul, ops, nums))
        result[total] = ops
    return result

Я в основном ищу другой алгоритм, чтобы подойти к этому.Мой текущий кажется довольно неэффективным.Однако, если у вас есть предложения по оптимизации самого кода, я тоже буду рад их услышать.

Дополнительно:

• Ничего страшного, если в результате пропущены некоторые ответы(или имеет несколько посторонних ответов), если он заканчивается намного быстрее.
• Если есть несколько способов получить число, любой из них подойдет.
• ДляРазмеры списков, которые я использую, 99,9% способов выдают повторяющиеся числа.
• Это нормально, если результат не соответствует способу, которым были созданы числа, если, опять же, он заканчивается намного быстрее.

Answer 1

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

def combine(l,r):
    res = set()
    for x in l:
        for y in r:
            res.add( x+y )
            res.add( x-y )
            res.add( -x+y )
            res.add( -x-y )
    return list(res)

def pmv(nums):
    if len(nums) > 1:
        l = pmv( nums[:len(nums)/2] )
        r = pmv( nums[len(nums)/2:] )
        return combine( l, r )
    return nums

РЕДАКТИРОВАТЬ : если важен способ генерации номера, вы можете использовать этот вариант:

def combine(l,r):
    res = dict()
    for x,q in l.iteritems():
        for y,w in r.iteritems():
            if not res.has_key(x+y):
                res[x+y] = w+q
                res[-x-y] = [-i for i in res[x+y]]
            if not res.has_key(x-y):
                res[x-y] = w+[-i for i in q]
                res[-x+y] = [-i for i in res[x-y]]
    return res

def pmv(nums):
    if len(nums) > 1:
        l = pmv( nums[:len(nums)/2] )
        r = pmv( nums[len(nums)/2:] )
        return combine( l, r )
    return {nums[0]:[1]}

Мои тесты показывают, что это все еще быстрее, чем другие решения.

Answer 2

РЕДАКТИРОВАНИЕ:

Ага!
Код написан на Python 3, вдохновлен tyz:

from functools import reduce # only in Python 3

def process(old, num):
    new = set(map(num.__add__, old)) # use itertools.imap for Python 2
    new.update(map((-num).__add__, old))
    return new

def pmv(nums):
    n = iter(nums)
    x = next(n)
    result = {x, -x} # set([x, -x]) for Python 2
    return reduce(process, n, result)

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

На вычисление 256 чисел уходит менее 1 секунды.

---

Почему продукт тогда mult?

def pmv(nums):
    return {sum(i):i for i in itertools.product(*((num, -num) for num in nums))}

Может бытьбыстрее без того, как были получены цифры:

def pmv(nums):
    return set(map(sum, itertools.product(*((num, -num) for num in nums))))

Answer 3

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

Я делю список на части и создаю варианты для него.Так как вы получаете намного меньше чем 2 ** len(chunk) вариантов, это будет быстрее.Длина чанка равна 6, вы можете поиграть с ним, чтобы увидеть, какая оптимальная длина чанка.

def pmv(nums):
    chunklen=6
    res = dict()
    res[0] = ()
    for i in xrange(0, len(nums), chunklen):
        part = plus_minus_variations(nums[i:i+chunklen])
        resnew = dict()
        for (i,j) in itertools.product(res, part):
            resnew[i + j] = tuple(list(res[i]) + list(part[j]))
        res = resnew
    return res

Answer 4

Вы можете получить что-то вроде ускорения на 50% (по крайней мере, для коротких списков), просто выполнив:

from itertools import product, imap
from operator import mul

def plus_minus_variations(nums):
    result = {}
    for ops in product((-1, 1), repeat=len(nums)):
        result[sum(imap(mul, ops, nums))] = ops
    return result

imap не будет создавать промежуточные списки, которые вам не нужны. Импорт в локальное пространство имен экономит время поиска атрибутов. Кортежи быстрее, чем списки. Не храните ненужные промежуточные предметы.

Я попробовал это с пониманием, но это было немного медленнее. Я попробовал это с заданным пониманием (не сохраняя ops), и это была та же скорость.

Я не знаю, почему вы вообще использовали zip и xrange ... вы не использовали результат в своих вычислениях.

Редактировать: Я получаю значительное ускорение с этой версией вплоть до момента, когда ваша версия выдает ошибку памяти, а не только для коротких списков.

Answer 5

Этот простой итерационный метод вычисляет все возможные суммы. @ Tyz может быть примерно в 5 раз быстрее, чем рекурсивный метод.

def pmv(nums):
    sums = set()
    sums.add(0)
    for i in range(0, len(nums)):
        partialsums = set()
        for s in sums:
            partialsums.add(s + nums[i])
            partialsums.add(s - nums[i])
        sums = partialsums
    return sums

Answer 6

С математической точки зрения вы, наконец, достигли всех кратностей наибольшего общего делителя ваших начальных значений.

Например:

• стартовые значения 2,4. тогда gcd (2,4) равно 2, поэтому сгенерированные числа равны .. -4, -2, 0, 2, 4, ...
• начальные значения 3,5. тогда gcd (3,5) равно 1, вы получите все целые числа.
• startvalues ​​12, 18, 15. gcd (12,15,18) равен 3, вы получаете .. -6, -3, 0, 3, 6, ....