在Haskell中构建循环列表的最经济的方法 [英] Least expensive way to construct cyclic list in Haskell

问题描述

因此，如果我想构建一个n 0和1 1的循环列表，下列哪种方法更好/更便宜？还有更好/更便宜的方法吗？考虑到n是一个整数，可能很大（尽管实际上它不会超过2 ^ 32）。

  aZerosAndOnes :: Integer  - > [Int] 
 aZerosAndOnes n 
 | n> = 0 =循环（genericReplicate n 0 ++ [1]）$ ​​b $ b |否则= [] 
  

与

  bZerosAndOnes :: Integer  - > [Int] 
 bZerosAndOnes n 
 | n> = 0 = tail（cycle（1：genericReplicate n 0））
 |否则= [] 
  

解决方案

其次，因为它显然高效并且足够清晰。第一个将取决于 genericReplicate 是否能够以某种方式与 ++ 融合。要确定的最好方法是运行

  ghc -O2 -ddump-simpl -dsuppress-all whatever.hs |减去
  

hr>

也就是说，一个周期的整个长度实际上将分配在内存中。这就是目前实施的循环功能的性质，并且看起来似乎不会改变（除了一些显着的进步 - 折叠/构建融合似乎不足够）。所以你最好避免使用这种方法，通过以不同的方式编写其他代码来避免这种情况。

---

是的，我想到别的东西。如果你以单线程的方式使用这个列表，你可以完全省去循环：

weirdthing n = genericReplicate n 0 ++ [1] ++ weirdthing n

这就是我的最终答案。这使得无限列表，而不是一个循环列表，但当 n 足够大，这是更好。

So if I want to construct a circular list of n 0's and 1 1, which of the following ways is better/cheaper? And is there an even better/cheaper way? Taking into account that n is an Integer and may be large (though realistically its not going to exceed 2^32).

aZerosAndOnes :: Integer -> [Int]
aZerosAndOnes n 
    | n >= 0    = cycle (genericReplicate n 0 ++ [1])
    | otherwise = []

versus

bZerosAndOnes :: Integer -> [Int]
bZerosAndOnes n 
    | n >= 0    = tail (cycle (1 : genericReplicate n 0))
    | otherwise = []

解决方案

I'd definitely go with the second, because it's obviously efficient and plenty clear enough. The first will depend on whether genericReplicate is able to fuse with ++ in some fashion. The best way to find out for sure is to run

ghc -O2 -ddump-simpl -dsuppress-all whatever.hs | less

and pore over what it spews.

---

That said, the entire length of a cycle will actually be allocated in memory. Such is the nature of the cycle function as currently implemented, and that does not seem likely to change (barring some significant advance—foldr/build fusion does not seem to be sufficient). So you probably be better off avoiding this altogether by writing the rest of your code differently.

---

Ah yes, I thought of something else. If you consume this list in a "single-threaded" fashion, you can dispense with cycle altogether:

weirdthing n = genericReplicate n 0 ++ [1] ++ weirdthing n

and that's my final answer. This makes an infinite list instead of a cyclic list, but when n is big enough, that's better.

这篇关于在Haskell中构建循环列表的最经济的方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！