如何优化这个勾股数实现

Question

如何优化这个勾股数实现

3

这里是Haskell代码。

import GHC.Int

triples = [(x, y, z) | z <- [(1::Int32)..],
                       x <- [(1::Int32) .. z + 1],
                       y <- [x.. z + 1],
                       x * x + y * y == z * z]

main = mapM_ print (Prelude.take 1000 triples)

具有以下配置文件

       triples +RTS -p -RTS

    total time  =       47.10 secs   (47103 ticks @ 1000 us, 1 processor)
    total alloc = 62,117,115,176 bytes  (excludes profiling overheads)

COST CENTRE MODULE    SRC                      %time %alloc

triples     Main      triples.hs:(5,1)-(8,46)  100.0  100.0

                                                                              individual      inherited
COST CENTRE  MODULE                SRC                     no.     entries  %time %alloc   %time %alloc

MAIN         MAIN                  <built-in>              118          0    0.0    0.0   100.0  100.0
 CAF         Main                  <entire-module>         235          0    0.0    0.0   100.0  100.0
  main       Main                  triples.hs:10:1-46      236          1    0.0    0.0     0.0    0.0
  triples    Main                  triples.hs:(5,1)-(8,46) 237          1  100.0  100.0   100.0  100.0
 CAF         GHC.Conc.Signal       <entire-module>         227          0    0.0    0.0     0.0    0.0
 CAF         GHC.IO.Encoding       <entire-module>         216          0    0.0    0.0     0.0    0.0
 CAF         GHC.IO.Encoding.Iconv <entire-module>         214          0    0.0    0.0     0.0    0.0
 CAF         GHC.IO.Handle.FD      <entire-module>         206          0    0.0    0.0     0.0    0.0
 CAF         GHC.IO.Handle.Text    <entire-module>         144          0    0.0    0.0     0.0    0.0
 main        Main                  triples.hs:10:1-46      238          0    0.0    0.0     0.0    0.0

尽管等效的rust代码运行速度快了一个数量级。这对我来说似乎非常奇怪。

fn triples() -> impl Iterator<Item=(i32, i32, i32)> {
    (1..).flat_map(|z| {
        (1..z + 1).flat_map(move |x| {
            (x..z + 1).filter_map(move |y| {
                if x * x + y * y == z * z {
                    Some((x, y, z))
                } else {
                    None
                }
            })
        })
    })
}

fn main() {
    for triple in triples().take(1000) {
        println!("{:?}", triple);
        // unsafe {printf("(%i, %i, %i)\n".as_ptr() as *const i8, x, y, z)};
    }
}

结果如下：

[I] ~/c/pythagoras (master|✚1…) $ time ./range > /dev/null
0.16user 0.00system 0:00.16elapsed 100%CPU (0avgtext+0avgdata 2248maxresident)k
0inputs+0outputs (0major+124minor)pagefaults 0swaps
[I] ~/c/pythagoras (master|✚1…) $ time ./triples > /dev/null
2.39user 0.00system 0:02.39elapsed 99%CPU (0avgtext+0avgdata 4736maxresident)k
0inputs+0outputs (0major+473minor)pagefaults 0swaps

这两个结果都使用了 -O3 标志。

在保留惯用的 Haskell 代码的同时，是否有可能优化掉分配？也许某些融合库或其他东西可以做到这一点？

EDIT1. 好的，使用 Int 而不是 Int32 或 Int64 可以使代码更快，这很好。然而，使用 fflvm 仍然比 Rust 慢两倍，并且根据分析，它仍然大部分时间花费在分配上。是什么阻止 Haskell 例如重用三元组而不仅仅分配一次？

- user1685095

https://stackoverflow.com/tags/haskell/info - jberryman

你的第三个生成器应该从x+1开始，我认为？在勾股数中，x和y应始终是不同的数字。 - Yawar

2个回答

2

也许需要改变你的实现方式？

triples = [(m^2-n^2,2*m*n,m^2+n^2) | m<-[2..], n<-[1..(m-1)]]

- karakfa

我不确定这是否生成相同的列表（直到排序）。它似乎是经验性的，但至少需要一个参考（虽然很酷！） - luqui

1

这里有一个参考链接：http://mathworld.wolfram.com/PythagoreanTriple.html，该公式可能已有两千年历史。通过对`n，m`施加相对质数和不同的奇偶条件，可以得到原始三元组。OP还生成了原始三元组的倍数，所以我没有去烦恼。 - karakfa

重点是使用相同的实现方式来比较所有语言的性能。 - user1685095

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- András Kovács · Accepted Answer

您的代码存在两个问题：

为了提高性能，应该不带 profiling，使用优化编译。Profiling 会增加显著的开销。在我的系统上，使用 ghc -prof 的运行时间超过40秒，与您的时间相似。而不带 -prof 的 ghc -O2 只需要4.2秒。
在64位系统上使用 Int32。这样做是错误的，因为非本机大小的 Int 操作会编译成缓慢的 out-of-line primops。如果将 Int32 更改为 Int，运行时间将变成0.44秒。如果额外使用 LLVM 代码后端的 -fllvm，则可将其缩短到 0.2 秒。