配列からn個の要素を重複無しでランダムに取り出す

真っ先に思いついたのはコレ。

function random(array, num) {
    var a = array.concat(); // clone.
    var r = [];
    var l = array.length;
    var n = Math.min(num, array.length);
    while(n-- > 0) {
        var i = Math.floor(Math.random() * l--);
        r.push(a[i]);
        a.splice(i, 1);
    }
    return r;
}

ランダムに1個取り出して、元の配列からそれを削除していくことで重複を避けるものです。
実際に使う分にはこれで全く問題ないと思うんですが、扱う数が大きくなってくると splice がボトルネックになってきます(LinkedListではないですからね)。
そこで、こう書き換えてみました。

function random(array, num) {
    var a = array.concat(); // clone.
    var r = [];
    var l = array.length;
    var n = Math.min(num, array.length);
    while(n-- > 0) {
        var i = Math.floor(Math.random() * l);
        r.push(a[i]);
        a[i] = a[--l];
    }
    return r;
}

だいぶ高速化できたんじゃないでしょうか？
ツッコミあればよろしくお願いします。

• -

こうすれば concat もいらないか。
(追記：t[i]が 0 とか false 等だといけないけど。)
(追記：バグ修正しました。)

function random(array, num) {
    var a = array;
    var t = {};
    var r = [];
    var l = a.length;
    var n = num < l ? num : l;
    while (n-- > 0) {
        var i = Math.random() * l | 0; // http://d.hatena.ne.jp/amachang/20070813/1186980089
        r[n] = t[i] || a[i];
        // 6/16 バグ修正
        // t[i] = a[--l];
        --l;
        t[i] = t[l] || a[l];
    }
    return r;
}

• -

トラックバックいただきました。ありがとうございます。

後の二つは一様にならないし，重複する可能性もあるような。

ランダムにｎ個 - ellaneous

理由がわからなかったので、できれば解説をお願いしたいのですが…。
少なくとも(3番目の追記分を除けば)重複はありえないと思っているのですけれども(まさに追記分のことでしたらすみません)。

• -

3番目、修正しました(言われてみると確かに、試せばすぐわかりましたね。すみません)。
ご指摘ありがとうございます。