arrays - Haskell:List v. Array，性能差异

Question

Haskell n00b 的另一个问题。

我正在比较 Project Euler 网站上用于解决问题 #14 的各种方法的效率。特别是，我希望更好地了解导致四种(略有)不同解决问题方法的评估时间差异的因素。

(问题 #14 和各种方法的描述如下。)

首先，快速概述问题#14。它与“Collat​​z numbers”有关(即，与我之前探索 Haskell 不同方面的帖子相同的编程练习)。给定整数的 Collat​​z 数等于该整数的 Collat​​z 序列的长度。一个整数的 Collat​​z 序列计算如下:序列中的第一个数字(“n0”)是该整数本身；如果 n0 是偶数，则序列中的下一个数字(“n1”)等于 n/2；如果 n0 是奇数，则 n1 等于 3 * n0 + 1。我们继续递归扩展序列，直到到达 1，此时序列完成。例如，5 的collat​​z 序列是:{5, 16, 8, 4, 2, 1}(因为16 = 3 * 5 + 1, 8 = 16/2, 4 = 8/2,...)。

问题 14 要求我们找出 1,000,000 以下的整数，它具有最大的 Collat​​z 数。为此，我们可以考虑一个函数“collat​​z”，当将整数“n”作为参数传递时，它返回 n 以下具有最大 Collat​​z 数的整数。换句话说，p 1000000 为我们提供了问题 #14 的答案。

出于本练习的目的(即理解评估时间的差异)，我们可以考虑 Haskell 版本的“collat​​z”，它们在两个维度上有所不同:

(1) 实现:我们将 Collat​​z 数的数据集(将为所有整数 1..n 生成)存储为列表还是数组？我称之为“实现”维度，即函数的实现要么是“列表”，要么是“数组”。

(2) 算法:我们是否通过扩展 Collat​​z 序列直到它完成(即，直到我们达到 1)来计算任何给定整数 n 的 Collat​​z 数？或者我们是否只扩展序列直到我们达到一个小于 n 的数 k(此时我们可以简单地使用我们已经计算过的 k 的 Collat​​z 数)？我称之为“算法”维度，即函数的算法要么是“完整的”(计算每个整数的 Collat​​z 数)，要么是“部分的”。后者显然需要较少的操作。

以下是“collat​​z”函数的四种可能版本:数组/部分、列表/部分、数组/完整和列表/完整:

import Data.Array ( (!) , listArray , assocs )
import Data.Ord ( comparing )
import Data.List ( maximumBy )

--array implementation; partial algorithm (FEWEST OPERATIONS)
collatzAP x = maximumBy (comparing snd) $ assocs a where
    a = listArray (0,x) (0:1:[c n n | n <- [2..x]])
    c n i = let z = if even i then div i 2 else 3*i+1
      in if i < n then a ! i else 1 + c n z

--list implementation; partial algorithm
collatzLP x = maximum a where   
    a = zip (0:1:[c n n | n <- [2..x]]) [0..x]
    c n i = let z = if even i then div i 2 else 3*i+1
      in if i < n then fst (a!!i) else 1 + c n z

--array implementation, complete algorithm
collatzAC x = maximumBy (comparing snd) $ assocs a where
    a = listArray (0,x) (0:1:[c n n | n <- [2..x]])
    c n i = let z = if even i then div i 2 else 3*i+1
     in if i == 1 then 1 else 1 + c n z     

--list implementation, complete algorithm (MOST OPERATIONS)
collatzLC x = maximum a where   
    a = zip (0:1:[c n n | n <- [2..x]]) [0..x]
    c n i = let z = if even i then div i 2 else 3*i+1
      in if i == 1 then 1 else 1 + c n z

关于评估速度:我知道数组的访问速度比列表快得多(即，对于给定的索引 n，O(1) 与 O(n) 访问时间)所以我期望“collat​​z”的“数组”实现比“列表”实现更快，其他条件不变。此外，我希望“部分”算法比“完整”算法(其他条件不变)更快，因为它需要执行更少的操作来构建 Collat​​z 数字的数据集。

在不同大小的输入中测试我们的四个函数，我们观察到以下评估时间(下面的评论):



确实如此，“数组/部分”版本是“collat​​z”的最快版本(优势很大)。但是，我发现“列表/完成”并不是最慢的版本，这有点违反直觉。这一荣誉归于“list/partial”，它比“list/complete”慢 20 倍以上!

我的问题:'list/partial' 和 'list/complete' 之间的评估时间差异(与 'array/partial' 和 'array/complete' 之间的相比)是否完全是由于列表和Haskell 中的数组？或者我不是在进行“受控实验”(即，是否还有其他因素在起作用)？

Answer 1

我不明白有关使用列表的两种算法的相对性能的问题与数组有什么关系……但这是我的看法:

如果性能有任何问题，请尽量避免索引列表，尤其是长列表。索引实际上是一种遍历(如您所知)。 “列表/部分”正在索引/遍历很多。列表/完整不是。因此 Array/complete 和 List/complete 之间的差异可以忽略不计，而“list/partial”和其余部分之间的差异是巨大的。