Как оптимизировать алгоритм (Euler 14)?

Question

[Umid]

Задача.

Есть ли возможность оптимизировать алгоритм?

def euler14(limit):
	kNum = limit - 1
	maxLen = 0

	def kollats(number):
		kolNums = [number]
		while True:
			n = kolNums[len(kolNums) - 1]
			if n == 1:
				break

			if n % 2:
				n = 3*n + 1
			else:
				n = int(n / 2)
			kolNums.append(n)
		return kolNums

	for i in range(1, limit):
		kol = kollats( kNum )
		
		if len(kol) > maxLen: 
			maxLen = len(kol)
		kNum -= 1
	print(maxLen)
euler14(1000000)

Время отработки кода: 94 секунды.

Comments

[jcmvbkbc]

У меня есть решение этой задачки на C, выполняется за 0.1с.

[sts]

jcmvbkbc: C это читерство по сравнению с Питоном и другими высокоуровневыми яп=)

[javedimka]

Как насчёт просто погуглить?
code.jasonbhill.com/c/project-euler-problem-14

[jcmvbkbc]

stunoff: если ты хочешь сказать, что наблюдаемый 1000-кратный разрыв в производительности обусловлен исключительно различием языков, то я сомневаюсь в этом. Но ок, читерство так читерство.

[sts]

jcmvbkbc: я хочу сказать что скомпилированный и норм написанный код на С будет один фиг быстрее чем код интерпритированный на питоне. И да, разрыв в 1к это норм, бывает и больше

[longclaps]

stunoff: ну-ну)

Answer 1

[longclaps]

Почитай про тренарный оператор и целочисленное деление.

def euler14(limit):
    cache, kolNums = {1: 1}, []
    for n in range(2, limit):
        while n not in cache:
            kolNums.append(n)
            n = 3 * n + 1 if n % 2 else n // 2
        res = cache[n]
        while kolNums:
            res += 1
            cache[kolNums.pop()] = res
    print(*max(cache.items(), key=lambda e: e[1]))

Comments

[Umid]

Спасибо за ответ!
А что означает вот эта строка: while kolNums: ?

[javedimka]

Umid: выполнять цикл до тех пор пока в kolNums есть значения

[Umid]

javedimka: Т.е., если в цикле 5 элементов, то будет 5 итераций?

[javedimka]

Umid: По поводу реализации и особенностей работы функции лучше у автора спрашивать, у меня 9 классов образования. ¯\_(ツ)_/¯

[longclaps]

javedimka: Не скромничай, тебе не идёт )
Umid: Когда вместо вопросов ты начнешь пробовать, кое-что изменится )

l = [1, 2, 3]
while l:
    print(l.pop())

pythonz.net/references/named/object.__bool__

[Umid]

longclaps: Понял, спасибо вам большое!

[Umid]

И всё же, затрудняюсь понять ваш код. Не могли бы вы сопроводить их комментариями, пожалуйста.

[longclaps]

Я не вижу смысла комментировать построчно.
Вот код, эквивалентый последней строке:

best = mx = 1  # посл. Коллатца, начнающаяся с 1, имеет длину 1
    for key, value in cache.items():
        if mx < value:
            best, mx = key, value
    print(best, mx)

С остальным разбрайся сам, ты же штурмуешь EulerProject!
Совет: повставляй в код принтов вроде

flag = n == limit - 1
.....
if flag:
    print("строка такая-то", <что тебя интересует>)
.....
if flag:
    print("другая строка", <еще чего-то>)

выставь limit=3, посмотри, что будет.
выставь limit=4, посмотри, что будет.
....