Нашли или выдавили из себя код, который нельзя назвать нормальным, на который без улыбки не взглянешь? Не торопитесь его удалять или рефакторить, — запостите его на говнокод.ру, посмеёмся вместе!
−101
maxi=140000
plist=set(primes(maxi))
dlist={}
def dp(n):
if dlist.has_key(n):
return dlist[n]
else:
facts= len([k for k in plist if n%k==0])
dlist[n]=facts
return facts
print [k for k in range (1,maxi) if dp(k)==4 and dp(k+1)==4 and dp(k+2)==4 and dp(k+3)==4]
http://projecteuler.net/problem=47
http://projecteuler.net/thread=47;page=8
Этот товарищ растянул на 11 секунд то, что даже тупым брутфорсом решается за <1 секунду.
Запостил: 
TheHamstertamer,
12 Июня 2012
Follow us!
11тый пост сверху
> for (int i = 2 ; i <= Math.sqrt(number) ; i++)
Ява умеет оптимизировать такие штуки? Или это будет гонять sqrt на каждой итерации?
if (prime*prime > candidate) же!
Печальный код :(
Но это только на первый.
Если всмотреться - делается full-scan списка всех простых чисел.
([k for k in plist if n%k==0])
Оно вроде и выглядит компактно, логично, красиво, но внутри пиздец.
ЗЫ. А в пухтоне вот так можно писать:
return ( dlist[n]= len([k for k in plist if n%k==0]) )
Да сколько их там? n/log(n) вроде, да, тогда многовато.
> ЗЫ. А в пухтоне вот так можно писать:
И чё, для кешированного значения оно сразу вернёт значение?
Вроде присваивания внутри выражений там недопустимы. Не уверен, т.к. не знаю питон, и имею к нему индивидуальную непереносимость.
Такая же херня.
Это я типа так спросил. Можно ли.
Решение в лоб на хаскеле 0.21с. А если дописать primes :: [Int] то 0.08с :)
А автор, конечно жжот, сканируя ВЕСЬ список простых чисел :)
Haskell - 6
Python - ~11
P.S. А че не в одну строку все ? )
Показать свою джедайскую силу.
В путхоне самая длинная
print [k for k in range (1,maxi) if dp(k)==4 and dp(k+1)==4 and dp(k+2)==4 and dp(k+3)==4]
И то её можно написать короче.
Если уж меряться длиной кода - то символами а не строками.
Haskell - 516
Python - 298
В таком случае все же короче.
Что за отвратная факторизация по p <- [2..n], isPrime p, выше же у вас описан primes... Да еще и фулл-скан как в оригинальном посте... Или это просто попытка переписать код дословно?
Сортоф.
Он медленный от того, что я на своей машине использовал следующий код:
А в примере для краткости заменил его на код выше.
Такие дела.
Хотя вот вопрос: в последней строке считается map (length . nub . factorize) [x, y, z, c], а перед этим пачка let'ов.
1) Почему бы не убрать let и не сделать [x, x+1, x+2, x+3]?
2) Получается в 4 раза больше факторизаций, чем в моем варианте?
2) Да вроде, я сильно оптимизацией не заморачевался, подумал, что если будет тупить, то перепишу, но оно и так выполняется за <1 сек.
Говно.
У борланда лучше норм:
http://ideone.com/3bCAe
P.S. У этого кода на хаскеле есть плюс - из-за работы с бесконечным списком не нужно подбирать верхнюю планку для простых чисел (140000 в оригинальном решении).
Во-вторых, генератор-то линеен, если нужен кэш, то не проще ли functools.lru_cache?
И потом, что именно заворачивать в lru_cache? primes()? Так оно аргументов не просит, кэш не сработает. Код целиком как функцию? Не ну можно конечно, но большой ли будет выигрыш?
Можно написать свой простенький вариант, вряд ли получится длинее, чем генератор + Set.
Но maxprime - явный хак: если не знать порядок, то получится либо оверхэд, либо усложнение (проверять не отстал ли он и подтягивать при необходимости).
Вообще есть более интересный вариант:
Для тех кто не знает питона: последний else относится к while, и сработает если произойдёт нормальный выход из цикла по условию, а не по break/return/exception.
Т.е. мы точно знаем что в кэше числа нет, и не трогаем его, а вместо этого проверяем свежеполученные числа. При этом кэш все равно обновляется.
Правда, может получиться дурацкая ситуация когда промах кэша будет отрабатывать быстрее чем попадание.
Без такой конструкции пришлось бы вводить флаг "элемент найден". Пустячок, а приятно, и никто пользоваться не заставляет.
Такой else есть у циклов for, while, и у блока try. В последнем случае он выполнится только если при выполнении try НЕ произошло исключения. Привести пример для этого я затрудняюсь, правда.
"The use of the else clause is better than adding additional code to the try clause because it avoids accidentally catching an exception that wasn’t raised by the code being protected by the try ... except statement."
Т.е. если в readlines у нас вылетит ошибка чтения - мы не выдадим кривое сообщение "не могу открыть файл".