Python 3: оптимизация проекта Эйлера, задача № 14 - PullRequest
Новая
       50

Python 3: оптимизация проекта Эйлера, задача № 14

0 голосов
/ 10 июня 2019

Я пытаюсь решить проблему Hackerrank Project Euler # 14 (самая длинная последовательность Коллатца) с использованием Python 3. Ниже приведена моя реализация. 

cache_limit = 5000001
lookup = [0] * cache_limit
lookup[1] = 1


def collatz(num):
    if num == 1:
        return 1
    elif num % 2 == 0:
        return num >> 1
    else:
        return (3 * num) + 1


def compute(start):
    global cache_limit
    global lookup
    cur = start
    count = 1

    while cur > 1:
        count += 1
        if cur < cache_limit:
            retrieved_count = lookup[cur]
            if retrieved_count > 0:
                count = count + retrieved_count - 2
                break
            else:
                cur = collatz(cur)
        else:
            cur = collatz(cur)

    if start < cache_limit:
        lookup[start] = count

    return count


def main(tc):
    test_cases = [int(input()) for _ in range(tc)]
    bound = max(test_cases)
    results = [0] * (bound + 1)

    start = 1
    maxCount = 1
    for i in range(1, bound + 1):
        count = compute(i)
        if count >= maxCount:
            maxCount = count
            start = i
        results[i] = start

    for tc in test_cases:
        print(results[tc])


if __name__ == "__main__":
    tc = int(input())
    main(tc)

Есть 12 тестовых случаев,Вышеприведенная реализация проходит до контрольного примера № 8, но не проходит для контрольных примеров № 9 - № 12 по следующей причине: 

Terminated due to timeout

Я застрял с этим на некоторое время.Не уверен, что еще можно сделать здесь.

Что еще можно оптимизировать здесь, чтобы я перестал получать тайм-аут?

Любая помощь будет оценена по достоинству:)

Примечание: Используя вышеописанную реализацию, я могу решить актуальную задачу Project Euler # 14.Это дает тайм-аут только для этих 4 тестовых случаев в хакерранке.

Ответы [ 2 ]

0 голосов
/ 24 июня 2019

Да, есть вещи, которые вы можете сделать со своим кодом, чтобы оптимизировать его. Но я думаю, что более важно, есть математическое наблюдение, которое вы должны рассмотреть, которое лежит в основе проблемы : 

whenever n is odd, then 3 * n + 1 is always even.

Учитывая это, всегда можно разделить (3 * n + 1) на 2. И это сэкономит немало времени ...

0 голосов
/ 10 июня 2019

Вот моя реализация (для вопроса специально на сайте Project Euler): 

num = 1
limit = int(input())
seq_list = []
while num < limit:
    sequence_num = 0
    n = num
    if n == 1:
        sequence_num = 1
    else:
        while n != 1:
            if n % 2 == 0:
                n = n / 2
                sequence_num += 1
            else:
                n = 3 * n + 1
                sequence_num += 1

        sequence_num += 1
    seq_list.append(sequence_num)
    num += 1

k = seq_list.index(max(seq_list))
print(k + 1)
...