javascript - Object.keys（）の複雑さ？

Question

一般的な実装におけるECMAScript5のObject.keys（）の時間計算量を知っている人はいますか？キーO(n)用ですか？nハッシュの実装を想定すると、時間はハッシュテーブルのサイズに比例しますか？

言語実装者による保証または実際のベンチマークのいずれかを探しています。

Answer 1

O(n)少なくともV8（chrome、node.js）にはあるようです。

> var hash = {}
>   ,    c = 0;
> 
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
0
> for(var i=0; i<100000; i++, c++){ hash[c] = 1; }
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
26
> for(var i=0; i<100000; i++, c++){ hash[c] = 1; }
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
49
> for(var i=0; i<100000; i++, c++){ hash[c] = 1; }
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
75
> for(var i=0; i<100000; i++, c++){ hash[c] = 1; }
> var s = +new Date();Object.keys(hash);console.log(+new Date() - s);
102    

Answer 2

（V8開発者はこちら。）

Object.keys()Mark Kahnの答えは、の複雑さが実際にO（n）である、十分に密な整数キー/「インデックス付き」プロパティに対して正しいものです。

JavaScript仕様は、すべてのオブジェクトプロパティが文字列キー/「名前付き」であると偽っていますが、それは最新の高性能エンジンがそれを実装する方法ではありません。内部的には大きな違いがあります！インデックス付きのプロパティは配列に格納され（十分な密度がある限り）、一般的に辞書よりもはるかに優れたパフォーマンスを提供します。{'1': 1, ...}

何千もの名前付きプロパティを持つオブジェクトの場合、実装では実際にハッシュテーブルを使用します（質問が推測したように）。つまり、の複雑さObject.keys()はO（n log n）です。これは、ハッシュテーブルが（もちろん）独自の順序でエントリを格納するためです。Object.keys()名前付きプロパティは、作成された順序で返す必要があります。これは、追加のメタデータとして保存されます。つまり、O（n log n）操作であるハッシュテーブルからキーを取得した後、キーを並べ替える必要があります。

実際に発生するほとんどのオブジェクトの名前付きプロパティ（最大約1,000個のプロパティ）は、（通常）作成順に特別な種類の内部配列に格納されるため、O（n）で取得でき、ソート済み。

したがって、要約は実際には「状況によって異なります」です:-)