Нахождение суммы суб вектор, удовлетворяющий неравенству


Я попросил, чтобы реализовать код, который проверяет, если есть суб вектор, который имеет сумму, v_l, который бы удовлетворял \$ \ГРП{1}{4}и MN + 1 \лек v_l \Лек в - \ГРП{1}{4} м N - 1\$.

def possible(vec, m):
    n = len(vec)     # Number of columns
    v = sum(vec)
    global R

    R = []

    num = {i: 0 for i in set(vec)}
    for i in vec:
        num[i] += 1

    solution = dfs_backtrack(num, m, n, v)    

return solution

def dfs_backtrack(vec, m, n, v):

    v_l = sum([i*vec[i] for i in vec.keys()])
    R.append(vec)

    if 0.25 * m * n + 1 <= v_l <= v - 0.25 * m * n - 1:
        return vec

    for i in vec.keys():
        temp = dict(vec)
        temp[i] -= 1
        if temp[i] is 0:
            temp.pop(i)
        if temp and temp not in R :
            temp = dfs_backtrack(temp, m, n, v)
        else:
            temp = None
        if temp:
            return temp
    return None

Из моего анализа будет иметь место и сложность \$О(Н^{М+1} м^{-м-1})\$, где \1 $\leq и М \Лек п\$. Что я могу сделать, чтобы улучшить пространство и время сложность?



Комментарии
2 ответа

Так как сумма v_l изменения с каждой итерацией словарь значений numЯ не знаю способа, чтобы предварительно вычислить правой стороне суммы, прежде чем руки. Это было бы немного легче, если вы могли бы использовать внешние модули. Что сказал, Вы можете увидеть небольшой скорости, если вы используете больше осмысленности. Например, вы можете получить num через num = {x : vec.count(x) for x in vec}. Кроме того, используйте == 0 (не is 0) для проверки нулевой равенства и использовать is None(не == None) для проверки None.

Также, вы перебора всех возможных комбинаций. В случае использования votes1 и m1вы знаете, что m = m1 = 10 и n = len(votes1) = 30. Так вы знаете, что ваша нижняя граница отсечения на 76. Это 76 перестановок, что вам не нужно использовать. Вы можете включить break заявление по нижней границе с увеличении вниз (temp[i] -= 1), но я бы вместо того, чтобы использовать эту нижнюю границу в качестве отправной точки и повторяют, увеличивая вверх, как можно найти какой-то другой способ ограничить суммы в верхний предел.

И наконец, использование Globals и не описательные имена переменных делает его трудно редактировать код. Например, votes вместо vec, ndict вместо nи т. д. Кроме того, вы можете пройти R в dfs_backtrack.

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

def get_lower_bound(m, n):
return m*n/4 + 1

def get_upper_bound(m, n, v):
return v - m*n/4 - 1

def initialize_constants(m, n, votes):
""" Pre-compute these values as they do not change."""
size = len(votes)
total = sum(votes)
lower_bound = get_lower_bound(m, n=30)
return size, total, lower_bound

def initialize_vl(votes, m):
## I think set look-ups are quickest, these provide unique values just like dictionaries do
unique_votes = list(set(votes)) #keys for num
vcounts = [votes.count(x) for x in unique_votes] #vals for num
vl = sum([a*b for a,b in zip(unique_votes, vcounts)])
return unique_votes, vcounts, vl

Таким образом, вам не нужно использовать

    temp = dict(vec)
temp[i] -= 1
if temp[i] is 0:
temp.pop(i)
if temp and temp not in R :

как вы создаете temp как копия vec; любое изменение temp изменения vec как хорошо. Кроме того, вы можете перебрать свои уникальные значения в list(set(...)) вместо того, чтобы проверить, если каждый элемент в R.

К сожалению я не смогла помочь. Дайте мне знать, если что-то непонятно.

1
ответ дан 2 апреля 2018 в 09:04 Источник Поделиться

Взяв немного силы в этом, я бы предложил следующие изменения:


  • Использовать collections.Counter для выполнения подсчета. Незначительные настройки, но это в стандартной библиотеке, и это быстро.

  • Использовать общий аргумент, а не глобальную переменную, чтобы отслеживать, какие рекурсий ты уже вычислен.

  • Предварительно вычисляем нижнюю и верхнюю границы. Они никогда не меняются, и это очищает функция recursed немного.

  • Поскольку вы знаете, какой элемент удаляется, когда вы рекурсию, вычесть его из суммы, а не ре-сумма вектора в каждой рекурсии.

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

  • Преобразование из стандартного return-на основе функции с генератором позволяет использовать yield from чтобы более аккуратно обработать случай, где "я не нашел ответа, но один из моих детей мог бы". В данном случае, я на самом деле цикл на рекурсию, а не yield from это, но это имеет тот же эффект. Это также означает, что, бесплатно, те же функции может дать мне либо все допустимый ответы или только первый правильный ответ он сталкивается.

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

Окончательный код, я в конечном итоге с после этих предложений заключалась в следующем:

from collections import Counter
import warnings

def possible(vec, m):
n = len(vec) # Number of columns
v = sum(vec)
lower_bound = 0.25 * m * n + 1
upper_bound = v - 0.25 * m * n - 1

# Check for simple failure cases
if sum(num for num in vec if num > 0) < lower_bound or sum(num for num in vec if num < 0) > upper_bound:
return None

# Use the high-performance, built-in counter class
counts = Counter(vec)

# Use a generator syntax rather than direct return
# Some benefits:
# 1. You avoid having to check if a value gets returned (temp variables), just "yield from" when recursing and "yield" when successful
# 2. You automatically end up with a function that could produce _all_ valid answers, if desired, for free
# 3. You end up with predictable errors if no answer is found
# Use a shared mutable variable for R within a call stack, not a global
# R is now a set to allow for O(1) "contains" checks
valid_subvectors = dfs_backtrack(set(), counts, v, lower_bound, upper_bound)

try:
return next(valid_subvectors)
except StopIteration:
return None
except RecursionError:
warnings.warn("Unable to find subvector, it's too long/diverse for recursive solver")
return None

def dfs_backtrack(R, vec, cur_sum, lower_bound, upper_bound):
# Only need to check keys since, for each call we handle all possible numbers of a single key
checked_this_already = tuple(sorted(vec.keys()))
if checked_this_already not in R:
# Since R is now a shared instance of a list, it acts "global" but only exists within the current call stack
R.add(checked_this_already)

# Summation is now performed by subtracting recursively from total, rather than re-summing each time

if lower_bound <= cur_sum <= upper_bound:
# Convert counter back into vector form
yield list(vec.elements())

# Add a simple heuristic to try to find the right answer faster
def heuristic(k):
return abs((lower_bound + upper_bound) // 2 - (cur_sum - k))

# Pre-limit the keys we'll consider so we don't even run the heuristic on irrelevant keys (since 0's are no longer popped)
potential_keys = [i for i in vec.keys() if i > 0]
for i in sorted(potential_keys, key=heuristic):
# Handle all possible numbers of that key at once to reduce recursion
num_keys = vec.pop(i)
for n in range(1, num_keys + 1):
for solution in dfs_backtrack(R, vec, cur_sum - i * n, lower_bound, upper_bound):
yield [i] * (num_keys - n) + solution

vec[i] = num_keys

С этими изменениями, в течение нескольких векторов выборки, я получаю около 3-5х ускорение. Кроме того, изменения в рекурсии скороговоркой делает его способным выполнять намного больше векторов так долго, как существует ограниченное количество уникальных значений в них (а не оригинальный подход, который попадает в ограничение рекурсии на основании исходных длина вектора). Это может быть сделано лучше вообще избегать рекурсии, но это казалось слишком резкие изменения кода для этого параметра.

1
ответ дан 2 мая 2018 в 04:05 Источник Поделиться