Ускорить выполнение кода Python

Question

Ускорить выполнение кода Python

Рейтинг: 2Ответов: 3Опубликовано: 02.08.2023

Задача на разделение набора чисел на 2 части, так чтобы разность сумм элементов этих частей была минимальна. Необходимо вывести разность. Количество чисел в пределах 100, их значения до 1000000. Скрипт должен быть выполнен менее чем за секунду. При количестве чисел 20 - 25 код выполняется с огромной задержкой, больше 25 вообще не тянет. Хотелось бы разобраться. Заранее благодарен.

from random import randint
from itertools import combinations

myset = set(randint(1, 1000000) for k in range(randint(1, 20)))

half_numb = sum(myset) // 2

print(myset)

mylist = []
for i in range(1, len(myset)):
    for j in combinations(myset, i):
        a = sum(j)
        if a in range(half_numb - 1000000, half_numb + 1000000):
            mylist.append(abs(a - sum(myset - set(j))))
print(min(mylist))

python алгоритм

Источник: Stack Overflow на русском

Answer 1

▲ 4Принят

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

Пусть битовый массив bits хранит текущие возможные суммы, а v - новое значение. Тогда bits | (bits << v) представляет возможные суммы с учетом прибавления нового значения. В коде используется более сложное выражение с использованием маски, чтобы в результат не попадали биты с номерами больше target. Начальное значение для bits - единица, что означает нулевую сумму. Номер старшего бита в конце вычисляется с помощью метода bit_length().

Код укладывается в полсекунды:

import pprint
import random


n = int(input())
a = tuple(random.randint(1, 1000000) for _ in range(n))
sum_a = sum(a)
print('random list')
pprint.pprint(a, compact=True)
print('random list sum', sum_a)

target = sum_a // 2
print('target', target)

mask = (1 << (target + 1)) - 1

bits = 1
for v in a:
    bits |= (bits & (mask >> v)) << v

best = bits.bit_length() - 1
print('best result', best)
print('diff', sum_a - 2 * best)

$ time echo 100 | python best-half-sum.py
random list
(774463, 428203, 965459, 818122, 193575, 281900, 888202, 463588, 843773, 745292,
 364132, 133468, 894830, 119204, 413031, 2747, 848141, 555223, 511840, 157509,
 984794, 533463, 77229, 865676, 353186, 913647, 855883, 315587, 593910, 726941,
 729062, 399663, 213904, 359355, 890092, 52267, 105879, 168716, 373423, 231081,
 595450, 17507, 844313, 765630, 531597, 721180, 29680, 664959, 784327, 656553,
 74145, 837963, 454037, 357505, 667483, 421984, 453216, 979355, 505268, 932855,
 483589, 19503, 39389, 129525, 605585, 467242, 245845, 89485, 351318, 751965,
 639115, 693835, 401083, 414712, 212093, 366859, 243789, 123832, 679784, 942795,
 789211, 907654, 799522, 398138, 555322, 664031, 665411, 794290, 837955, 822544,
 640505, 580149, 598882, 333417, 491232, 245162, 7552, 932056, 50860, 217223)
random list sum 50673926
target 25336963
best result 25336963
diff 0

real  0m0.440s
user  0m0.364s
sys   0m0.072s

Answer 2

▲ 1

Проверка in range не эквивалентна проверке больше меньше. Да и смысл её не понятен. Она не уменьшает сложность. Если используете - используйте больше-меньше

Перевод в set не соответствует условиям задачи. Не вижу в условиях ничего связанного с уникальным множеством.

sum(set(j)) считается три раза. Посчитайте один раз то что можно посчитать один раз. sum(set(mylist)) вообще фэйл.

Зачем считаете комбинации? В условиях задачи ряд, а не множество. Ряд делится срезом.

Answer 3

▲ 1

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

Для решения этой задачи на поиск минимальной разности весов двух куч среди случайно сгенерированных камней, использую динамическое программирование. Это снизит сложность алгоритма до O(n * sum) и позволит эффективно решить задачу даже при больших значениях n и w[i].

from random import randint

def find_min_difference(numbers):
    total_sum = sum(numbers)  # Вычисляем сумму всех чисел в переданном наборе
    half_sum = total_sum // 2  # Половина суммы всех чисел, которую мы хотим приблизить

    dp = [False] * (half_sum + 1)  # Создаем список для динамического программирования
    dp[0] = True

    for num in numbers:
        for j in range(half_sum, num - 1, -1):
            dp[j] |= dp[j - num]  # Заполняем список возможными суммами чисел

    min_diff = total_sum
    for j in range(half_sum, -1, -1):
        if dp[j]:
            min_diff = total_sum - 2 * j  # Находим минимальную разницу сумм между двумя частями
            break

    return min_diff

if __name__ == "__main__":
    myset = set(randint(1, 1000000) for k in range(randint(1, 20)))  # Генерируем случайный набор чисел

    print("Входной набор чисел:", myset)
    min_difference = find_min_difference(myset)
    print("Минимальная разница:", min_difference)

Ускорить выполнение кода Python

Ответы