Разница в сложности времени выполнения двух, казалось бы, похожих решений

Question

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

Это оператор присваивания

Целью этой проблемы является реализация варианта алгоритма 2-SUM, описанного в лекциях этой недели.

Файл содержит 1 миллион целых чисел, как положительных, так и отрицательных (возможно, есть некоторые повторения! ). Это ваш массив целых чисел, в i-й строке которого указан i-й элемент массива.

Ваша задача - вычислить количество целевых значений t в интервале [-10000,10000](включительно), так что во входном файле есть различные числа x, y, которые удовлетворяют x + y = t. Переменная all_ints представляет собой список, содержащий все целые числа

hashtable = set(all_ints)
min_t = -1024
max_t = -min_t + 1

solutions = 0
k = 0

from time import time

# Solution 1 that I wrote
t0 = time()
for n in range(min_t, max_t):
    solutions+=1 if any([True if 2*i!=n and n-i in hashtable else False for i in hashtable]) else 0


# Solution 2 that I found online
t1 = time()
solutions2 = sum(1 for n in range(min_t, max_t) if any(n - x in hashtable and 2 * x != n for x in hashtable))
t2 = time()

print(t1-t0) #857.0168697834015
print(t2-t1) #591.8803908824921

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

Какая основная разница между двумя реализациями, которая вызывает это

Answer 1

Как сказано выше, вы делаете True, если ... иначе False явно. Это дополнительный шаг, который при больших значениях может показать некоторые издержки. Кроме того, сначала вы строите весь список, а затем проверяете, есть ли какое-либо значение в нем True. Второе решение использует генератор, который является ленивым, и как только он встречает значение True, он останавливает выполнение, что может сэкономить много времени.

Пример ниже - ваш базовый код, использующий целые числа 10K (вместо миллиона) для тестирования. Обратите внимание, что этот способ синхронизации не очень надежен (лучше использовать timeit), но для иллюстрации, я думаю, он дает достаточно хорошую идею.

import random
from time import time

all_ints = [random.randint(0, int(1E04)) for i in range(int(1E04))]
hashtable = set(all_ints)
min_t = -1024
max_t = -min_t + 1

solutions = 0
k = 0

# Solution 1 that I wrote
t0 = time()
for n in range(min_t, max_t):
    solutions += 1 if any(2*i!=n and n-i in hashtable for i in hashtable) else 0


# Solution 2 that I found online
t1 = time()
print('solution_1', t1-t0)

solutions2 = sum(1 for n in range(min_t, max_t) if any(n - x in hashtable and 2 * x != n for x in hashtable))
t2 = time()

assert solutions == solutions2

print('solution_2', t2-t1)

• solution_1 11.994043588638306
• solution_2 2.5971169471740723

Теперь давайте удалим понимание списка в пользу генератора:

solutions += 1 if any(True if 2*i!=n and n-i in hashtable else False for i in hashtable) else 0

• solution_1 7.071138620376587
• solution_24.714937686920166

Дополнительное улучшение: вам не нужно 'True if ...', вы можете просто передать само условие:

solutions += 1 if any(2*i!=n and n-i in hashtable for i in hashtable) else 0

• solution_16.017507076263428
• solution_2 2.9826767444610596

Наконец: всякий раз, когда у вас есть условие, состоящее из нескольких условий, очень хорошо подумайте о порядке условий. Заказывайте их от самого быстрого до самого медленного. В вашем случае выполнение 2*i!=n может быть медленнее (особенно для больших значений), чем поиск по множеству (что очень быстро), поэтому я бы предложил поменять порядок.

solutions += 1 if any(n-i in hashtable and 2*i!=n for i in hashtable) else 0

• solution_13.184004545211792
• solution_2 2.4962565898895264

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

---

Вот лучший тест (но выводы те же):

import timeit

setup = '''
import random
all_ints = [random.randint(0, int(1E03)) for i in range(int(1E03))]
hashtable = set(all_ints)
min_t = -1024
max_t = -min_t + 1
'''


# Solution 1 (original)
def sum_one(min_t, max_t, hashtable):
    solutions = 0
    for n in range(min_t, max_t):
        solutions += 1 if any([True if 2 * i != n and n - i in hashtable else False for i in hashtable]) else 0

    return solutions

# Solution 1 (generator instead of list comprehension)
def sum_one_gen(min_t, max_t, hashtable):
    """
    - generator instead of list comprehension
    """
    solutions = 0
    for n in range(min_t, max_t):
        solutions += 1 if any(True if 2 * i != n and n - i in hashtable else False for i in hashtable) else 0

    return solutions


def sum_one_gen_implicit_conditional(min_t, max_t, hashtable):
    """
    - generator instead of list comprehension
    - remove True if ... else False in favour of implicit conditional
    """
    solutions = 0
    for n in range(min_t, max_t):
        solutions += 1 if any(2 * i != n and n - i in hashtable for i in hashtable) else 0

    return solutions


def sum_one_gen_swap_conditions(min_t, max_t, hashtable):
    """
    - generator instead of list comprehension
    - remove True if ... else False in favour of implicit conditional
    - swap conditions
    """
    solutions = 0
    for n in range(min_t, max_t):
        solutions += 1 if any(n - i in hashtable and 2 * i != n for i in hashtable) else 0

    return solutions

def sum_two(min_t, max_t, hashtable):
    return sum(1 for n in range(min_t, max_t) if any(n - x in hashtable and 2 * x != n for x in hashtable))


sum_one_s = timeit.timeit(stmt='sum_one(min_t, max_t, hashtable)',
                          setup=setup + 'from __main__ import sum_one',
                          number=1000)
print('sum_one_s', sum_one_s)

sum_one_gen_s = timeit.timeit(stmt='sum_one_gen(min_t, max_t, hashtable)',
                              setup=setup + 'from __main__ import sum_one_gen',
                              number=1000)
print('sum_one_gen_s', sum_one_gen_s)

sum_one_gen_implicit_conditional_s = timeit.timeit(stmt='sum_one_gen_implicit_conditional(min_t, max_t, hashtable)',
                                                   setup=setup + 'from __main__ import sum_one_gen_implicit_conditional',
                                                   number=1000)
print('sum_one_gen_implicit_conditional_s', sum_one_gen_implicit_conditional_s)

sum_one_gen_swap_conditions_s = timeit.timeit(stmt='sum_one_gen_swap_conditions(min_t, max_t, hashtable)',
                                              setup=setup + 'from __main__ import sum_one_gen_swap_conditions',
                                              number=1000)
print('sum_one_gen_swap_conditions_s', sum_one_gen_swap_conditions_s)

sum_two_s = timeit.timeit(stmt='sum_two(min_t, max_t, hashtable)',
                          setup=setup + 'from __main__ import sum_two',
                          number=1000)
print('sum_two_s', sum_two_s)

Результаты:

• sum_one_s 144.5597518660361
• sum_one_gen_s 84.23750544409268
• sum_one_gen_implicit_conditional_s 78.40655627311207
• sum_one_gen_swap_conditions_s 57.4693741860101
• sum_two_s 52.64653824502602

Answer 2

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

Второе решение использует генератор, который сразу выдает значения при его вычислении, не нуждаясь в списке. .