Python-сообщество

Проверяю своё предположение:
По тому же алгоритму просто добавил при получении более длинной цепочки print.
Список значений - 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171, 10971, 13255, 17647, 23529, 26623, 34239, 35655, 52527, 77031, 106239, 142587, 156159, 216367, 230631, 410011, 511935, 626331, 837799
Хотя конечно не факт что дальше не попадётся чётное число с большей цепочкой. Но предположение оправдалось.
ред. Если сохранять предыдущие значения, скорость вырастает в 10 раз.

Отредактировано (Окт. 2, 2009 17:14:42)

Можно синтаксическое отступление? :) Я ещё не особо спец в пайтоне, какова структура вот этой конструкции?
c = len()
в частности не совсем понимаю x перед for, и саму конструкцию x for x in gen(i) внутри описания списка 0_о
не нагуглил ничего про это (

Ищи “генератор списков”.

Всё, по “генератор списков” нагуглил ) спасибо :)

В итоге сделал вот так:

allchains = {}
def calclen(start):
 global allchains
 n = start
 chainlen = 1
 chain = []
 while (n > 1):
  if (n in allchains):
   chainlen = allchains[n]
   break
  chain.append(n)
  n = (n % 2) and (3*n + 1) or (n/2)
 for i in range(len(chain)):
  n = chain[i]
  allchains[n] = chainlen + len(chain) - i
 return chainlen + len(chain)
map(calclen, range(1, 1000000))
maxlen = 0
maxstart = 0
for x in allchains.iteritems():
 if (x[1] > maxlen):
  maxstart, maxlen = x
print maxstart, maxlen

Отредактировано (Окт. 3, 2009 02:57:17)

Я его не считаю. Просто не нужно.
Когда “тормозит” - запускаю cProfile. После смотрю результат в runsnakerun и начинаю разбираться, где теряю время.
Мой подход рассчитан на задачи из production и тормоза в нем - не беда “просто алгоритма”.
Приходится принимать во внимание то, что система - большая. Каждая и подсистем - тоже не маленькая.
И настоящие проблемы возникают тогда, когда этот чертов код в надцатый раз упорно пытается спросить у базы данных штуку, которую он уже получил - это был пример.
Оптимизация по архитектуре, а не по алгоритмам - а если уж структурно система плоха - то надо срочно ее менять.
Но помнить алгоритмы нужно - чтобы просто-напросто заметить, что у нас теперь получилась квадратичная сложность (хорошо если так) вместо логарифмической.

Совсем уж оффтоп - расскажу сказку:
Работал я когда-то на одной фирме. Микропроцессоры программировал.
Требования по скорости - запредельные. Мой коллега - электронщик (умница неимоверная, постоянно изобретал элегантные решения, позволяющие переложить всю работу на проц и сильно удешевить схему) - не всегда понимал, почему нельзя считать производительность как чистые мегагерцы/тактовую частоту. И что нужно еще время, чтобы держать пять источников прерываний из которых три - затратные.
Суть не в том, хотя я очень люблю задачи на оптимизацию: перелопатить код, найти узкие места и поменять архитектуру.

Была у нас штучка, которая мне не нравилась. Ассембер показывал, что несколько простых арифметических операций превращались в очень накладную вещь.
Поменял этот код на правильный с моей точки зрения.
Запускаю заново прошитый девайс - он работает!. Отлично!
Для измерения производительности выводил сигнал на свободную лапку. Т.е. если там ноль - “считалка” не работает. Если единица - мы как раз обрабатываем этот самый проблемный код.
Тыкаю лучом осцилографа в нужный вывод - и ничего не вижу. Устройство работает, а ожидаемого всплеска сигнала нет. Перепроверяю все - и опять ничего. Так раз пять. Наконец догадался переключить осцилограф на другой режим. Поймал мой всплеск.
По результатам измерений считалка стала делать свою работу в 60 раз быстрее.

Осознал, порадовался и понял - еще раз такое в естественных условиях мне не повторить.
Это был очень редкий и крайний случай.

Сейчас сорок процентов - это очень хорошо, почти предел. Иначе - переписывать сильно много нужно.

Sapphire
PS: а как вы подсчитываете время выполнения? не нашёл в man python ничего про это… Считал по часам))

startTime = datetime.datetime.now()
...код...
print datetime.datetime.now() - startTime

Griffon
Первое - искомое число находится между девятками. То есть искомое число больше либо равно 900 009. Очень сильно сокращает количество итераций ибо используются пары чисел (x,y) с соответствующими окончаниями (1,9) (3,3) (7,7) (9,1)

Griffon
Тут всё просто. (X - A) * (Y - B) всегда меньше чем (X - C) * Y, где С < A.

# -*- coding: utf-8 -*-

"""Problem 14
   The following iterative sequence is defined for the set of positive integers:

      n = n/2 (n is even)
      n = 3n + 1 (n is odd)

   Using the rule above and starting with 13, we generate the following sequence:
      13  40  20  10  5  16  8  4  2  1

   It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms.
   Although it has not been proved yet (Collatz Problem), it is thought that all starting
   numbers finish at 1.

   Which starting number, under one million, produces the longest chain?

   NOTE: Once the chain starts the terms are allowed to go above one million."""

m = 0
mc = 0
for i in xrange(1000000):
    n = i
    c = 0
    while n > 1:
        c += 1
        if n % 2 == 0:
            n = n/2
            if n == 1:
                break
        else:
            n = 3*n + 1
    if c > mc:
        mc, m = c, i
print m

Отредактировано (Окт. 3, 2009 22:01:33)

По окончаниям имеется ввиду: например, число Х заканчивается на 1, а число Y на 9, что даёт пару (1,9). Только четыре пары при умножении дадут число которое заканчивается на 9. И соответственно число итераций любого алгоритма сокращается вдвое.
И кстати даже если искомое число ниже, ничто нам не мешает для всех чисел которые дают сумму больше 900009, это правило применять. А для чисел которые дают сумму больше 800008, но меньше 900009 проверять только пары которые дают в сумме 8. И так до нуля.

ZZZ
>>Griffon написал:
>>Тут всё просто. (X - A) * (Y - B) всегда меньше чем (X - C) * Y, где С < A.

Хм… У меня это тоже проверяется.

def do1(l):
	def full(x):
		x = str(x)
		return int(x+x[::-1])
	max1 = int("9" * l)
	first_max = int("9" * (l-1) + "7")
	min1 = int("1" + "0" * (l-1))
	c = 0
	for i in range(first_max, min1, -1):
		for j in range(max1, min1, -1):
			f = full(i)
			c += 1
			test = f / j
			if test > j:
				break
			if test.is_integer():
				print(f, j, int(test), c)
				return True

>> do(3)
906609 993 913 2251

def do(start, end=0):
	values = [start, start - 1]
	max_list = [start**2, (start - 1)**2]
	offsets = [0, 0]
	i = 0
	max_len = start - end
	test = values[0]
	c = 0
	while i < max_len and test != 0:
                c += 1
                x = values[i]
                y = x - offsets[i]
                test = x * y
                max_list[i] = test
                max_val = max(max_list)
                if test < max_val:
                        max_val_index = max_list.index(max_val)
                        if max_val_index == len(max_list) - 1:
                                values += [values[-1] - 1]
                                max_list += [values[-1]**2]
                                offsets += [0]
                        i = max_val_index
                        continue
                offsets[i] += 1

                test = str(test)
                if test == test[::-1]:
                        print(test, x, y, c)
                        return True

>> do(999)
906609 993 913 4454

Отредактировано (Окт. 5, 2009 21:58:34)