Необъяснимо невероятное выступление с пифагорейскими тройками в Хаскеле

Question

Допустим, у нас есть эта простая функция на Haskell, которая генерирует пифагорейские тройки:

pytha :: [(Int, Int, Int)]
pytha = [(x, y, z)
        | z <- [0..]
        , x <- [1..z]
        , y <- [x..z]
        , x * x + y * y == z * z
        ]

, и мы хотели бы оценить, сколько времени потребуется, чтобы произвести, скажем, первые 100 тройок.Таким образом (используя библиотеку criterion и предполагая import Criterion.Main) у нас есть этот тест:

main :: IO ()
main = do
  countStr <- readFile "count.txt"
  defaultMain [ bgroup "pytha" [ bench countStr $ nf (`take` pytha) (read countStr) ] ]

, где мы даже читаем count из файла, чтобы убедиться, что ghc не пытается оценить pytha во время компиляции!

Выполнение echo 100 > count.txt, компиляция теста с -O2 и запуск на моей машине (процессор Sandy Bridge 4,0 ГГц) показывает некоторые интересные цифры:

time                 967.4 ns   (957.6 ns .. 979.3 ns)
                     0.999 R²   (0.998 R² .. 0.999 R²)
mean                 979.6 ns   (967.9 ns .. 995.6 ns)
std dev              45.34 ns   (33.96 ns .. 60.29 ns)

Слегка изменив эту программу, чтобы показать, сколько троек было рассмотрено в целом (сначала сгенерировав все тройки, сжав список с помощью [0..], а затем отфильтровав все непифифагорейские тройки и просмотрев индексы полученных), видно, что почти 900000Рассматривалось трижды.

Все это, естественно, поднимает вопрос: как приведенному выше коду удается достичь 1000 триплетов / нс на одном ядре довольно стандартного процессора?Или просто мой тест неверен?

Answer 1

Вам нужно использовать функцию, а не значение, которое будет запомнено.

pytha :: Int -> [(Int, Int, Int)]
pytha z_max =
    [ (x, y, z)
    | z <- [0..z_max]
    , x <- [1..z]
    , y <- [x..z]
    , x * x + y * y == z * z
    ]

GHC не станет достаточно умным, чтобы перевести это в takeWhile из списка констант, поэтомудолжен дать значимый ориентир.Просто убедитесь, что Criterion отвечает за передачу z_max, которую вы можете разумно установить на maxBound :: Int или что-то подобное.

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