[javascript] Javascript 배열이 희소합니까?

Program / 글쓴이

즉, 현재 시간을 배열의 인덱스로 사용하는 경우 :

array[Date.getTime()] = value;

인터프리터는 0부터 지금까지 모든 요소를 ​​인스턴스화합니까? 브라우저마다 다르게 작동합니까?

요청에 따라 의사 -ttys를 생성 하는 AIX 커널에 버그가 있었던 것을 기억합니다 . 그러나 “echo> / dev / pty10000000000″이라고 말하면 / dev / pty0, / dev / pty1이 생성됩니다. …. 그리고 죽어 넘어집니다. 무역 박람회에서는 재미 있었지만 고객에게 이런 일이 일어나지 않기를 바랍니다.

답변

JavaScript 배열이 정확히 구현되는 방식은 브라우저마다 다르지만 일반적으로 실제 배열을 사용하는 것이 비효율적이라면 일반 객체의 속성 액세스에 사용되는 것과 동일한 희소 구현으로 대체됩니다.

특정 구현에 대해 더 많은 지식을 가진 사람에게 조밀에서 희소로의 전환을 유발하는 원인에 대한 답변을 요청해야하지만 예제는 완벽하게 안전해야합니다. 조밀 한 배열을 얻으려면 명시적인 길이 인수를 사용하여 생성자를 호출하고 실제로 하나를 얻길 바랍니다.

olliej의 자세한 설명 은 이 답변 을 참조하십시오 .

답변

네, 그렇습니다. 실제로는 내부적으로 해시 테이블이므로 큰 정수뿐만 아니라 문자열, 부동 소수점 또는 기타 개체도 사용할 수 있습니다. 모든 키 toString()는 해시에 추가되기 전에을 통해 문자열로 변환됩니다 . 몇 가지 테스트 코드로이를 확인할 수 있습니다.

<script>
  var array = [];
  array[0] = "zero";
  array[new Date().getTime()] = "now";
  array[3.14] = "pi";

  for (var i in array) {
      alert("array["+i+"] = " + array[i] + ", typeof("+i+") == " + typeof(i));
  }
</script>

표시 :

array[0] = zero, typeof(0) == string
array[1254503972355] = now, typeof(1254503972355) == string
array[3.14] = pi, typeof(3.14) == string

for...in실제로 정의 된 인덱스 만 제공 하는 구문을 어떻게 사용했는지 주목하십시오 . 더 일반적인 for (var i = 0; i < array.length; ++i)반복 스타일 을 사용하면 비표준 배열 인덱스에 분명히 문제가 있습니다.

답변

이런 종류의 것을 위해 설계된 자바 스크립트 구문을 사용하여 문제를 피할 수 있습니다. 사전으로 취급 할 수 있지만 “for … in …”구문을 사용하면 모든 것을 얻을 수 있습니다.

var sparse = {}; // not []
sparse["whatever"] = "something";

답변

자바 스크립트 객체는 희소하고 배열은 자동 유지되는 길이 속성 (실제로 는 정의 된 요소 수가 아니라 가장 큰 인덱스보다 하나 더 큼 )과 몇 가지 추가 메서드 가있는 특수 객체입니다 . 당신은 어느 쪽이든 안전합니다. 추가 기능이 필요한 경우 배열을 사용하고 그렇지 않으면 객체를 사용하십시오.

답변

대답은 일반적으로 JavaScript에서 그렇듯이 “조금 더 현명합니다 ….”입니다.

메모리 사용량은 정의되지 않았으며 모든 구현은 어리석은 것이 허용됩니다. 이론적으로 const a = []; a[1000000]=0;는 메가 바이트의 메모리를 태울 수 const a = [];있습니다. 실제로 Microsoft조차도 이러한 구현을 피합니다.

Justin Love 는 길이 속성이 가장 높은 인덱스 세트라고 지적합니다 . 그러나 인덱스가 정수인 경우에만 업데이트됩니다.

따라서 배열은 희소합니다. 그러나 reduce (), Math.max () 및 “for … of”와 같은 내장 함수는 0에서 길이까지 가능한 정수 인덱스의 전체 범위를 살펴보고 ‘undefined’를 반환하는 많은 항목을 방문합니다. 그러나 ‘for … in’루프는 정의 된 키만 방문하여 예상대로 수행 할 수 있습니다.

다음은 Node.js를 사용하는 예입니다.

"use strict";
const print = console.log;

let a = [0, 10];
// a[2] and a[3] skipped
a[4] = 40;
a[5] = undefined;  // which counts towards setting the length
a[31.4] = 'ten pi';  // doesn't count towards setting the length
a['pi'] = 3.14;
print(`a.length= :${a.length}:, a = :${a}:`);
print(`Math.max(...a) = :${Math.max(a)}: because of 'undefined values'`);
for (let v of a) print(`v of a; v=:${v}:`);
for (let i in a) print(`i in a; i=:${i}: a[i]=${a[i]}`);

기부:

a.length= :6:, a = :0,10,,,40,:
Math.max(...a) = :NaN: because of 'undefined values'
v of a; v=:0:
v of a; v=:10:
v of a; v=:undefined:
v of a; v=:undefined:
v of a; v=:40:
v of a; v=:undefined:
i in a; i=:0: a[i]=0
i in a; i=:1: a[i]=10
i in a; i=:4: a[i]=40
i in a; i=:5: a[i]=undefined
i in a; i=:31.4: a[i]=ten pi
i in a; i=:pi: a[i]=3.14

그러나. 아직 언급되지 않은 어레이에 대한 더 많은 코너 케이스가 있습니다.

답변

비표준 process.memoryUsage ()를 사용하여 NodeJS에 대해 희소성 (또는 밀도)을 경험적으로 확인할 수 있습니다 .

때때로 노드는 배열을 희박하게 유지하기에 충분히 영리합니다.

Welcome to Node.js v12.15.0.
Type ".help" for more information.
> console.log(`The script is using approximately ${Math.round(process.memoryUsage().heapUsed / 1024 / 1024 * 100) / 100} MB`)
The script is using approximately 3.07 MB
undefined
> array = []
[]
> array[2**24] = 2**24
16777216
> array
[ <16777216 empty items>, 16777216 ]
> console.log(`The script is using approximately ${Math.round(process.memoryUsage().heapUsed / 1024 / 1024 * 100) / 100} MB`)
The script is using approximately 2.8 MB
undefined

때로는 노드가 밀도를 높이도록 선택합니다 (이 동작은 향후 최적화 될 수 있음).

> otherArray = Array(2**24)
[ <16777216 empty items> ]
> console.log(`The script is using approximately ${Math.round(process.memoryUsage().heapUsed / 1024 / 1024 * 100) / 100} MB`)
The script is using approximately 130.57 MB
undefined

그런 다음 다시 희소합니다.

> yetAnotherArray = Array(2**32-1)
[ <4294967295 empty items> ]
> console.log(`The script is using approximately ${Math.round(process.memoryUsage().heapUsed / 1024 / 1024 * 100) / 100} MB`)
The script is using approximately 130.68 MB
undefined

따라서 원래 AIX 커널 버그에 대한 느낌을 얻기 위해 조밀 한 배열을 사용하는 것은 범위와 유사한 방식 으로 강제해야 할 수도 있습니다 .

> denseArray = [...Array(2**24).keys()]
[
   0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11,
  12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
  24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35,
  36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
  48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
  60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71,
  72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83,
  84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95,
  96, 97, 98, 99,
  ... 16777116 more items
]
> console.log(`The script is using approximately ${Math.round(process.memoryUsage().heapUsed / 1024 / 1024 * 100) / 100} MB`);
The script is using approximately 819.94 MB
undefined

왜 넘어지게하지 않습니까?

> tooDenseArray = [...Array(2**32-1).keys()]

<--- Last few GCs --->

[60109:0x1028ca000]   171407 ms: Scavenge 1072.7 (1090.0) -> 1056.7 (1090.0) MB, 0.2 / 0.0 ms  (average mu = 0.968, current mu = 0.832) allocation failure
[60109:0x1028ca000]   171420 ms: Scavenge 1072.7 (1090.0) -> 1056.7 (1090.0) MB, 0.2 / 0.0 ms  (average mu = 0.968, current mu = 0.832) allocation failure
[60109:0x1028ca000]   171434 ms: Scavenge 1072.7 (1090.0) -> 1056.7 (1090.0) MB, 0.2 / 0.0 ms  (average mu = 0.968, current mu = 0.832) allocation failure


<--- JS stacktrace --->

==== JS stack trace =========================================

    0: ExitFrame [pc: 0x100931399]
    1: StubFrame [pc: 0x1008ee227]
    2: StubFrame [pc: 0x100996051]
Security context: 0x1043830808a1 <JSObject>
    3: /* anonymous */ [0x1043830b6919] [repl:1] [bytecode=0x1043830b6841 offset=28](this=0x104306fc2261 <JSGlobal Object>)
    4: InternalFrame [pc: 0x1008aefdd]
    5: EntryFrame [pc: 0x1008aedb8]
    6: builtin exit frame: runInThisContext(this=0x104387b8cac1 <ContextifyScript map = 0x1043...

FATAL ERROR: invalid array length Allocation failed - JavaScript heap out of memory

Writing Node.js report to file: report.20200220.220620.60109.0.001.json
Node.js report completed
 1: 0x10007f4b9 node::Abort() [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
 2: 0x10007f63d node::OnFatalError(char const*, char const*) [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
 3: 0x100176a27 v8::Utils::ReportOOMFailure(v8::internal::Isolate*, char const*, bool) [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
 4: 0x1001769c3 v8::internal::V8::FatalProcessOutOfMemory(v8::internal::Isolate*, char const*, bool) [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
 5: 0x1002fab75 v8::internal::Heap::FatalProcessOutOfMemory(char const*) [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
 6: 0x1005f3e9b v8::internal::Runtime_FatalProcessOutOfMemoryInvalidArrayLength(int, unsigned long*, v8::internal::Isolate*) [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
 7: 0x100931399 Builtins_CEntry_Return1_DontSaveFPRegs_ArgvOnStack_NoBuiltinExit [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
 8: 0x1008ee227 Builtins_IterableToList [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
Abort trap: 6

답변

그럴 수 있지만 항상 그럴 필요는 없으며 그렇지 않을 때 더 잘 수행 할 수 있습니다.

다음은 배열 인스턴스에서 인덱스 희소성을 테스트하는 방법에 대한 설명입니다.
https://benmccormick.org/2018/06/19/code-golf-sparse-arrays/

이 코드 골프 (최소 문자) 우승자는 다음과 같습니다.

let isSparse = a => !!a.reduce(x=>x-1,a.length)

기본적으로 길이 값을 !!줄이고 거짓 / 진정한 숫자 결과 의 강화 된 부울을 반환하면서 인덱스 된 항목에 대한 배열을 탐색합니다 (누산기가 0까지 감소하면 인덱스가 완전히 채워지고 희소하지 않음). 위의 Charles Merriam의주 의 사항도 고려해야하며이 코드는이를 해결하지 않지만 arr[var]= (something)var가 정수가 아닌 요소를 할당 할 때 발생할 수있는 해시 된 문자열 항목에 적용됩니다 .

인덱스 희소성에 관심이있는 이유는 스크립트 엔진마다 다를 수있는 성능에 대한 영향입니다. 여기에 배열 생성 /. 초기화에 대한 훌륭한 토론이 있습니다.
JavaScript를 선언하는 동안 “Array ()”와 “[]”의 차이점은 무엇입니까? 정렬?

해당 게시물에 대한 최근 답변에는 V8이 희소성 ( https://v8.dev/blog/elements-kinds) 과 같은 특성에 대한 (재) 테스트를 피하기 위해 태그를 지정하여 어레이를 최적화하는 방법에 대한 링크가 있습니다 . 블로그 게시물은 ’17 년 9 월에 작성되었으며 자료는 일부 변경 될 수 있지만 일상적인 개발에 대한 의미에 대한 분석은 유용하고 명확합니다.