JavaScript中的惰性数组介绍

Rickie22I 4年前
   <p>今天我要介绍的是 <a href="/misc/goto?guid=4959750097102238086" rel="nofollow,noindex">lazy-arr</a> ,它给JavaScript中带来了惰性数组。</p>    <h2>什么是惰性数组,它为什么有用?</h2>    <p>我们来重现一下你第一次面试软件工程师时的题目:写一个斐波纳契函数。我们明确了0和1的基本情况,然后递归生成剩下的:</p>    <pre>  <code class="language-javascript">let fib = n => {    switch (n) {      case 0: return 0      case 1: return 1      default: return fib(n - 1) + fib(n - 2)    }  }</code></pre>    <p>小菜一碟。</p>    <p>这种解决方案有什么问题吗?还用说么 - 效率真的真的很低。要计算第n个斐波那契数字,我们要调用 fib 函数 2的n-1幂次!简直糟糕的要命,我们应该做的更好一点。</p>    <p>一种方法是记录 fib 的输出。就是说,由于 fib 是纯粹和幂等的,我们可以缓存其输出:</p>    <pre>  <code class="language-javascript">let memoize = fn => {    let cache = new Map    return _ => {      if (!cache.has(_)) {        cache.set(_, fn(_))      }      return cache.get(_)    }  }    let fib = memoize(n => {    switch (n) {      case 0: return 0      case 1: return 1      default: return fib(n - 1) + fib(n - 2)    }  })</code></pre>    <p>好多了!现在我们输入为n时,只需调用 fib n - 1次。</p>    <p>我们还能怎么表达这种思想呢?</p>    <h2>懒序列</h2>    <p>在Scale中,你可以这样做(这得归功于 <a href="/misc/goto?guid=4959750097209311334" rel="nofollow,noindex">Philipp Gabler</a> ):</p>    <pre>  <code class="language-javascript">def fib(n: Int): Stream[Int] = {    lazy val stream: Stream[Int] = 0 #:: stream.scan(1)(_ + _)    stream.take(n)  }</code></pre>    <p>上面做的事情就是定义一个惰性的数据流(两个初始数字,加上一个能产生更多数字的函数),当调用 fib(n) 时,它返回第n个数字,或者如果还没有计算,就生成并返回它。另一种思考方式是用生成器和一个记录先前产生值的缓存,这样之后就可以通过值的索引进行访问。</p>    <p>惰性流是一个非常酷的抽象概念,对于计算开销昂贵的序列,或者是不可能计算所有索引的序列都有效(即:无限序列)。这在功能性语言中很受欢迎,特别是默认具有惰性求值的语言。比如在Haskell中就是这样做:</p>    <pre>  <code class="language-javascript">fibs :: [Integer]  fibs = 0 : 1 : zipWith (+) fibs (tail fibs)</code></pre>    <p>同样的思维,但在Clojure就是这样:</p>    <pre>  <code class="language-javascript">(defn fib []    ((fn rfib [a b]          (cons a (lazy-seq (rfib b (+ a b)))))      0 1))</code></pre>    <p>你大概明白了吧。</p>    <p>那在JavaScript中怎么用呢?</p>    <h2>JavaScript中的惰性序列</h2>    <p>通过 <a href="/misc/goto?guid=4959750097102238086" rel="nofollow,noindex">lazy-arr</a> ,你可以像这样:</p>    <pre>  <code class="language-javascript">let fibs = lazy([0, 1])(_ => fibs[_ - 1] + fibs[_ - 2])</code></pre>    <p>就这样!然后,您可以根据需要访问数组中的项,并根据需要进行计算:</p>    <pre>  <code class="language-javascript">fibs[10] // 55  fibs[7]  // 13</code></pre>    <p>第一行计算第10个斐波纳契数,并且由于我们递归地进行计算的定义(按照以前的斐波那契数),我们需要计算前9个斐波那契数,以此来计算第10个。所以当我们在第二行计算第七个斐波纳契数时,结果会立即返回,因为我们已经计算好了!</p>    <p>最重要的是,就用户关心的来说, fibs 数组并不会做任何懈怠地、有状态地或递归地或其他类似的事情。它只是一个数组。那些麻烦的东西被lazy-arr封装好了,生成器就是一行代码。</p>    <p>是不是很优雅?</p>    <p> </p>    <p>来自:http://www.zcfy.cc/article/performancejs-introducing-lazy-arrays-in-javascript-3312.html</p>    <p> </p>