性能问题在collat​​z链上 [英] performance issue on collatz chain

问题描述

我有一个工作程序来计算给定范围内最长的collat​​z链（项目euler n°14）。我认为它工作正常，但速度很慢。我试图寻找更好的解决方案，但我只能稍微减少评估域。我做错了什么？

实现使用记忆来避免两次计算相同的结果。 Data.Map对一般性能不好？

  import Data.Map（（！），member，insert，singleton，assocs， （Map Integer Integer）
 insertSolution n syracMap 
 | b 
 $ b insertSolution :: Integer->（Map Integer Integer） - & n`member` syracMap = syracMap 
 | otherwise = let 
 next = if n`mod` 2 == 0然后n`div` 2 else 3 * n + 1 
 newMap = insertSolution next syracMap 
 solution = newMap！ next + 1 
插入n解决方案newMap 
 
 bound = 1 :: Integer 
 lower = 999999 :: Integer 
 
 test :: [Integer] 
 test = [lower，lower + 2..bound] 
 
 values = takeWhile（\（k，v） - > k 如果v> v'则（k，v）else（k'，v' v'））（1，1）的值为
 
 main = putStr $ show $ result 
  

编辑

更新了删除错误的功能。这是我的解决方案：

 模块主要
其中
 
导入Data.List 
导入Data.Ord 
 
 next_hailstone n |即使n = n`div` 2 
 |否则= 3 * n + 1 
 
 gen_next_hailstone n 
 = if nh == 1 
 then Nothing 
 else Just（nh，nh）
 where nh = next_hailstone n 
 
 hailstone n = unfoldr gen_next_hailstone n 
 
 hailstone_seqs =地图冰雹[1..1000000] 
 
 zip_hailstone = zip [1 .. 1000000] hailstone_seqs 
 
 max_hailstone = maximumBy（比较（length。snd））zip_hailstone 
 
 main = print。 fst $ max_hailstone 
  

速度相对较快。如果您想要更快的速度，请咨询Haskell Wiki （ SPOILER ALERT !!! <强>）。

I have a working program to compute the longest collatz chain in a given range (project euler n°14). I think it works correctly, but is very slow. I tried to look for a better solution, but I can only reduce slightly the evaluated domain. Am I doing something wrong?

The implementation use memoization to avoid computing the same result twice. Is Data.Map bad for general performances?

import Data.Map ((!), member, insert, singleton, assocs, Map)

insertSolution::Integer->(Map Integer Integer)->(Map Integer Integer)
insertSolution n syracMap
    | n `member` syracMap = syracMap
    |otherwise = let
        next = if n `mod` 2 == 0 then n `div` 2 else 3 * n + 1
        newMap = insertSolution next syracMap
        solution = newMap ! next + 1
        in insert n solution newMap

bound = 1::Integer
lower = 999999::Integer

test::[Integer]
test = [lower,lower+2..bound]

values = takeWhile (\(k, v) -> k < bound) $ assocs $ foldr insertSolution (singleton 1 1) test

result = foldr (\(k, v) (k', v') -> if v > v' then (k, v) else (k', v')) (1, 1) values

main = putStr $ show $ result

edit

updated function to remove bug. It is still pretty slow on my laptop.

解决方案

FWIW, here's my solution:

module Main
    where

import Data.List
import Data.Ord

next_hailstone n | even n = n `div` 2
                 | otherwise = 3*n+1

gen_next_hailstone n
    = if nh == 1
      then Nothing
      else Just (nh, nh)
          where nh = next_hailstone n

hailstone n = unfoldr gen_next_hailstone n

hailstone_seqs = map hailstone [1..1000000]

zip_hailstone = zip [1..1000000] hailstone_seqs

max_hailstone = maximumBy (comparing (length . snd)) zip_hailstone

main = print . fst $ max_hailstone

It's relatively fast. If you want more speed, consult the Haskell wiki (SPOILER ALERT!!!).

这篇关于性能问题在collat​​z链上的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！