js最適化ループ、DUFFデバイスで展開反復を実現する。

序文

日々の開発では、データ構造で構成された配列やオブジェクトがいたるところで見られますが、ビジネス機能が複雑化するにつれ、単純なオブジェクト配列では対応できなくなります。

判例

今、そういう需要があるとします：

1. テーブルが与えられた場合、テーブルの各行は、現在の行を一意に示す id 属性を持つオブジェクトです。
2. マルチセレクトをサポートし、データの各行の前にあるマルチセレクトボタンをクリックし、配列idArrに保存し、キャンセルされたときに配列内の項目を削除します。
3. 保存ボタンをクリックした後、行のisCheckedプロパティをtrueに変更します。

考え方はおそらく上記と同じ

各行のデータと、チェックされた行の ID の配列です。

const obj = [
    {
        'id': 0x1,
        'name': 'row1',
        'a': false
    },
    {
        'id': 0x2,
        'name': 'row2',
        'a': false
    },
    {
        'id': 0x3,
        'name': 'row3',
        'a': false
    },
    {
        'id': 0x4,
        'name': 'row4',
        'a': false
    },
    {
        'id': 0x5,
        'name': 'row5',
        'a': false
    },
    {
        'id': 0x6,
        'name': 'row6',
        'a': false
    },
    {
        'id': 0x7,
        'name': 'row7',
        'a': false
    }
];
const foo = [
    0x1,
    0x2,
    0x3,
    0x4,
    0x5,
    0x6
];

このように2つの配列がある場合、対応するid行のデータをそれぞれ変更したいのであれば、2レベルループを使用するのが自然ですが、問題はデータ量が大きい場合、これは非常にパフォーマンスを消費する可能性があるということです。

実装方法

• 2レベルループは以下のように実装されています。

// 仮にデータが data
const data = [
 {id: 1, name: 'row1', isChecked: false}, 
 {id: 2, name: 'row2', isChecked: false}, 
 {id: 3, name: 'row3', isChecked: false},
 {id: 4, name: 'row4', isChecked: false},
 {id: 5, name: 'row5', isChecked: false},
 {id: 6, name: 'row6', isChecked: false},
 {id: 7, name: 'row7', isChecked: false}
]
//   idArr
const idArr = [1,2,3,4,5,6]
for(let i = idArr.length - 1; i >= 0 ; i--) {
	for(let j = data.length - 1; j >= 0; j--) {
		if(data[i].id !== idArr[i]) continue
		data[i].isChecked = true
	}
}

上記のような数十数百のデータは、問題が特に顕著ではないので、書き込みますが、データの量が10,000以上に達すると、データの階層が深すぎるときにページが詰まる原因となる可能性があります！

• 2サイクルで1つのレイヤーを読み込みます。

// 仮にデータが data
const data = [
 {id: 1, name: 'row1', isChecked: false}, 
 {id: 2, name: 'row2', isChecked: false}, 
 {id: 3, name: 'row3', isChecked: false},
 {id: 4, name: 'row4', isChecked: false},
 {id: 5, name: 'row5', isChecked: false},
 {id: 6, name: 'row6', isChecked: false},
 {id: 7, name: 'row7', isChecked: false}
]
//   idArr
const idArr = [1,2,3,4,5,6]
// idマッピングテーブルを定義する
const dataMap = {}
for(let i = data.length - 1; i >= 0; i--) {
	// 行のidをキー、参照アドレスを値としてオブジェクトを形成する。
	dataMap[data[i].id] = data[i]
}
// idArrのペアを繰り返し、行データを再割り当てする。
for(let i = idArr.length - 1; i >= 0; i--) {
	dataMap[idArr[i]].isChecked = true
}
console.log(data)

結果は以下のようになり、1-6のisCheckedが変更されていることがわかります。 この方法は、2つの入れ子ループを同じレベルの2つのループに置き換えることで、時間の複雑さを軽減します。

考える：最適化を続ける方法はないでしょうか？データに100万個のエントリがある場合、上記のメソッドは100万個のエントリをトラバースする必要があります。

• DUFF

レッドブックは、 DUFFデバイスに 言及している 、大幅にループの数を減らすことができ、本のソースコードは次のとおりです：

var doSomething = (num) => console.log(num);
var values = [];
// 50w個のデータがあるとする
に対して (var i = 0; i < 500000; i++) {
 values.push(i);
}
var count = Math.ceil(values.length / 8);
var start = values.length % 8;
var j = 0;
do {
 switch (start) {
 case 0: doSomething(j++);
 case 7: doSomething(j++);
 case 6: doSomething(j++);
 case 5: doSomething(j++);
 case 4: doSomething(j++);
 case 3: doSomething(j++);
 case 2: doSomething(j++);
 case 1: doSomething(j++);
 }
 start = 0;
} while (--count > 0);

上記のアルゴリズムでは、長さ10の配列を2回反復するだけです。要素数を8で割ってループ回数を計算することです。ceilは小数点以下を切り上げるので、反復回数は常に正になりますが、完全に反復すると、n / 8が無尽蔵になりそうなので、最初の反復は小数点以下を切り上げられる部分を除いて、length % 8回になるので、さらに数回doSomethingする必要があるかもしれません。doSomething関数を最初に実行します。

長さが10、実行回数が2、残りの8が2とすると、最初の繰り返しはケース2からスタートし、1回目はdoSomethingを2回実行し、スタート実行後の1回目は0、2回目はdoSomethingを8回実行し、足すと10になります

ピット：なぜ8で割らなければならないのでしょうか？9は反復回数を最小限にするためではないでしょうか？この場所についていろいろ考えているのですが、答えが見つかりません！

DUFFは反復回数を大幅に減らすことができるので、私は上記の2番目のアルゴリズムを最適化したいと思います。

// 仮にデータが data
const data = [
 {id: 1, name: 'row1', isChecked: false}, 
 {id: 2, name: 'row2', isChecked: false}, 
 {id: 3, name: 'row3', isChecked: false},
 {id: 4, name: 'row4', isChecked: false},
 {id: 5, name: 'row5', isChecked: false},
 {id: 6, name: 'row6', isChecked: false},
 {id: 7, name: 'row7', isChecked: false}
]
//   idArr
const idArr = [1,2,3,4,5,6]
// DUFF関数を定義する
Array.prototype.duffFunc = function(callback){
 console.log(this)
	if(!Array.isArray(this)) {
		console.error('must be a array')
		return
	}
	let iteration = Math.ceil(this.length / 8)
	let start = this.length % 8
	let index = 0
	do{
		switch(start) {
			case 0: callback(this[index], index++)
			case 7: callback(this[index], index++)
			case 6: callback(this[index], index++)
			case 5: callback(this[index], index++)
			case 4: callback(this[index], index++)
			case 3: callback(this[index], index++)
			case 2: callback(this[index], index++)
			case 1: callback(this[index], index++)
		}
		start = 0
	}while (--iteration > 0)
}
// すべてのforループをダフな実装に置き換える
const dataMap = {}
data.duffFunc((item, index) => {
	dataMap[item.id] = item
})
idArr.duffFunc((item, index) => {
	dataMap[item].isChecked = true
})
console.log(data)