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

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

問題

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

解決方案

Fisher-Yates shuffle是一種高效、公正的方式來讓數(shù)組中的元素隨機(jī)化。這是一個(gè)相當(dāng)簡單的方法：在列表的結(jié)尾處開始，用一個(gè)隨機(jī)元素交換最后一個(gè)元素列表中的最后一個(gè)元素。繼續(xù)下一個(gè)并重復(fù)操作，直到你到達(dá)列表的起始端，最終列表中所有的元素都已打亂。這[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 ]

討論

一種錯(cuò)誤的方式

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

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

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

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

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

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

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

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

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語言中相當(dāng)普遍，但是在JavaScript中擴(kuò)展本地對(duì)象通常被認(rèn)為是不太好的做法 ( 參考:Maintainable JavaScript: Don’t modify objects you don’t own
正如提到的，以上的代碼的添加是十分安全的。它僅僅需要添Array :: shuffle如果它不存在，就要添加賦值運(yùn)算符(? =) 。這樣，我們就不會(huì)重寫到別人的代碼，或是本地瀏覽器的方式。

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