Haskell:List v.Array,性能差异

Question

来自Haskell n00b的另一个问题.

我正在比较Project Euler网站上用于解决问题#14的各种方法的效率.特别是,我希望能够更好地理解驱动评估时间差异的因素,以解决问题的四种(略微)不同方法.

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

首先,快速概述问题#14.它与"Collat​​z数字"有关(即,与我上一篇文章相同的编程练习,探讨了Haskell的不同方面).给定整数的Collat​​z数等于该整数的Collat​​z序列的长度.整数的Collat​​z序列计算如下:序列中的第一个数字("n0")是整数本身; 如果n0是偶数,则序列中的下一个数字("n1")等于n/2; 如果n0是奇数,那么n1等于3*n0 + 1.我们继续递归地扩展序列,直到我们到达1,此时序列结束.例如,5的折叠序列是:{5,16,8,4,2,1}(因为16 = 3*5 + 1,8 = 16/2,4 = 8/2,......).

问题14要求我们找到具有最大Collat​​z数的1,000,000以下的整数.为此,我们可以考虑一个函数"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"函数的四个可能版本:array/partial,list/partial,array/complete和list/complete:

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)访问时间)因此我期望"array"的"数组"实现比其他条件不变的"列表"实施更快.此外,我预计'部分'算法比'完整'算法(ceteris paribus)更快,因为它需要执行更少的操作才能构建Collat​​z数字的数据集.

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

事实上,'阵列/部分'版本是"collat​​z"的最快版本(以良好的差距).但是,我觉得有点违反直觉,'list/complete'不是最慢的版本.这个荣誉归于'list/partial',比'list/complete'慢20倍!

我的问题:'list/partial'和'list/complete'之间的评估时间差异(与'array/partial'和'array/complete'之间的评估时间相比)完全是由于列表之间访问效率的差异和Haskell中的数组？或者我没有进行"对照实验"(即,还有其他因素在起作用)吗？

Answer 1

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

如果考虑到性能，请尽量避免对列表建立索引，尤其是长列表。索引实际上是一种遍历（如您所知）。“列表/部分”正在索引/遍历很多。列表/完整不是。因此，Array/complete 和 List/complete 之间的差异可以忽略不计，而“list/partial”与其他之间的差异则很大。