Debugging неэффективного проект Эйлер 58

Question

Я пытаюсь решить проблему Проекта Эйлера 58.

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

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

Функция isPrime просто берет Int и возвращает, если это просто.

Проблема и мои текущие решения приведены ниже.

{-| 
- Problem 58 
- 
- Starting with 1 and spiralling anticlockwise in the following way, a square 
- spiral with side length 7 is formed. 
- 
- 37 36 35 34 33 32 31 
- 38 17 16 15 14 13 30 
- 39 18 5 4 3 12 29 
- 40 19 6 1 2 11 28 
- 41 20 7 8 9 10 27 
- 42 21 22 23 24 25 26 
- 43 44 45 46 47 48 49 
- 
- It is interesting to note that the odd squares lie along the bottom right 
- diagonal, but what is more interesting is that 8 out of the 13 numbers lying 
- along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%. 
- 
- If one complete new layer is wrapped around the spiral above, a square spiral 
- with side length 9 will be formed. If this process is continued, what is the 
- side length of the square spiral for which the ratio of primes along both 
- diagonals first falls below 10%? 
-} 

import Data.List (genericLength) 
import Data.List.Split (splitPlaces) 
import EulerFunctions (isPrime) 

-- Each ring is another concentric circle in the spiral. 
-- The first 3 are [1], [2..9], and [10..25] 
type Ring = [Int] 

-- Returns an infinite list of rings. 
rings :: [Ring] 
rings = [1] : splitPlaces [8,16..] [2..] 

-- Given a ring, returns the numbers on its corners. 
corners  :: Ring -> [Int] 
corners [1] = [1] 
corners ring = let end = last ring 
        diff = (length ring) `div` 4 
       in map (\n -> end - n * diff) [0..3] 

diagPrimes  = scanl1 (+) $ map (genericLength . filter isPrime . corners) rings 
diagLengths  = [1,5..] 
diagPrimeRatios = zipWith (/) diagPrimes diagLengths 

p58 = fst . head . filter ((< 0.1) . snd) $ [1,3..] `zip` tail diagPrimeRatios 

Answer 1

Компиляция

Как всегда на переполнение стека, я чувствую, что мне нужно, чтобы убедиться, что люди 1. компиляции своего кода вместо использования GHCI 2. с помощью оптимизации. Подумайте, что Haskell больше похож на C в том, что вы должны скомпилировать двоичный файл и использовать -O2, а не как Python, где вы просто предполагаете, что интерпретируется как a-ok. Короче говоря:

ghc -O2 -fllvm so.hs 

Если вы сделаете это, вы увидите, ваш алгоритм делает оканчиваются в умеренном количестве времени - пару минут и низкий уровень использования кучи.

Алгоритм Проблемы

Какого черта это займет пару минут? Давайте посмотрим!

1. corners строит список объектов, а затем принимает углы. Зачем? Вы знаете длину стороны при каждой новой упаковке, просто получите четыре цифры! [1] затем [3,5,7,9], [13,17,21,25]. То есть, добавьте 2,2,2,2 .. 4,4,4,4 ... 6,6,6,6 ... replicate 4 (sidelength-1) каждый раз.

2. [удален] Я думал, что вы перепрофилировали простые числа.

3. Небольшая точка и скрыта под вашим отсутствием сигнатур типа, но ваша арифметика diagLengths - это все двойники - используйте целочисленную арифметику, а затем отбросьте ее на ох, поэтому бессмысленную разницу в производительности diagLength = map fromIntegral ([1,5..] :: [Int]).

EDIT: Поэтому я думал, что основной проблемой были простые числа, в которые я был неправ. Во всяком случае, идиоматические решения, которые я пробовал, дают результаты в ~ 0,3 секунды, так что это выполнимо. Я думаю, что создание и перемещение этих довольно больших списков для corners является скорее убийцей, поскольку это требует выделения ресурсов и доступа к памяти.

Answer 2

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

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

[3,5,7,9],[13,17,21,25],[31,37,43,49] 

Обратите внимание на различиях между последовательными элементами в каждом списке являются постоянными, а постоянная разница в список увеличивается в соответствии с [2,4,6..], и разница между последним углом одной стороны и первой из следующей стороны вдвое превышает разницу между последовательными значениями первого списка. Эта проза соответствует точно следующему коду:

{-# LANGUAGE BangPatterns #-} 

corners :: [[Integer]] 
corners = [1] : go 3 2 where 
    go i0 !d = let l = i0+3*d 
       d' = d+2 
      in [i0,i0+d,i0+2*d,l] : go (l+d') d' 

Обратите внимание, что первый угол является особым случаем. Также обратите внимание на использование шаблонов ударов - важно, чтобы такие функции были строгими (углы никогда не рассматривают d, поэтому их необходимо принудительно вручную). Это важное соображение эффективности.

Далее рассмотрим функцию, которая вычисляет отношение простых чисел в одном списке. Поскольку она должна учитывать старое соотношение, он должен также принимать старые отношения в качестве параметра:

import Data.List (foldl') 
import Math.NumberTheory.Primes.Testing (isPrime) 

primeRatio :: (Int, Int) -> [Integer] -> (Int, Int) 
primeRatio pR nums = foldl' (\(!p,!t) n -> (p + fromEnum (isPrime n), 1+t)) pR nums 

fromEnum преобразует False в 0 и True к 1 непосредственно (вместо if) - в противном случае эта функция очень проста. Заметьте, опять же, шаблоны взлома и использование foldl' - оба важны для производительности здесь. Кроме того, тест primality - это высокоэффективный Baille PSW, реализованный в отличном пакете арифмои, - то, что тест прочности, который вы используете, значительно повлияет на вашу производительность.

Теперь мы можем, наконец, написать быстрый цикл, который потребляет каждый список углового в линейное время:

go !rIndex (cs:css) tgt pR 
    | tgt pR' = 2*rIndex+1 
    | otherwise = go (rIndex+1) css tgt pR' 
     where pR' = primeRatio pR cs 

Обратите внимание, что окончательный ответ (число строк) вычисляются непосредственно из индекса (расстояние от центра к внешней строке). Это всегда должно быть нечетное число, что имеет место для выражения 2*x+1. Проверка на завершение просто кодируется как параметр для этой функции - нам не нужно решать, что это такое. Если проверка завершения не удалась, то все, что мы делаем, это обновление текущего отношения со следующим элементом в списке углов! Как просто.

У нас есть одно окончательное соображение: соотношение составляет менее 10% для первых нескольких строк. Таким образом, мы должны относиться к тем, специально:

euler58 :: Integer 
euler58 = 
    let prefix = 4 -- Number of cases to handle specially 

     -- Special and non special cases 
     (first,rest) = splitAt prefix corners 

     -- Initial part where the ratio is allowed to fall below the targe 
     initVals = foldl' primeRatio (0,0) first 

     go !rIndex (cs:css) tgt pR 
     | tgt pR' = 2*rIndex+1 
     | otherwise = go (rIndex+1) css tgt pR' 
      where pR' = primeRatio pR cs 

    in go prefix rest (\(nPrimes, nTotal) -> (nPrimes%nTotal) < (1%10)) initVals 

Это вычисляет ответ (26241) менее чем за полсекунды на моей машине даже при компиляции без оптимизации. Я даже не стал пытаться оптимизировать его дальше - возможно, его можно было бы ускорить, но он уже «мгновен», поэтому, похоже, это не так.