Прирост скорости от 50% - 100% от базового решения.
Мне только так и не нравится, что по факту три прохода по массиву.
1) Копирование части массива
2) Присваивание значимых элементов
3) Максимизация
Как не бился, первые два прохода не объединяются в один. Точнее можно сделать через цикл, но он в двадцать раз медленнее получается, видимо векторизация отменяется.
Как понимаю на C можно в один проход сделать, но мне кажется всё равно медленнее будет чем текущая версия с векторизацией.
import random as rnd
import numpy as np
import time
def find_subset_sum(numbers: list, target: int):
dp = np.zeros(target + 1, dtype='uint8' if len(numbers) < 256 else 'uint16')
dp[0] = 1
offset = 1
for i, val in enumerate(numbers):
offset += val
if offset > target + 1:
offset = target + 1
temp = dp[:offset-val].copy()
temp[temp > 0] = len(numbers) - i
np.maximum(dp[val:offset], temp, dp[val:offset])
if dp[target]:
break
if not dp[target]:
return []
subset = []
j = target
while j > 0:
i = numbers[len(numbers) - dp[j]]
subset.append(i)
j -= i
return subset[::-1]
n = 50
rnd.seed(1)
source = [rnd.randint(1000000, 9999999) for i in range(n)]
target_sum = sum(source) // 2
print('source:', source)
print('target_sum:', target_sum)
print()
start = time.time()
result = find_subset_sum(source, target_sum)
end = time.time()
elapsed_time = end - start
print(f"Execution time: {elapsed_time:.6f} seconds")
print('result:', sum(result), result)
С последним вариантом неувязка вышла. Зато новая попытка в среднем 10% выигрыш по времени.
Основная идея в том, что не нужно трогать ту часть массива, которая остаётся неизменной на каждом этапе.
for i, val in enumerate(numbers):
temp = np.roll(dp, val).view()[val:]
temp[temp > 0] = len(numbers) - i
dp_slice = dp[val:]
np.maximum(dp_slice, temp, dp_slice)
if dp[target]:
break
for i, val in enumerate(numbers):
k = np.uint8(len(numbers) - i) if len(numbers) < 256 else np.uint16(len(numbers) - i)
temp = np.roll(dp, val)
temp[:val] = 0
np.maximum(dp, temp.astype(bool) * k, dp)
if dp[target]:
break
У меня ускорилось в два раза, так как мы убираем лишний проход по массиву.
Всякие максимумы, которые не факт что векторизованы.
np.maximum 100% векторизированна, там внутри должна быть интерпретация к PMAXUB/PMAXUW. А в зависимости от процессора там прирост может быть значительный.
И если вы будете его сравнивать с линейным решателем, то надо делить время на 10. Ведь решатель-то написан на каком-нибудь с++, а из питона вы лишь вызываете библиотеку
Ну это такой аргумент, numpy если я не ошибаюсь написан на том же си и так же использует SIMD векторизацию. Так что разница будет не столь значительна.
У вас в решении примерно это и хранится, только перевернутое - вы храните, сколько там единиц в столбце.
Не совсем так, я храню индекс числа в оригинальном массиве, в перевёрнутом виде. И оставляю больший индекс проходя функцией max (оставляем более старый) чтоб не затереть уже найденный маршрут. Мне такой подход напоминает алгоритм Дейкстры для поиска пути в графе.
Хотелось бы сравнить алгоритм с вашей реализацией по скорости.
Я долго сопротивлялся, но похоже вам удалось убедить меня в неправоте, за что вам большой респект. Один хороший контрпример решил дело.
Мне не остаётся ничего кроме, как проиндексировать биты dp, тогда восстановление идет всегда правильно. Памяти требует, как в оригинальном решении, при длине входного массива до 256 элементов, и в двое больше в ином случае.
import numpy as np
def find_subset_sum(numbers: list, target: int):
dp = np.zeros(target + 1, dtype='uint8' if len(numbers) < 256 else 'uint16')
dp[0] = len(numbers)
for i, val in enumerate(numbers):
temp = np.roll(dp, val)
temp[:val] = 0
temp[temp > 0] = len(numbers) - i
dp = np.maximum(dp, temp)
if dp[target]:
break
if not dp[target]:
return []
subset = []
j = target
while j > 0:
i = numbers[len(numbers) - dp[j]]
subset.append(i)
j -= i
return subset[::-1]
source = [2, 3, 3, 4, 52, 52, 100, 1000, 1000]
target_sum = 1108
print('source:', source)
print('target_sum:', target_sum)
print()
result = find_subset_sum(source, target_sum)
print('result:', sum(result), result)
Ну вот новый контрпример: ([2, 3, 3, 4, 52, 52, 100, 1000, 1000], 108) ...
Ну вот я добавил пару 1000 в массив и ваша эвристика сломалась.
Где же сломалась? Работает, проверьте исходные данные.
Еще раз, проблема в том, что можно получить ситуацию, что вам надо набрать 8, а у вас остались числа [2, 3, 3, 4]
Я понимаю резон в ваших словах, но и вы поймите, что смысл всех танцев как раз в том, чтобы исключить возможность выбора тех величин, что приведут к тупику в дальнейшем.
И да вы правы нужно доказать логически, а это не простая задача.
Благодарю Вас в вашем упорстве находить истину и желании помочь другим в этом же.
Действительно в моих первоначальных рассуждениях закралась ошибка: Если мы усекаем список просматриваемых чисел на первом этапе, то его и на втором этапе нужно усекать в том же объёме.
Однако, это не отменяет работоспособность самой идеи получения списка результата. Сортировка по возрастанию как раз и используется для того чтобы числа, которые могут состоять из нескольких меньших чисел утилизировались в первую очередь.
Я не убеждён, что и новый алгоритм не может содержать ошибки, но вы так категорично утверждаете, что решение в корне не верно, что вызывает желание понять почему.
На мой взгляд так как сложение - операция коммуникативная и ассоциативная, мы выстраиваем поле в рамках которого ищем результат, и не важно в каком порядке мы будем обходить это поле решений.
И ещё в процессе нашей дискуссии я исправил огрех, который не заметил сразу, после рола правые биты оказываются слева строки, а это иногда вносит ошибку. Потому выкладываю очередную версию, в которой все ваши контрпримеры вычисляются верно.
import bitstring as bit
def find_subset_sum(numbers: list, target: int):
numbers.sort()
dp = bit.BitArray(target + 1)
dp[0] = 1
count = -1
for i in numbers:
temp = dp.copy()
dp.ror(i)
dp.set(0, range(i))
dp |= temp
print('i:', i, dp.bin)
count += 1
if dp[target] == 1:
break
if not dp[target]:
return []
print()
subset = []
j = target
for i in numbers[count::-1]:
if j >= i and dp[j - i]:
print('i:', i, 'j:', j, '- берём')
subset.append(i)
j -= i
else:
print('i:', i, 'j:', j, '- не берём')
return subset[::-1]
source = [2, 3, 3, 4, 52, 52, 100]
target_sum = 108
print('source:', source)
print('target_sum:', target_sum)
print()
result = find_subset_sum(source, target_sum)
print('result:', sum(result), result)
Вам надо набрать 8, есть числа {2,3,3,4}. Первым шагом вы возьмете 4, ведь можно же набрать 4 всеми этими числами. И дальше все. Оставшиеся 4 вы никак из {2,3,3} не наберете.
Немного доработал представленный алгоритм динамического программирования для Python.
Теперь он требует в восемь рез меньше памяти и в два раза быстрее, чем через numpy. Но это ожидаемо, так как используется более плотное хранение бит благодаря модулю bitstring.
Ещё мне показалось уместным не дожидаться обхода всего входного массива, если допустимое решение уже найдено, что даёт приличный прирост производительности.
Возможно, кому то пригодится.
import bitstring as bit
import random as rnd
import time
def find_subset_sum(numbers: list, target: int):
dp = bit.BitArray(target + 1)
dp[0] = 1
for i in numbers:
temp = dp.copy()
dp.ror(i)
dp |= temp
if dp[target] == 1:
break
if not dp[target]:
return []
subset = []
j = target
for i in numbers[::-1]:
if j >= i and dp[j - i]:
subset.append(i)
j -= i
return subset[::-1]
n = 100
# rnd.seed(0)
source = [rnd.randint(1000000, 9999999) for i in range(n)]
print('source:', source)
target_sum = sum(source) // 2
print('target_sum:', target_sum)
print()
start = time.time()
result = find_subset_sum(source, target_sum)
end = time.time()
elapsed_time = end - start
print(f"Execution time: {elapsed_time:.6f} seconds")
print(f"Subset with sum {target_sum}: {result}")
Алгоритм ДП, что я рассматривал, очень неэффективен по сравнению с тем, что предоставили Вы.
Беру свои слова назад, в такой реализации ДП на многих наборах обходит мою версию ЛП.
Любопытно, на некоторых наборах сильно лидирует ЛП, но если проигрывает, то часто значительно, тогда как ДП более стабилен. Как вариант интересно устраивать гонку алгоритмов, какой финиширует первым.
Однако меня огорчил тот факт, что на больших наборах входных данных, памяти ДП всё же не хватает, и он не выполняется с ошибкой:
MemoryError: Unable to allocate 14.2 GiB for an array with shape (15207959671,) and data type bool.
И ещё проблема, что решение должно быть точным, а любая микро-погрешность не найдёт решение Xi in {0,1}, посчитается какой-нибудь Xi=0.99999 и всё, вариант отсечётся. То есть, я думаю, тщательное тестирование на очень сложных случаях покажет, что этот метод не всегда даёт правильный результат.
Это зависит от качества решателя. Если под капотом используются float64, так и бывает у большинства решателей.
Однако, как я считаю хороший решатель должен работать с натуральными дробями, и тогда погрешность не возникает совсем.
ДП больше пары десятков элементов у меня не тянет. Тот алгоритм что я использовал сжирает всю память для кэша.
Возможно алгоритм что не хранит всё кэше и вывезет. Но если предположить, что по скорости алгоритм с меморизацией и без равны, то навряд ли сравняется с ЛП.
Выигрыш есть, именно для этого пост и писался. Только что бы это показать нужно смотреть на практике. Выигрыш очень велик, когда количество чисел превалирует над размером.
Динамическое программирование требует очень много память на больших N и P. Линейное в этом смысле сильно выигрывает, но у него плохо со стабильностью результатов, уже больно оно зависит от набора входных данных. На некоторых наборах выигрыш феноменален, не некоторых экспонента всё портит. Но по моим наблюдениям в среднем разы рвёт ДП.
На случайных наборах результат очень хороший, особенно когда допустимых решений много.
Если вы приложите набор тестовых данных, то могу протестировать.
То, что задача NP - полна коллега вроде и не оспаривал. Видимо он хотел указать, что сложность задачи зависит не только от числа элементов (N), но и от точности (P) и это не имеет отношение к NP-полноте. Я не верно понял?
А ларчик просто открывался!
Прирост скорости от 50% - 100% от базового решения.
Мне только так и не нравится, что по факту три прохода по массиву.
1) Копирование части массива
2) Присваивание значимых элементов
3) Максимизация
Как не бился, первые два прохода не объединяются в один. Точнее можно сделать через цикл, но он в двадцать раз медленнее получается, видимо векторизация отменяется.
Как понимаю на C можно в один проход сделать, но мне кажется всё равно медленнее будет чем текущая версия с векторизацией.
С последним вариантом неувязка вышла. Зато новая попытка в среднем 10% выигрыш по времени.
Основная идея в том, что не нужно трогать ту часть массива, которая остаётся неизменной на каждом этапе.
Попробуйте изменить на это:
У меня ускорилось в два раза, так как мы убираем лишний проход по массиву.
np.maximum 100% векторизированна, там внутри должна быть интерпретация к PMAXUB/PMAXUW. А в зависимости от процессора там прирост может быть значительный.
Ну это такой аргумент, numpy если я не ошибаюсь написан на том же си и так же использует SIMD векторизацию. Так что разница будет не столь значительна.
Не совсем так, я храню индекс числа в оригинальном массиве, в перевёрнутом виде. И оставляю больший индекс проходя функцией max (оставляем более старый) чтоб не затереть уже найденный маршрут. Мне такой подход напоминает алгоритм Дейкстры для поиска пути в графе.
Хотелось бы сравнить алгоритм с вашей реализацией по скорости.
Я долго сопротивлялся, но похоже вам удалось убедить меня в неправоте, за что вам большой респект. Один хороший контрпример решил дело.
Мне не остаётся ничего кроме, как проиндексировать биты dp, тогда восстановление идет всегда правильно. Памяти требует, как в оригинальном решении, при длине входного массива до 256 элементов, и в двое больше в ином случае.
Где же сломалась? Работает, проверьте исходные данные.
Я понимаю резон в ваших словах, но и вы поймите, что смысл всех танцев как раз в том, чтобы исключить возможность выбора тех величин, что приведут к тупику в дальнейшем.
И да вы правы нужно доказать логически, а это не простая задача.
Благодарю Вас в вашем упорстве находить истину и желании помочь другим в этом же.
Действительно в моих первоначальных рассуждениях закралась ошибка: Если мы усекаем список просматриваемых чисел на первом этапе, то его и на втором этапе нужно усекать в том же объёме.
Однако, это не отменяет работоспособность самой идеи получения списка результата. Сортировка по возрастанию как раз и используется для того чтобы числа, которые могут состоять из нескольких меньших чисел утилизировались в первую очередь.
Я не убеждён, что и новый алгоритм не может содержать ошибки, но вы так категорично утверждаете, что решение в корне не верно, что вызывает желание понять почему.
На мой взгляд так как сложение - операция коммуникативная и ассоциативная, мы выстраиваем поле в рамках которого ищем результат, и не важно в каком порядке мы будем обходить это поле решений.
И ещё в процессе нашей дискуссии я исправил огрех, который не заметил сразу, после рола правые биты оказываются слева строки, а это иногда вносит ошибку. Потому выкладываю очередную версию, в которой все ваши контрпримеры вычисляются верно.
Обратите внимание на условие:
Оно заранее завершает процесс заполнения dp, и исключает во многом те ситуации, что вы описывали в предыдущем ответе.
Это не так! Проиллюстрирую:
Так понимаю достаточно сделать:
numbers.sort()первым шагом функции.Поскольку обход цикла идёт с конца списка, проблема полностью устраняется.
Могли бы вы подробнее пояснить, что за идея у вас тут оформлена. Очень хотелось бы разобраться, но боюсь мой скил в плюсах не настолько хорош.
Немного доработал представленный алгоритм динамического программирования для Python.
Теперь он требует в восемь рез меньше памяти и в два раза быстрее, чем через numpy. Но это ожидаемо, так как используется более плотное хранение бит благодаря модулю bitstring.
Ещё мне показалось уместным не дожидаться обхода всего входного массива, если допустимое решение уже найдено, что даёт приличный прирост производительности.
Возможно, кому то пригодится.
Не утверждаю, что решение с ЦЛП - серебряная пуля.
Возможно, решение находится не всегда быстро, но по памяти более гуманно факт.
Алгоритм ДП, что я рассматривал, очень неэффективен по сравнению с тем, что предоставили Вы.
Беру свои слова назад, в такой реализации ДП на многих наборах обходит мою версию ЛП.
Любопытно, на некоторых наборах сильно лидирует ЛП, но если проигрывает, то часто значительно, тогда как ДП более стабилен. Как вариант интересно устраивать гонку алгоритмов, какой финиширует первым.
Однако меня огорчил тот факт, что на больших наборах входных данных, памяти ДП всё же не хватает, и он не выполняется с ошибкой:
MemoryError: Unable to allocate 14.2 GiB for an array with shape (15207959671,) and data type bool.
Это зависит от качества решателя. Если под капотом используются float64, так и бывает у большинства решателей.
Однако, как я считаю хороший решатель должен работать с натуральными дробями, и тогда погрешность не возникает совсем.
ДП больше пары десятков элементов у меня не тянет. Тот алгоритм что я использовал сжирает всю память для кэша.
Возможно алгоритм что не хранит всё кэше и вывезет. Но если предположить, что по скорости алгоритм с меморизацией и без равны, то навряд ли сравняется с ЛП.
Выигрыш есть, именно для этого пост и писался. Только что бы это показать нужно смотреть на практике. Выигрыш очень велик, когда количество чисел превалирует над размером.
Динамическое программирование требует очень много память на больших N и P. Линейное в этом смысле сильно выигрывает, но у него плохо со стабильностью результатов, уже больно оно зависит от набора входных данных. На некоторых наборах выигрыш феноменален, не некоторых экспонента всё портит. Но по моим наблюдениям в среднем разы рвёт ДП.
На случайных наборах результат очень хороший, особенно когда допустимых решений много.
Если вы приложите набор тестовых данных, то могу протестировать.
То, что задача NP - полна коллега вроде и не оспаривал. Видимо он хотел указать, что сложность задачи зависит не только от числа элементов (N), но и от точности (P) и это не имеет отношение к NP-полноте. Я не верно понял?
Вы правы. Мне не хотелось излишне усложнять текст.
Так как для чисел порядка миллиарда, число двоичных разрядов практически не имеет значения, то я несколько упростил повествование.