Python: производительность поиска делителей

Question

Сравнительный анализ этих функций:

def divisors_optimized(number):
    square_root = int(math.sqrt(number))

    for divisor in range(1, square_root):
        if number % divisor == 0:
            yield divisor
            yield number / divisor

    if square_root ** 2 == number:
        yield square_root

def number_of_divisors_optimized(number):
    count = 0
    square_root = int(math.sqrt(number))

    for divisor in range(1, square_root):
        if number % divisor == 0:
            count += 2

    if square_root ** 2 == number:
        count += 1

    return count

Вы можете видеть, что основная структура идентична в обоих.

Код теста:

number = 9999999
for i in range(10):
    print(f"iteration {i}:")
    start = time.time()
    result = list(utils.divisors_optimized(number))
    end = time.time()
    print(f'len(divisors_optimized) took {end - start} seconds and found {len(result)} divisors.')

    start = time.time()
    result = utils.number_of_divisors_optimized(number)
    end = time.time()
    print(f'number_of_divisors_optimized took {end - start} seconds and found {result} divisors.')

    print()

Выход:

iteration 0:
len(divisors_optimized) took 0.00019598007202148438 seconds and found 12 divisors.
number_of_divisors_optimized took 0.0001919269561767578 seconds and found 12 divisors.

iteration 1:
len(divisors_optimized) took 0.00019121170043945312 seconds and found 12 divisors.
number_of_divisors_optimized took 0.00020599365234375 seconds and found 12 divisors.

iteration 2:
len(divisors_optimized) took 0.000179290771484375 seconds and found 12 divisors.
number_of_divisors_optimized took 0.00019049644470214844 seconds and found 12 divisors.

iteration 3:
len(divisors_optimized) took 0.00019025802612304688 seconds and found 12 divisors.
number_of_divisors_optimized took 0.00020170211791992188 seconds and found 12 divisors.

iteration 4:
len(divisors_optimized) took 0.0001785755157470703 seconds and found 12 divisors.
number_of_divisors_optimized took 0.00017905235290527344 seconds and found 12 divisors.

iteration 5:
len(divisors_optimized) took 0.00022721290588378906 seconds and found 12 divisors.
number_of_divisors_optimized took 0.00020170211791992188 seconds and found 12 divisors.

iteration 6:
len(divisors_optimized) took 0.0001919269561767578 seconds and found 12 divisors.
number_of_divisors_optimized took 0.00018930435180664062 seconds and found 12 divisors.

iteration 7:
len(divisors_optimized) took 0.00017881393432617188 seconds and found 12 divisors.
number_of_divisors_optimized took 0.00017905235290527344 seconds and found 12 divisors.

iteration 8:
len(divisors_optimized) took 0.00017976760864257812 seconds and found 12 divisors.
number_of_divisors_optimized took 0.0001785755157470703 seconds and found 12 divisors.

iteration 9:
len(divisors_optimized) took 0.00024819374084472656 seconds and found 12 divisors.
number_of_divisors_optimized took 0.00020766258239746094 seconds and found 12 divisors.

Вы можете видеть, что время выполнения очень близко, каждый раз предпочтение либо.

Может ли кто-нибудь объяснить мне, почему создание списка из генератора и получение его длины примерно так же быстро, как просто подсчет во время итерации? Я имею в виду, не должно выделяться память (list()) будет намного дороже, чем задания?

Я использую Python 3.6.3 .

Answer 1

Вы тестируете гораздо больше вещей, чем производите. Цена int против list операций генератора для случая "найденного фактора" меркнет по сравнению с объемом выполненных работ в целом. Вы выполняете более 3000 пробных делений; двенадцать yields против двенадцати дополнений - это чурбанье против такого рода работы. Замена дополнения /yieldс pass (ничего не делая), вы обнаружите, что он все еще работает (примерно) в то же время:

def ignore_divisors_optimized(number):
    square_root = int(math.sqrt(number))

    for divisor in range(1, square_root):
        if number % divisor == 0:
            pass

    if square_root ** 2 == number:
        pass

И микробенчмаркинг с ipython"s %timeit магия:

>>> %timeit -r5 number_of_divisors_optimized(9999999)
266 µs ± 1.85 µs per loop (mean ± std. dev. of 5 runs, 1000 loops each)
>>> %timeit -r5 list(divisors_optimized(9999999))
267 µs ± 1.29 µs per loop (mean ± std. dev. of 5 runs, 1000 loops each)
>>> %timeit -r5 ignore_divisors_optimized(9999999)
267 µs ± 1.43 µs per loop (mean ± std. dev. of 5 runs, 1000 loops each)

Дело в том, что number_of_divisors была ли микросекунда быстрее, не имеет значения (дрожание от повторных тестов выше, чем микросекунда); все они в основном одинаковы по скорости, потому что>99% работы - это цикл и тест, а не то, что делается при прохождении теста.

Это пример правила оптимизации 90/10: примерно 90% вашего времени тратится на 10% вашего кода (в данном случае это само пробное подразделение); 10% тратится на остальные 90% вашего кода. Вы оптимизируете небольшую часть 90% кода, который выполняется 10% времени, и это не помогает, потому что подавляющее большинство времени тратится на if number % divisor == 0: линия. Если вы удалите этот тест в пользу просто цикл по range ничего не делая, время выполнения падает до ~78 мкс в моих локальных микробенчмарках, что означает, что тест занимает почти 200 мкс времени выполнения, что вдвое больше, чем требует весь остальной код, вместе взятый.

Если вы хотите оптимизировать это, вам нужно взглянуть на подходы, которые либо ускоряют саму строку пробного деления (что в основном означает другой интерпретатор Python, либо использует Cython для компиляции до C), либо способы запуска этой строки меньше раз (например, предварительно вычислить возможные простые факторы до определенной границы, поэтому для любого заданного входного значения вы можете избежать тестирования непростых делителей, а затем производить / вычислять число не простых факторов из известных простых факторов и их кратность).