在haskell中有效地计算列表中某个元素的比例

Question

这需要长长的列表，我想这是我长期使用的问题。

ratioOfPrimes :: [Int] -> Double 
ratioOfPrimes xs = fromIntegral (length (filter isPrime xs))/ fromIntegral(length xs) 

有没有更高效的方法呢？

Answer 1

length的双重使用不是这里的主要问题。您的实施中的多次遍历产生了一个常数因子，并且使用双重length和filter可以获得O(3n)的平均复杂度。由于流融合，它甚至是O(2n)，正如Impredicative已经提到的那样。但实际上，由于常数因素不会对性能产生显着影响，因此甚至可以忽略它们，因此，传统上讲，您的实现仍具有O(n)的复杂度，其中n是输入列表的长度。

这里真正的问题是，只有当isPrime的复杂度为O(1)时，上述情况才会成立，但事实并非如此。该函数通过所有素数列表遍历，所以它本身的复杂度为O(m)。所以这里戏剧性的性能下降是由于你的算法的最终复杂度为O(n*m)造成的，因为在输入列表的每次迭代中，它必须将所有素数列表遍历到未知深度。

为了优化，我建议先对输入列表（需要O(n*log n)）进行排序，然后在所有素数列表中迭代自定义查找，这将在每次迭代中删除已访问的数字。通过这种方式，您将能够在所有素数列表上实现单遍历，理论上可以授予您复杂度为O(n*log n + n + m)，通过突出显示成本中心，常规上可以将其简单地看作O(n*log n)。

Answer 2

所以，这里有一些事情要做。让我们来看看一些操作涉及：

• length
• filter
• isPrime
• length

正如你所说，使用length两次没有什么帮助，因为这是列表为O(n)。你做了两次。然后是filter，它也将在O(n)中完成整个列表。我们想要做的就是一次性完成所有这些。

Data.List.Stream模块中的功能实现了一种名为Stream Fusion的技术，例如将您的(length (filter isPrime xs))调用重写为单个循环。不过，你仍然有第二次电话会议。你可以用一对蓄电池的重写这整件事变成单眼皮（或使用该国家或ST单子），并在单次做到这一点：

ratioOfPrimes xs = let 
    (a,b) = foldl' (\(odd,all) i -> if (isPrime i) then (odd +1, all+1) else (odd, all+1)) (0,0) xs 
in a/b 

然而，在这种情况下，你也可以搬走从使用列表并使用vector库。载体库实现相同的流融合技术用于去除中间列表，但也有一些其它的漂亮的功能：

• length是O(1)
• 的Data.Vector.Unboxed模块可以存储unboxable类型（其原始类型如Int肯定是）没有盒装表示的开销。所以这个int列表将被存储为一个低级的Int数组。

使用vector软件包应该可以让您编写上面的惯用表示法，并且比单遍转换的性能更好。

import qualified Data.Vector.Unboxed as U 

ratioOfPrimes :: U.Vector Int -> Double 
ratioOfPrimes xs = (fromIntegral $ U.length . U.filter isPrime $ xs)/(fromIntegral $ U.length xs) 

当然，这还没有被提及的事情是isPrime功能，以及是否真正的问题是，它是为大型n缓慢。一个不成熟的总检查员可能会轻易地将注意力从列表中排除出水面。