JavaScript学習メモ: 配列のランダムソート_html/css_WEB-ITnose

JavaScript には、配列項目の順序を変更するための sort() メソッドと reverse() メソッドが用意されています。しかし、多くの場合、これら 2 つの方法では、ポーカー ゲームのランダム シャッフルなど、実際のビジネスのニーズを満たすことができません。

この記事では、上記の例の効果を実現する方法と、配列のランダムな順序に関する関連知識を学びましょう。

配列のランダムソートに関する関連情報をインターネットで調べたところ、Math.random() を見つけました。ブラウザ コントローラを開き、次のように入力します:

Math.random()

JavaScript 乱数の概要については、記事「Math.random() 乱数についての 2 つまたは 3 つのこと」を参照してください。

この図から、Math.random() が 0 ～ 1 の間の乱数を取得していることがわかります。ご存知のとおり、sort() はパラメーターとして関数を呼び出すことができます。関数が値 -1 を返した場合、配列内の項目 a が項目 b よりも前にランク付けされていることを意味します。このようにして、Math.random() によってランダムに生成された数値を 0.5 と比較するランダム関数を作成できます。数値が 0.5 より大きい場合は -1 (a が b の前にランク付けされます) を返します。 return 1 (b は a の前にランクされます):

function randomSort(a, b) {    return Math.random() > 0.5 ? -1 : 1;}

例を見てください:

var arr = [1,2,3,4,5,6,7,8,9];arr.sort(randomSort);

このように、最初の例の効果は

前の方法は配列のランダムな並べ替えを実現しますが、新しい配列に送信される各要素の位置は常にランダムではないように感じられます。前の例と同様に、配列 arr 内の値 1 を持つ要素の元のキー値は 0 です。ランダムな並べ替え後、キー値 1 が 0 ～ 8 になる確率は同じです。次に、sort() メソッドが順番に比較するため、ここでは減少しています。

この現象に対処するには、次の再帰的メソッドを使用できます:

function randomSort(arr, newArr) {    // 如果原数组arr的length值等于1时，原数组只有一个值，其键值为0    // 同时将这个值push到新数组newArr中    if(arr.length == 1) {        newArr.push(arr[0]);        return newArr; // 相当于递归退出    }    // 在原数组length基础上取出一个随机数    var random = Math.ceil(Math.random() * arr.length) - 1;    // 将原数组中的随机一个值push到新数组newArr中    newArr.push(arr[random]);    // 对应删除原数组arr的对应数组项    arr.splice(random,1);    return randomSort(arr, newArr);}

この場合、次のように使用できます:

for (var i = 0; i < 10; i++) {    var arr=[1,2,3,4,5,6,7,8,9];    var newArr=[];    randomSort(arr,newArr);    console.log(newArr);}

出力結果:

randomSort(arr, newArr) 関数の実行後、元の配列 arr はクリアされます。

このメソッドを使用して記事の冒頭のシャッフルの例を実行する場合は、resetPic() 関数で pukePic 配列をリセットする必要があります。

上記の 2 つに加えて、メソッド、@Traveller 記事「配列要素のランダムな並べ替えアルゴリズムの実装」が DIV.IO で共有されました。この記事では、配列項目をランダムに並べ替えるための 3 つの実装方法を説明します。

配列の並べ替えメソッドを使用してランダムに並べ替えます。配列要素

Array.prototype.shuffle = function(n) {    var len = this.length ,        num = n ? Math.min(n,len) : len,        arr = this.slice(0);    arr.sort(function(a,b){        return Math.random()-0.5;    });    return arr.slice(0,num-1);}

配列内の要素をランダムに交換します

lib = {}lib.range = function(min,max) {    return min + Math.floor(Math.random()*(max-min+1));}Array.prototype.shuffle = function(n) {    var len = this.length,        num = n ? Math.min(n,len) : len,        arr = this.slice(0),        temp,        index;    for (var i=0;i<len;i++){        index = lib.range(i,len-1);        temp = arr[i];        arr[i] = arr[index];        arr[index]=temp;    }    return arr.slice(0,num);}

元の配列から要素をランダムに抽出し、新しい配列に追加します

lib = {}lib.range = function(min,max) {    return min+Math.floor(Math.random()*(max-min+1));}Array.prototype.shuffle = function(n) {    var len = this.length,         num = n ? Math.min(n,len) : len,        arr = this.slice(0),        result=[],        index;    for (var i=0;i<num;i++){        index = lib.range(0,len-1-i);        // 或者 result.concat(arr.splice(index,1))        result.push(arr.splice(index,1)[0]);  }  return result}

シャッフル アルゴリズム

配列のランダム ソートの基本原理は、シャッフル アルゴリズム (Fisher–Yates shuffle) です。

は、有限集合

の順序を破壊するアルゴリズムです。

Principle

• 配列 (シャッフル) を定義します。長さ (length) は元の配列 (arr) の長さです。
• インデックス (初期値) に 0 を取ります。 0) ランダム値 rand、shuffled[index ] = shuffled[rand] 、shuffled[rand] = arr[index]
• Index++ ; Index = length -1

は 0 から長さ -1 への代入処理でシャッフルされ、新しく追加された値は arr[index] です。 shuffled[index] の値は、重複する要素が 2 つあるため、割り当てられた要素間のランダムな値 shuffled[rand] になります。したがって、 shuffled[rand ] は新しく追加された値 arr[index] と同じになります。

underscore.js の shuffle メソッド

function random(min, max) {    if (max == null) {      max = min;      min = 0;    }    return min + Math.floor(Math.random() * (max - min + 1));};function shuffle(arr) {  var length = arr.length,      shuffled = Array(length);  for (var index = 0, rand; index < length; index++) {      rand = random(0, index);      if (rand !== index) shuffled[index] = shuffled[rand];      shuffled[rand] = arr[index];    }    return shuffled;}

実際のアプリケーション:

var arr = [1,2,3,4,5,6,7,8,9];for (var i = 0; i < 10; i++){    console.log(shuffle(arr));}

Chrome によって出力される結果は次のとおりです:

同様に、シャッフル アルゴリズムを使用して記事の冒頭の例を完成させます:

より単純なアルゴリズムもあります。より理解しやすい書き方:

function shuffle(arr) {    var i,         j,        temp;    for (i = arr.length - 1; i > 0; i--) {        j = Math.floor(Math.random() * (i + 1));        temp = arr[i];        arr[i] = arr[j];        arr[j] = temp;    }    return arr;};

シャッフルアルゴリズムに関する詳細な資料

Fisher–Yates shuffle
JavaScript での配列のシャッフル
Fisher-Yates Shuffle
シャッフル プログラムをテストする方法
Fisher-Yates シャッフル アルゴリズム
JavaScript 配列をランダム化 (シャッフル) する方法

概要

この記事では主に配列のランダムソートに関する関連情報をまとめてまとめています。もちろん、市場には同様の機能を実現するための方法がたくさんあります。これらはここで収集して整理したものです。より良い方法がある場合は、コメントで共有してください。

初心者が学習ノートを作成していますが、間違っているところがあれば専門家に指導してもらいたいです。誤解を招いてしまい申し訳ございません。

Da Mo

一般的に使用されるニックネームは、W3CPlus の創設者で現在モバイル タオバオで働いている「Da Mo」です。中国の Drupal コミュニティの中心メンバーの 1 人。彼は、HTML5、CSS3、Sass などのフロントエンド スクリプト言語について非常に深い理解と豊富な実践経験を持っており、特に CSS3 の研究に注力しており、中国で最初に研究と使用を行った人物の 1 人です。 CSS3テクノロジー。 CSS3、Sass、Drupalの中国人エバンジェリスト。 2014 年に『図解 CSS3: コア技術と事例実践』を出版しました。