javascript - 이차원 - 자바스크립트 동적 2차원 배열




자바 스크립트에서 2 차원 배열을 빠르게 스케일하는 방법? (3)

주어진 2 차원 배열 a :

let a = [
    [0, 0, 1, 0], 
    [0, 1, 1, 1], 
    [0, 0, 1, 0], 
    [0, 0, 1, 1] 
]

주어진 요인으로 어떻게 규모를 조정할 수 있습니까? 예를 들어, 배열 b는 4로 축척 된 배열입니다.

let b =[ 
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
]

이것은이 작업을 수행하기 위해 작성한 코드이지만 큰 배열 (200 x 200)을 처리 할 때 속도가 느립니다 (클라이언트 브라우저 : Chrome). 스케일링을 사용하면 facor가 16이라고 말할 수 있습니다.

// scale an array by a factor of 'scale'

const scaledMatrixArray = (arr, scale) => {
        let newArr = [];
        arr.forEach((el) => {
            let newArrRow = [];
            el.forEach((el) => {
                for (let j = 0; j < scale; j++) {
                    newArrRow.push(el);
                }
            });
            for(let i = 0; i < scale ; i++) {
                newArr.push(newArrRow);
            }
        });
        return newArr;
    };

구현이 O (n ^ 2)의 일부 변형이며 매우 비효율적이라는 것을 알고 있습니다. 나는이 일을하는 더 좋은 방법이나 더 좋고 빠른 도서관을 찾고있다. 결과적으로 N> 200 이상의 NXN 어레이는 가장 효율적이고, 가장 빠르고, 메모리 집약적 인 방법으로 800 x 800 배열로 확장 할 수 있습니다.


다음은 Array().fill 사용하여 매우 축소 된 방법 Array().fill 필자는 적어도 브라우저에서 다른 답변보다 빠르게 실행됩니다.

두 버전을 추가했습니다. 하나는 스프레드 연산자이고 다른 하나는 .apply 입니다. apply 때 더 빠른 결과를 얻고 apply .

function scaleSpread(array, factor) {
	const scaled = [];

	for(const row of array) {
		let x = [];

		for(const item of row)
			x.push(...Array(factor).fill(item));

		scaled.push(...Array(factor).fill(x));
	}

	return scaled;
}

function scaleApply(array, factor) {
	const scaled = [];

	for(const row of array) {
		let x = [];

		for(const item of row)
			x.push.apply(x, Array(factor).fill(item));

		scaled.push.apply(scaled, Array(factor).fill(x));
	}

	return scaled;
}

function scaleConcat(array, factor) {
	let scaled = [];

	for(const row of array) {
		let x = [];

		for(const item of row)
			x = x.concat(Array(factor).fill(item));

		scaled = scaled.concat(Array(factor).fill(x));
	}

	return scaled;
}

var a = [ [0, 0, 1, 0], [0, 1, 1, 1],  [0, 0, 1, 0],  [0, 0, 1, 1] ]

console.time('spread');
scaleSpread(a, 10000);
console.timeEnd('spread');

console.time('apply');
scaleApply(a, 10000);
console.timeEnd('apply');

console.time('concat');
scaleConcat(a, 10000);
console.timeEnd('concat');

편집 : 적용 및 스프레드가 매우 큰 배열을 Maximum call stack size exceeded 하는 Maximum call stack size exceeded 인해 이후 버전을 .concat 사용하여 추가되었습니다.


약간의 재미, 당신은 많은 가치에 액세스하지 않는 경우 lazily 할 수 있습니다. 이 코드를 많이 테스트하지는 않았지만 작동해야합니다.

        var a = [
            [0, 0, 1, 0],
            [0, 1, 1, 1], 
            [0, 0, 1, 0], 
            [0, 0, 1, 42] 
          ],
          scale = 4;
    
        for (var idx = 0; idx < a.length; idx++) {
            a[idx] = new Proxy(a[idx], {
              get: function(target, i) {
            return target[Math.floor(i/scale)];
          }
        });
        }
        a = new Proxy(a, {
              get: function(target, i) {
            return target[Math.floor(i/scale)];
          }
        });
    
        console.log(a[16-1][16-1])

        for (var ii = 0; ii < 16;ii++) {
          for(var j=0;j<16;j++){
            console.log(a[ii][j])
          }
        }


일반적으로 함수 호출 수가 적을수록 오버 헤드가 적습니다.

function scale1D(arr, n) 
{
  for (var i = arr.length *= n; i; ) 
    arr[--i] = arr[i / n | 0]
}

function scale2D(arr, n) 
{
  for (var i = arr.length; i; )
    scale1D(arr[--i], n)

  scale1D(arr, n)
}

var a = [ [0, 0, 1, 0], [0, 1, 1, 1],  [0, 0, 1, 0],  [0, 0, 1, 1] ]
console.time( 1e6 )
scale2D(a, 1e6)
console.timeEnd( 1e6 )

var b = [ [0, 0, 1, 0], [0, 1, 1, 1],  [0, 0, 1, 0],  [0, 0, 1, 1] ]
scale2D(b, 4)
console.log( JSON.stringify( b ).replace(/],/g, '],\n ') )







matrix