Как я могу уменьшить временную сложность этого скрипта Python?

avatar
在去中国
9 августа 2021 в 02:00
112
1
0

Вот описание проблемы:

Сумма пар

По заданному списку целых чисел и одному суммированному значению верните первые два значения (анализируйте слева) в порядке появления, которые в сумме образуют сумму.

sum_pairs([11, 3, 7, 5], 10) == [3, 7]

Мое решение:

import collections

def sum_pairs(ints, s):
    beforenums = collections.defaultdict()
    for index_before, num in enumerate(ints[1:]):
        beforenums[ints[index_before]] = index_before
        try:
            r = beforenums[s-num]
        except KeyError:
            pass
        else:
            return [s-num, num]
        
    return None

Это решение работает, и мне удалось снизить его временную сложность до O(n). есть ли способ еще больше сократить время выполнения, у меня все еще истекает время на codewars. проблема говорит, что мне будут предоставлены списки свыше 10 000 000 элементов. Полную задачу можно найти здесь: https://www.codewars.com/kata/54d81488b981293527000c8f/train/python

Источник
Kelly Bundy
9 августа 2021 в 02:15
2

docs.python.org/3/faq/design.html#how-fast-are-exceptions

ggorlen
9 августа 2021 в 02:16
0

Исключения не помогут с временной сложностью, но да, их лучше избегать. Что еще более важно, они, вероятно, хотят досрочного спасения больших тестовых случаев, но ints[1:] уже проходит через все это. Пропустить первый элемент вручную — по-прежнему O(n), но постоянный множитель уменьшается вдвое или лучше, в зависимости от тестовых случаев.

Mark
9 августа 2021 в 02:18
1

Мне любопытно, почему вы используете defaultdict?

Kelly Bundy
9 августа 2021 в 02:26
0

@ggorlen Второй из четырех «мучительно длинных тестов» состоит из 10 миллионов элементов, и победившая пара находится в самом конце. В четвертом 10 миллионов элементов и нет выигрышной пары. Таким образом, быстрый O(n) ints[1:] на самом деле в целом играет второстепенную роль по сравнению с медленным O(n) остальных.

Mark
9 августа 2021 в 02:31
0

Кажется, все было бы чище, если бы вы сделали beforenums = set(). Тогда if s - num in beforenums: будет истинным, если вы нашли пару [s - num, num], иначе beforenums.add(num). Вам не нужен enumerate.

在去中国
9 августа 2021 в 02:31
0

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

Kelly Bundy
9 августа 2021 в 12:47
0

@ggorlen Теперь провел надлежащий тест с реальными тестовыми примерами сайта, но на стабильном компьютере. Код OP занимает около 11,2 секунды. С return в качестве первого оператора в цикле (то есть ints[1:]) это занимает около 0,35 секунды.

Kelly Bundy
9 августа 2021 в 13:06
0

Да, и вместо этого замена махинаций с исключениями на if s-num in beforenums: сокращает время примерно до 3,7 секунды, так что они действительно занимают больше всего времени.

Ответы (1)

avatar
Daniel Hao
9 августа 2021 в 02:38
0

Вы можете попробовать использовать set(), чтобы ускорить его работу.

def sum_pairs(ints, s):
    cache = set()
    
    for x in ints:
        if s - x in cache:
            return [s-x, x]
        cache.add(x)

Или используйте словарь.

Kelly Bundy
9 августа 2021 в 02:39
1

Или с add = cache.add для немного большей скорости (поскольку этот вопрос касается уменьшения постоянного коэффициента).

Daniel Hao
9 августа 2021 в 02:40
0

Ницца. Скорость немного улучшена в платформе, но ненамного.