Как сократить и оптимизировать алгоритм?

Question

[Dazai]

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

def izb(n:int):
    delt = []
    for i in range(1,n):
        if n % i == 0:
            delt.append(i)
    else:
        if sum(delt) > n:
            return True
        else:
            return False

def allizb():
    all_izb = []
    for i in range(12,28124):
        if izb(i) == True:
            all_izb.append(i)
    else:
        return all_izb

alizb = allizb()

i = 1 
otv = []

for i in range(12,28124):
    for g in alizb:
        for h in alizb:
            if i != (g+h):
                otv.append(i)
            print(i)
else:
    print( sum(otv ))

Comments

[longclaps]

Хотелось бы помочь, но в вашем коде столько идиотства, что единственно действенным способом помощи будет предложение - откомментируйте каждую строчку кода, объясните, что имели ввиду, зачем так написали.
Я абсолютно серьёзен, тут по-другому никак.

[Dazai]

longclaps,

def izb(n:int): #функция для определения является число избыточным или нет
    delt = [] # массив куда будут помещаться все делители числа n
    for i in range(1,n):
        if n % i == 0:
            delt.append(i) #добавления делителя в массив 
    else:
        if sum(delt) > n: #если сумма делителей больше самого числа то это избыточное числа то есть выводим True
            return True
        else:
            return False 

def allizb(): #функция в которой я получаю все избыточные числа до 28124(от 12 потому что по условию это самое маленькое избыточное число)
    all_izb = []
    for i in range(12,28124): #если число избыточное добавляю в массив, в конце верну массив со всеми числами
        if izb(i) == True:
            all_izb.append(i)
    else:
        return all_izb

alizb = allizb() 

i = 1 
otv = [] #массив куда буду вносить числа которые не могут быть суммой двух избыточных чисел
for i in range(12,28124): 
    for g in alizb:
        for h in alizb:
            if i != (g+h): #если i не равна сумме 2 избыточных чисел из массива то добавляем
                otv.append(i)
            print(i)
else:
    print( sum(otv )) # в конце выводим сумму всех чисел

[longclaps]

Dazai,

def izb(n:int): #функция для определения является число избыточным или нет
    delt = [] # массив куда будут помещаться все делители числа n
    for i in range(1,n):
        if n % i == 0:
            delt.append(i) #добавления делителя в массив 
    else:
        if sum(delt) > n: #если сумма делителей больше самого числа то это избыточное числа то есть выводим True
            return True
        else:
            return False

Это не функция, это кусок дерьма. Зачем копить делители в списке, по отдельности они не нужны. Перепишите.
Выражение sum(delt) > n возвращает логическое значение и может быть передано напрямую в оператор return. Перепишите.

[Dazai]

longclaps,

def izb(n:int):
    delt = 0
    for i in range(1,n):
        if n % i == 0:
            delt +=i 
    return delt > n

print(izb(11))

Так будет лучше? Что еще исправить?

[longclaps]

Dazai, настройся на долгую серию. Дерьма по-прежнему выше крыши.
Все числа делятся на 1 - зачем проверять?
Ни одно не делится на более чем n//2
Перепиши

[Dazai]

longclaps,

def izb(n:int):
    delt = 1
    for i in range(2, (n//2) + 1 ):
        if n % i == 0:
            delt +=i 
    return delt > n

[longclaps]

Dazai, отлично. Теперь я уже сам расскажу, почему это по-прежнему дерьмо и как сделать лучше.
Ты знаешь что такое решето Эратосфена, можешь написать с его помощью генератор простых чисел?

[Dazai]

longclaps, первый раз слышу об этом, генератор простых чисел писал лишь такой:

def simple(n):
    lst=[2]
    for i in range(3, n+1, 2):
        if (i > 10) and (i%10==5):
            continue
        for j in lst:
            if j*j-1 > i:
                lst.append(i)
                break
            if (i % j == 0):
                break
        else:
            lst.append(i)
    if max(lst) == n:
        return True
    else:
        return False
    
simple = [i for i in range((2*10**6) + 1) if simple(i) == True]
print(simple)

Простые числа до 2 миллионов, за основу для функции проверки на простоту, взял код со статьи на хабре

[longclaps]

Dazai, гугли, читай вики, разберись - это общее место, есть в школьной программе

[Dazai]

longclaps, после написать генератор?

[longclaps]

Dazai, да, это очень просто. Сам по себе он здесь не нужен, но некоторая техника из него будет очень полезна.
Повторяю, это просто, и, если есть время - делай это сейчас.

[longclaps]

Dazai, что-то ты темп потерял. Вот смотри, изучай.

N = 50  # для наглядности возьмём небольшое N
sum_of_dividers = [1] * N  # все числа делятся на 1, проходили уже
for i in range(2, N // 2 + 1):  # начнем делители с двойки
    for j in range(i * 2, N, i):  # ко всем ячейкам с адресом,
        # кратным i но большим, чем i,
        sum_of_dividers[j] += i  # прибавим делитель i
for i in range(2, N):
    print(i, sum_of_dividers[i], '' if sum_of_dividers[i] <= i else 'избыточное')

[Dazai]

longclaps, для меня сейчас это выглядит безумно сложно

[Dazai]

longclaps, ну в целом я разобрался как это работает, очень сложно для понимания

[Dazai]

longclaps, а что же дальше?

[longclaps]

Dazai, дальше нужно вернуться к намеченой программе. Ты хотел знать, "Как сократить и оптимизировать алгоритм", мой ответ был - никак, его можно переписать аккуратнее, но сам по себе он - дерьмо.
1. Нужно разобраться, как это работает, не в общих чертах, а вполне. Там 8 строк, из них одна - комментарий, 1 тривиальная (N = 50), две последние - вывод, тоже тривиальный. Остаётся вполне разобраться, что там в четырёх строках. Я не знаю, как именно ты разбирался и что вызвало затруднения. Расскажи.
2. Нужно разобраться с решетом Эратосфена, просто нужно и всё.
3. Нужно понять, почему тот код - дерьмо, а этот получше. Придумать этому объяснения.

[Dazai]

longclaps, ну ваш алгоритм работает так:
Создается массив, где 50 единиц (можно назвать это ячейками). Потом начинается перебор делителей с первого простого числа до n//2 (ибо больше уже не будет и это предел). Делитель заносится в ячейку больше его самого в 2 раза (первое число которое делится на него ) и потом в каждую с шагом в этот делитель, то есть в те которые делятся на него нацело. И так происходит с каждым числом от 2 до n//2.
Возможно объяснение немного глупое, но надеюсь я понял правильно

[longclaps]

с первого простого числа

Разве?

[Dazai]

longclaps, перебор начинается с 2, ибо добавлять единицу нет смысла тк у нас есть уже список где 50 единичек

[Dazai]

longclaps, с решетом Эратосфена я тоже разобрался, понял как работает алгоритм. Вот он:

n = 30    # число, до которого хотим найти простые числа 
numbers = list(range(2, n + 1))
for number in numbers:
    if number != 0:
        for candidate in range(2 * number, n+1, number):
            numbers[candidate-2] = 0    
print(*list(filter(lambda x: x != 0, numbers)))

[Dazai]

longclaps, что мне еще сделать? И можете дать совет: что почитать, поизучать, посмотреть чтобы лучше писать алгоритмы и владеть языком? И вот не говнокодить

[longclaps]

Dazai,

с первого простого числа

Разве?

Разве речь шла о простых делителях?

Делитель заносится в ячейку

Делитель добавляется (суммируется)
Читай что пишешь, уже будет толк.

3. Нужно понять, почему тот код - дерьмо, а этот получше. Придумать этому объяснения.

Ну так?

[Dazai]

longclaps, тот это я так понимаю это:

def izb(n:int):
    delt = 1
    for i in range(2, (n//2) + 1 ):
        if n % i == 0:
            delt += i 
    return delt > n

или вся остальная программа?

[longclaps]

Dazai, да, ведь и у меня нет целой программы )

[Dazai]

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

[longclaps]

Dazai, хорошо, позже проверим.
Почитай про O-большое нотацию. У тебя там сколько? А у меня?

[Dazai]

longclaps, ну мой получается O(n), а ваш O(log n). Так ведь?..

[longclaps]

Dazai, я бы предпочел посчитать затраты на круг, при вычислении всех избыточных - тогда O(N**2) иO(N*log N).
А что с генераторами простых, старым и новым? А что там со второй частью твоего решения?

[Dazai]

longclaps, старый генератор получается О(n), а новый О(log n ). А дальнейшее решение:

def allizb(): #функция в которой я получаю все избыточные числа до 28124(от 12 потому что по условию это самое маленькое избыточное число)
    all_izb = []
    for i in range(12,28124): #если число избыточное добавляю в массив, в конце верну массив со всеми числами
        if izb(i) == True:
            all_izb.append(i)
    else:
        return all_izb

Это получается О(n)
А часть ниже:

i = 1 
otv = [] #массив куда буду вносить числа которые не могут быть суммой двух избыточных чисел
for i in range(12,28124): 
    for g in alizb:
        for h in alizb:
            if i != (g+h): #если i не равна сумме 2 избыточных чисел из массива то добавляем
                otv.append(i)
            print(i)
else:
    print( sum(otv )) # в конце выводим сумму всех чисел

это О(n**3)
Надеюсь правильно определил, но на самом деле тема достаточно непростая

[longclaps]

Dazai, еще раз: можно считать и средние затраты на одно число, и общие для результата в целом, но уж если сравнивать алгоритмы - надо мерять их по единой методе.
Ладно, самое главное - ты нащупал, где у тебя главная жопа. Но посмотри: в самом внутреннем цикле у тебя происходит вычисление одного и того же, (g+h). Нельзя ли как-то съэкономить?

[Dazai]

longclaps,

def c(): #получится массив с суммами избыточных чисел
    otv = [] 
    for f in alizb:
        for s in alizb:
            otv.append(f+s)
    return otv


arr = []
for i in range(12,28124):
    if i not in c(): # если i там нет то добавить
        arr.append(i)

так получится быстрее или наоборот хуже?

[longclaps]

Dazai, быстрее. Вот, смотри, как сделать это грамотно. Я спать.

def final(N):
    sum_of_dividers = [1] * N  # все числа делятся на 1, проходили уже
    for i in range(2, N // 2 + 1):  # начнем делители с двойки
        for j in range(i * 2, N, i):  # ко всем ячейкам с адресом,
            # кратным i но большим, чем i,
            sum_of_dividers[j] += i
    result = list(range(N))  # изначально все числа - кандидаты в нераскладываемые
    others = []  # здесь будем копить варианты второго слагаемого
    sum_of_dividers[0] = 0  # заглушим чтоб ноль не пролазил через if i < s
    for i, s in enumerate(sum_of_dividers):
        if i < s:  # i избыточное
            others.append(i)  # случай i + i должен быть учтен в этом же цикле
            for j in others:
                j += i
                if j >= N:  # выход за пределы диапазона
                    break  # в others числа по нарастающей, остальные заведомо больше
                result[j] = 0
    return sum(result)

[Dazai]

longclaps, Огромное вам спасибо за помощь. Но я хотел бы спросить, как мне лучше развиваться и двигаться в python? Не допускать глупых ошибок и тд. Что то почитать, посмотреть? Какие то определенные темы изучить? Я понял, что мне нужно углубиться в тему "О-большое", но что еще? Еще раз спасибо за вашу помощь.

[longclaps]

Dazai, запишись сюда.

[Dazai]

longclaps, спасибо за совет

[longclaps]

Dazai, готов продолжить?

[Dazai]

longclaps, Извините, а разве код не был до конца оптимизирован?.. Или вы хотите помочь мне развиваться в программировании? (простите если я понял что то не так )

[longclaps]

Dazai, более чем не был

[longclaps]

Dazai, найди или напиши инструмент, замеряющий время исполнения функции.
Разбей существующее решение на 2 части: получение избыточных и вычисление суммны несоставимых

[Dazai]

longclaps, для измерения времени нашел такое решение:

f = '''def final(N):
    sum_of_dividers = [1] * N  # все числа делятся на 1, проходили уже
    for i in range(2, N // 2 + 1):  # начнем делители с двойки
        for j in range(i * 2, N, i):  # ко всем ячейкам с адресом,
            # кратным i но большим, чем i,
            sum_of_dividers[j] += i
    result = list(range(N))  # изначально все числа - кандидаты в нераскладываемые
    others = []  # здесь будем копить варианты второго слагаемого
    sum_of_dividers[0] = 0  # заглушим чтоб ноль не пролазил через if i < s
    for i, s in enumerate(sum_of_dividers):
        if i < s:  # i избыточное
            others.append(i)  # случай i + i должен быть учтен в этом же цикле
            for j in others:
                j += i
                if j >= N:  # выход за пределы диапазона
                    break  # в others числа по нарастающей, остальные заведомо больше
                result[j] = 0
    '''


def measure_time(function: str):
    elapsed_time = timeit.timeit(function, number=100)/100
    print(elapsed_time)


measure_time(f)

Выводит значение 1.2200000000003873e-07

[Dazai]

longclaps, а в каком смысле разделить? Разместить эти части в разные функции или как ?

[longclaps]

Dazai, решение в принципе рабочее, но из-за того, что функция засунута в строку, работать с ней неудобно: IDE не понимает, чта там функция, нет подсветки синтаксиса, автодополнения, через жопу сообщения об ошибках. Предлагаю такой декоратор (если не знаешь про декораторы - почитай вскользь, не задерживаясь)

from time import time, sleep


def timer(f):
    def wrapper(*args, **kwargs):
        t, res = time(), f(*args, **kwargs)
        print(f"{f.__name__}, sec: {time() - t:f}")
        return res

    return wrapper

@timer
def slow_func(t):
    sleep(t)
    return 'I`m finish!'

print(slow_func(1))

[longclaps]

а в каком смысле разделить?

Dazai, создать 2 функции, первая принимает N и возвращает список избыточных меньше N, вторая принимает его и N и возвращает итоговую сумму

[Dazai]

longclaps, Получилось что-то такое:

def get_izb(N: int):
    sum_of_dividers = [1] * N  
    for i in range(2, N // 2 + 1):  
        for j in range(i * 2, N, i):
            sum_of_dividers[j] += i
    others = []  
    sum_of_dividers[0] = 0  
    for i, s in enumerate(sum_of_dividers):
        if i < s:  
            others.append(i) 
    return others


def get_sum(arr: dict, N: int):
    summ = []
    all_nums = list(range(N))
    for f in arr:
        for s in arr:
            s = f + s
            if s > N:
                break
            summ.append(s)
    lst = [o for o in all_nums if o not in summ]
    return sum(lst)


def final(N: int):
    return get_sum(get_izb(N), N)

Ответ выводит правильный

[longclaps]

def get_sum(arr: dict, N: int):
Dazai, dict?? Куда спешишь?

[Dazai]

longclaps, забыл изменить, осталось от прошлых попыток и экспериментов

[longclaps]

Dazai, приделай таймер к функциям.
Исследуй такой вариант второй функции, как это работает

def solve_by_set(abundants, lim):
    abundants_set = set(abundants)
    return sum(i for i in range(1, lim) if all(i - j not in abundants_set for j in abundants))

Обрати внимание на имена аргументов - и приведи другие варианты к однообразным аргументам.

[Dazai]

longclaps, С вашим решением разобрался, сделал как вы сказали вот что вышло:

from time import time, sleep


def timer(f):
    def wrapper(*args, **kwargs):
        t, res = time(), f(*args, **kwargs)
        print(f"{f.__name__}, sec: {time() - t:f}")
        return res

    return wrapper

@timer
def get_redundant_nums(limit: int):
    dividers = [1] * limit
    for i in range(2, limit // 2 + 1):
        for j in range(i * 2, limit, i):
            dividers[j] += i
    redundant_nums = []
    dividers[0] = 0
    for i, s in enumerate(dividers):
        if i < s:
            redundant_nums.append(i)
    return redundant_nums

@timer
def get_redundants_sum(redundants: list, limit: int):
    redundants_set = set(redundants)
    return sum(i for i in range(1, limit) if all(i - j not in redundants_set for j in redundants))


@timer
def final(limit: int):
    return get_redundants_sum(get_redundant_nums(limit), limit)


print(final(50))

Время выдает такое:

get_redundant_nums, sec: 0.000000
get_redundants_sum, sec: 0.000000
final, sec: 0.001018

[longclaps]

Это похоже на придирку, но всё же: есть оригинальный текст задачи, и там используется термин "abundant numbers", переведенный как "избыточные числа". Не то чтобы эти сраные избыточные числа так уж важны - нет, я их вообще видел один-единственный раз, именно в этой задаче. Тем не менее придерживаться оригинальной терминологии гораздо лучше, чем городить свою. И гораздо проще - ничего не надо придумывать, вот же, есть готовое.
Не знаю, в чем ты разобрался. Когда я брал N=50, я просто демонстрировал, какие числа из первых 50 избыточные, ну так чтобы все они влезли в экран. Никакого другого смысла в 50 не было, в задаче было N=28124, при таком значении ты получал бы какие-то осмысленные времена выполнения, а не голые нули, кроме того, ты получал бы ответ на собственно задачу.
В данном случае я бы хотел видеть решение с двумя этапами и временами их выполнения, суммарное время нафиг не нужно - ну это мелочи. Хотел так:

@timer
def get_abundants(limit: int):
    dividers = [1] * limit
    for i in range(2, limit // 2 + 1):
        for j in range(i * 2, limit, i):
            dividers[j] += i
    return [i for i in range(12, limit) if i < dividers[i]]


@timer
def solve_by_set(abundants: list, limit: int):
    abundants_set = set(abundants)
    return sum(i for i in range(1, limit) if all(i - j not in abundants_set for j in abundants))


N = 28124
Abundants = get_abundants(N)  # тут имеем время первого этапа
print(solve_by_set(Abundants, N))  # тут время второго и результат

Теперь про то, с чем ты там разобрался: на этом этапе это самое важное. Итак, с чем ты разабрался, расскажи.

[longclaps]

Dazai, смысл разбиения решения на этапы в том, что я могу их по-разному реализовывать и сравнивать:

@timer
def solve_by_product(abundants, lim):
    result = list(range(lim))  # изначально все числа - кандидаты в нераскладываемые
    others = []  # здесь будем копить варианты второго слагаемого
    for i in abundants:
        others.append(i)  # случай i + i должен быть учтен в этом же цикле
        for j in others:
            j += i
            if j >= lim:  # выход за пределы диапазона
                break  # в others числа по нарастающей, остальные заведомо больше
            result[j] = 0
    return sum(result)


print(solve_by_product(Abundants, N))  # тут время второго и результат

Я хочу, чтобы ты подумал о разнице этих реализаций второго этапа.

[Dazai]

longclaps, я разобрался с принципом работы функции

def solve_by_set(abundants: list, limit: int):
    abundants_set = set(abundants)
    return sum(i for i in range(1, limit) if all(i - j not in abundants_set for j in abundants))

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

[Dazai]

longclaps, не могу найти разницу в них, увидел лишь небольшую разницу в скорости...

[Dazai]

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

[longclaps]

Dazai, смотри: я демонстрирую тебе автомобиль на бензиновом двигателе и электромобиль, спрашиваю: в чем разница? Ты не видишь разницы, говоришь - примерно одинаковые. Каковы твои шансы стать конструктором? Ноль.
Тут две совсем разные стратегии решения задачи. Судя по ответу, ты не понимаешь ни одну, ни другую. Это два очень маленьких куска кода. Вообрази себя процессором, попробуй исполнить их в своей голове.
Вот тебе упрощенный, но идейно такой же код. Думай. Я беру паузу на неделю.

@timer
def solve_by_product(abundants, lim):
    result = list(range(lim))
    for i in abundants:
        for j in abundants:
            if i + j < lim:
                result[i + j] = 0
    return sum(result)

[Dazai]

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

[longclaps]

Dazai, верно лишь отчасти. Важно вот что: в одном случае я перебираю все возможные пары слогаемых и "бомблю result" нулями по адресу их сумм. Затем я прохожусь по result и суммирую оставшиеся ненулевые значения. Второй этап занимает мало времени, О(N), зато первый, подготовительный - О(N**2)
В другом же способе я перебираю возможные суммы (числа от 1 до lim) и для каждого ищу, есть ли ему хоть одна пара подходящих слагаемых.
В чем разница? А вот в чем: в первом способе я совершаю (упрощенный вариант) 6965**2==48511225 сложений, если сумма не превышает lim, обнуляю по этому адресу result, это 24294140 присвоений. Длина(result)==28124, делим одно на другое - имеем 864, столько раз в среднем происходит обнуление каждой ячейки.
С другой стороны, во втором случае, мы берем целевую сумму и просматриваем abundants на предмет наличия в нём пары слагаемых, дающих эту сумму. Сколько операций при этом совершается? Ответ зависит от:
Если таких слагаемых нет, а всего таких чисел 1456, (а их сумма 4179871), так вот, в этих случаях будут перебраны все 6965 избыточных чисел, и для каждого из них не найдётся второго слагаемого. Заметь, доля таких случаев - всего 1456/28124==0.05
Если же подходящие слагаемые есть - мы находим их быстро, ведь большинство сумм реализуется множеством сочетаний слагаемых, и первые решения находятся буквально сразу.

Итак, замечено: от тебя не исходит кода, ты даже не пытаешься провести численный эксперимент. Отсюда задание - подсчитать, сколько пар слагаемых перебирается вторым способом при решении задачи целиком.

[Dazai]

И так, сразу скажу в ответе я крайне не уверен и я думаю не просто так. Но я хочу показать то как я пришел к нему.
Для начала я сделать функцию чуть-чуть более читаемой лично для меня:

def get_redundants_sum(redundants: list, limit: int):
    redundants_set = set(redundants)
    arr = []
    for i in range(1, limit): # перебор от 1 до 28124 
        if all(i - j not in redundants_set for j in redundants): # если i - j нет в reduants_set добавляем
            arr.append(i)
    return sum(arr)

Получается мы перебираем все числа от 1 до 28124, и позже проверяем если все i - j ( j это избыточное число ) не находится во множестве избыточных чисел, то мы добавляем его в список. Отсюда я сделал вывод, что для каждой i нужно 6569 j и на основе этого я перемножил 28124 * 6569 и получил 195883660 пар чисел

[Dazai]

longclaps, если ответ неверен, скажите мне об этом и я подумаю еще

[longclaps]

Dazai, ты начал разворачивать однострочник, но недокончил.

def solve_by_set(abundants: list, limit: int):
    abundants_set = set(abundants)
    res = cnt = 0 #  res будет 4179871, а cnt - посмотрим
    for i in range(1, limit):  # для каждого i из диапазона 1..N
        for j in abundants:  # для каждого j из избыточных
            cnt += 1  # мы же считаем сколько нужно элементарных операций
            if i - j in abundants_set:  # если есть избыточное, дополняющие j до i 
                break  # хватит!
        else:  # а если не случилось брейка
            res += i  # значит не случилось
    return res, cnt

print(*solve_by_set(Abundants, N))

Твои рассуждения можно и нужно было проверить. Можно было попробовать воспроизвести мои результаты (там была куча цифр), потренироваться, самопровериться. Но ты приволок свои выводы на проверку мне.

Забудем пока про избыточные, толку от них никакого. Что, если вместо них будут просто все числа из диапазона 1..N? А что, если все четные из этого диапазона? А все нечетные? Первым способом, вторым, на компе, на бумажке - какой способ когда лучше и почему?

[Dazai]

longclaps, То есть нужно заменить избыточные числа обычными в диапазоне от 1 до N и подсчитать сколько пар слагаемых? А дальше уже заменять их на нечетные и так далее? И проверить какой способ лучше и почему. Я правильно понял задание? Или что-то упустил?
PS: извиняюсь за то что не отвечал такое большое количество времени ( не знаю вообще нужны ли извинения )

Answer 1

[Артем Имаев]

можно тут посмотреть
можно использовать nimpy(использует NIM), pypy(JIT), Cython(C код компилирует твою программу).
источник