CoffeeScript 打亂數(shù)組中的元素

打亂數(shù)組中的元素

問題

你想打亂數(shù)組中的元素。

解決方案

Fisher-Yates shuffle是一種高效、公正的方式來讓數(shù)組中的元素隨機化。這是一個相當簡單的方法：在列表的結(jié)尾處開始，用一個隨機元素交換最后一個元素列表中的最后一個元素。繼續(xù)下一個并重復(fù)操作，直到你到達列表的起始端，最終列表中所有的元素都已打亂。這[Fisher-Yates shuffle Visualization](http://bost.ocks.org/mike/shuffle/)可以幫助你理解算法。

shuffle = (source) ->
  # Arrays with < 2 elements do not shuffle well. Instead make it a noop.
  return source unless source.length >= 2
  # From the end of the list to the beginning, pick element `index`.
  for index in [source.length-1..1]
    # Choose random element `randomIndex` to the front of `index` to swap with.
    randomIndex = Math.floor Math.random() * (index + 1)
    # Swap `randomIndex` with `index`, using destructured assignment
    [source[index], source[randomIndex]] = [source[randomIndex], source[index]]
  source

shuffle([1..9])
# => [ 3, 1, 5, 6, 4, 8, 2, 9, 7 ]

討論

一種錯誤的方式

有一個很常見但是錯誤的打亂數(shù)組的方式：通過隨機數(shù)。

shuffle = (a) -> a.sort -> 0.5 - Math.random()

如果你做了一個隨機的排序，你應(yīng)該得到一個序列隨機的順序，對吧？甚至微軟也用這種隨機排序算法 。原來，[這種隨機排序算法產(chǎn)生有偏差的結(jié)果]( http://blog.codinghorror.com/the-danger-of-naivete/) ，因為它存在一種洗牌的錯覺。隨機排序不會導(dǎo)致一個工整的洗牌，它會導(dǎo)致序列排序質(zhì)量的參差不齊。

速度和空間的優(yōu)化

以上的解決方案處理速度是不一樣的。該列表，當轉(zhuǎn)換成JavaScript時，比它要復(fù)雜得多，變性分配比處理裸變量的速度要慢得多。以下代碼并不完善，并且需要更多的源代碼空間 … 但會編譯量更小，運行更快：

shuffle = (a) ->
  i = a.length
  while --i > 0
    j = ~~(Math.random() * (i + 1)) # ~~ is a common optimization for Math.floor
    t = a[j]
    a[j] = a[i]
    a[i] = t
  a

擴展 Javascript 來包含亂序數(shù)組

下面的代碼將亂序功能添加到數(shù)組原型中，這意味著你可以在任何希望的數(shù)組中運行它，并以更直接的方式來運行它。

Array::shuffle ?= ->
  if @length > 1 then for i in [@length-1..1]
    j = Math.floor Math.random() * (i + 1)
    [@[i], @[j]] = [@[j], @[i]]
  this

[1..9].shuffle()
# => [ 3, 1, 5, 6, 4, 8, 2, 9, 7 ]

注意: 雖然它像在Ruby語言中相當普遍，但是在JavaScript中擴展本地對象通常被認為是不太好的做法 ( 參考:Maintainable JavaScript: Don’t modify objects you don’t own
正如提到的，以上的代碼的添加是十分安全的。它僅僅需要添Array :: shuffle如果它不存在，就要添加賦值運算符(? =) 。這樣，我們就不會重寫到別人的代碼，或是本地瀏覽器的方式。

同時，如果你認為你會使用很多的實用功能，可以考慮使用一個工具庫，像Lo-dash。他們有很多功能，像跨瀏覽器的簡潔高效的地圖。Underscore也是一個不錯的選擇。