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

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

    DazaiCoder
    @DazaiCoder Автор вопроса
    longclaps, если ответ неверен, скажите мне об этом и я подумаю еще
    Написано
  • Как сократить и оптимизировать алгоритм?

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

    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 пар чисел
    Написано
  • Как сократить и оптимизировать алгоритм?

    DazaiCoder
    @DazaiCoder Автор вопроса
    longclaps, я точно нн уверен, но мне кажется, что разница этих функций в том, что в первой берутся все числа и исключаются не нужные и из этого получается ответ, а во второй подбирают именно нужные числа и складывают их
    Написано
  • Как сократить и оптимизировать алгоритм?

    DazaiCoder
    @DazaiCoder Автор вопроса
    longclaps, Возможно разница в том, что в более кратком варианте мы никак не изменяем списки, а в другом мы изменяем содержимое, добавляем
    Написано
  • Как сократить и оптимизировать алгоритм?

    DazaiCoder
    @DazaiCoder Автор вопроса
    longclaps, не могу найти разницу в них, увидел лишь небольшую разницу в скорости...
    Написано
  • Как сократить и оптимизировать алгоритм?

    DazaiCoder
    @DazaiCoder Автор вопроса
    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 я подставлял уже на каком то "автомате", чтобы проверить ответ, из за не внимательности не подставил необходимое число, поспешил.
    А функция реализацией похожа на мою, но ваша более краткая и элегантная что ли
    Написано
  • Как сократить и оптимизировать алгоритм?

    DazaiCoder
    @DazaiCoder Автор вопроса
    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
    Написано
  • Как сократить и оптимизировать алгоритм?

    DazaiCoder
    @DazaiCoder Автор вопроса
    longclaps, забыл изменить, осталось от прошлых попыток и экспериментов
    Написано
  • Как сократить и оптимизировать алгоритм?

    DazaiCoder
    @DazaiCoder Автор вопроса
    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)

    Ответ выводит правильный
    Написано
  • Как сократить и оптимизировать алгоритм?

    DazaiCoder
    @DazaiCoder Автор вопроса
    longclaps, а в каком смысле разделить? Разместить эти части в разные функции или как ?
    Написано
  • Как сократить и оптимизировать алгоритм?

    DazaiCoder
    @DazaiCoder Автор вопроса
    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
    Написано
  • Как сократить и оптимизировать алгоритм?

    DazaiCoder
    @DazaiCoder Автор вопроса
    longclaps, Извините, а разве код не был до конца оптимизирован?.. Или вы хотите помочь мне развиваться в программировании? (простите если я понял что то не так )
    Написано
  • Как исправить загрузку диска на 100 % Win 10?

    DazaiCoder
    @DazaiCoder Автор вопроса
    в диспетчере не показывается ничего, но если зайти в монитор ресурсов то там показывает, что system грузит тем что диск туда записывает что то 2 миллиона байт/с
    Написано
  • Как исправить загрузку диска на 100 % Win 10?

    DazaiCoder
    @DazaiCoder Автор вопроса
    SagePtr, TOSHIBA MQ01ABD100 ( у меня ноутбук если эта информация необходима )
    Написано
  • Как сократить и оптимизировать алгоритм?

    DazaiCoder
    @DazaiCoder Автор вопроса
    longclaps, спасибо за совет
    Написано
  • Как сократить и оптимизировать алгоритм?

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

    DazaiCoder
    @DazaiCoder Автор вопроса
    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)

    так получится быстрее или наоборот хуже?
    Написано
  • Как сократить и оптимизировать алгоритм?

    DazaiCoder
    @DazaiCoder Автор вопроса
    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)
    Надеюсь правильно определил, но на самом деле тема достаточно непростая
    Написано
  • Как сократить и оптимизировать алгоритм?

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