Go to Qiita Advent Calendar 2024 Top
LoginSignup
34
25

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@t2kojimain株式会社ソニックガーデン

[JavaScript] 疎な配列（Sparse Arrays）

Posted at

**疎な配列（Sparse Arrays）**ってご存知ですか？

この疎な配列に対する認識が曖昧だった為に最近テスト漏れを起こしてしまったので、その際に調査・検証した内容をまとめてみたいと思います。

TL;DR

  • 長さはあるけど要素が（一部、もしくは全て）存在しない配列があるよ。
  • ループやメソッドを扱う時、気を付けないと予期しない動作をするよ。

動作環境

  • node.js 8.11.3

コードの動作例は node の REPL を使用しています。

疎な配列ってなんだ？

疎な配列とは長さだけを与えられ初期化された配列、つまり new Array(5) のことです。[,,,,,] とも書けます。

連続した数値の配列（Range）が欲しい時使いますよね、あれのことです。

Array.from(Array(5), (v, k) => k) // これとか

[...Array(5).keys()] // これで使ってるよね

// [ 0, 1, 2, 3, 4 ] この配列を得ることができる

疎な配列の中身は空の状態です。各要素は初期化すらされていなく、undefined ですらない何も存在しない疎の状態です。

> Array(5)
[ <5 empty items> ]

宣言時の注意

疎な配列を作成する時、Array(5) で作るなら問題ありませんが、[,,,,,] で作る場合ちょっと注意が必要です。この 2 つの配列は両方とも長さが 5 になりますが、後者を見るとカンマが 5 個あるので要素が 6 つあるように見えます。

以下の結果を見ると、いくつかルールがあることがわかります。

> [,]
[ <1 empty item> ]
> [,,]
[ <2 empty items> ]
> [,1]
[ <1 empty item>, 1 ]
> [,1,]
[ <1 empty item>, 1 ]
  1. 見かけの要素数 -1（カンマの数）が実際の要素数
  2. 最後の要素が empty item の場合、カンマで終わらなければならない。
  3. 最後の要素が実際の値（undefined を含む）の場合、カンマで終わらなくてもよい。

3 番目は通常の配列では当然のことなので、1 番目と 2 番目が疎な配列を作る場合のルールということになります。

要素は undefined ではない

疎な配列の要素にアクセスすると undefined が返ってきます。

> Array(5)[1]
undefined

では疎な配列の各要素は undefined なのでしょうか？いいえ、ここで返ってきている undefined は要素に undefined が格納されているからではなく、存在しないプロパティにアクセスしたから undefined が返ってきているのです。

> Array(5)[999]
undefined // これと意味は同じ

もう一つ動作例として、疎な配列の要素に undefined を明示的に代入してみます。

> array = Array(5)
[ <5 empty items> ]
> array[2] = undefined
undefined
> array
[ <2 empty items>, undefined, <2 empty items> ]

undefined が <2 empty items> の間に入りました。これからもこの empty item は undefined と異なることが分かります。

疎な配列の各要素は undefined では無くプロパティが存在しない要素であることが分かりました。以後の説明をやり易くするため、このプロパティが存在しない要素を便宜的に疎の要素と呼ぶことにします。

どうやって識別するの？

疎な配列では要素を取り出そうとすると undefined が返ってきました。では本当に undefined が格納されている要素と疎の要素はどのように識別したら良いのでしょうか。

> array = [,undefined]
[ <1 empty item>, undefined ]
> array[0]
undefined // どちらも
> array[1]
undefined // undefinedだよね

識別には hasOwnProperty メソッドもしくは in演算子 を使います。これらが true を返せば存在するプロパティですし、false を返せば存在しないプロパティ（疎の要素）ということが分かります。

共に Array の場合はインデックスを渡すことでプロパティの有無を検査することができます。

> array = [,undefined]
> 0 in array
false // 疎の要素なのでfalse
> 1 in array
true  // undefinedは実際に格納されているのでtrue
> 2 in array
false // ついでに存在しないインデックスも当然false

hasOwnProperty でも結果は同じです。

> array = [,undefined]
> array.hasOwnProperty(0)
false
> array.hasOwnProperty(1)
true
> array.hasOwnProperty(2)
false

コピーでの違い

配列をコピー（シャローコピー）する時、対象が疎な配列の場合は注意しないと正確にコピーされません。

Array.from とスプレッド構文

通常の場合、これらは配列をコピーすることができます。（正確には新しい Array インスタンスを得ることができる）

> array = [1,2,3,4,5]
[ 1, 2, 3, 4, 5 ]
> Array.from(array)
[ 1, 2, 3, 4, 5 ]
> [...array]
[ 1, 2, 3, 4, 5 ]

しかし対象が疎な配列の場合、疎の要素が undefined に置き換わってしまいます。

> array = [,,3,,5]
[ <2 empty items>, 3, <1 empty item>, 5 ]
> Array.from(array)
[ undefined, undefined, 3, undefined, 5 ]
> [...array]
[ undefined, undefined, 3, undefined, 5 ]

Array#concat と Array#slice

疎な配列をコピーする場合は Array#concat もしくは Array#slice を利用しましょう。

この二つのメソッドは疎の要素を維持したままコピーしてくれます。

> array = [,,3,,5]
[ <2 empty items>, 3, <1 empty item>, 5 ]
> array.concat()
[ <2 empty items>, 3, <1 empty item>, 5 ]
> array.slice()
[ <2 empty items>, 3, <1 empty item>, 5 ]

全く同じ構造の配列を得ることができましたね！

ループでの違い

次に疎な配列の要素を列挙したい場合、ループ方法による違いを見てみます。

for

まずは通常の for 文によるループです。

array = [, , , , 4]
for (let i = 0; i < array.length; i += 1) {
  console.log(array[i])
}
// > undefined
// > undefined
// > undefined
// > undefined
// > 4

配列の各要素へはインデックスを添え字としてアクセスをしますので、疎の要素に対しては前述の通り undefined が返ってきます。

for...in

続いて for...in 文によるループです。

array = [, , , , 4]
for (const v in array) {
  console.log(v)
}
// > 4

for...in では配列のプロパティを列挙する為、プロパティが存在しない疎な配列は列挙されません。in演算子 で true になるものだけ列挙する、という動作ですね。

for...of

続いて for...of 文によるループです。

array = [, , , , 4]
for (const v of array) {
  console.log(v)
}
// > undefined
// > undefined
// > undefined
// > undefined
// > 4

for...of では配列のイテレータを利用して要素を列挙するので、疎の要素も列挙されます。ただし要素として取り出された時点で undefined になります。

forEach

最後に forEach メソッドを使ったループです。

array = [, , , , 4]
array.forEach(v => console.log(v))
// > 4

forEach メソッドでは、存在する要素のみを列挙する為、疎の要素は列挙されません。

まとめると、for と for...of は疎の要素を列挙できて、for...in と forEach は疎の要素を列挙できませんでした。ただ列挙できるとされた for と for...of でも undefined との識別ができるかどうかは別問題であり、for...of ではインデックスが得られない為に識別ができません。1

for (const i of [, , , undefined, , , undefined, undefined]) {
  console.log(i)
}
// > undefined
// > undefined
// > undefined
// > undefined
// > undefined
// > undefined
// > undefined
// > undefined 全部undefinedになってしまう。

なので、疎の要素を列挙かつ識別までできるのはfor 文のみとなります。

表にするとこんな感じですね。

for for...in for...of forEach
疎の要素を列挙 できる できない できる できない
疎の要素の識別 できる できない できない できない

いまどきループなんてしたくない

そうですよね。map や filter などの高階関数を利用して配列の処理を行うほうがよりモダンな方法です。

しかし map も filter も reduce も forEach も疎の要素をスキップします。

// filter
> array = [,,,,4]
[ <4 empty items>, 4 ]
> array.filter(i => i)
[ 4 ]
> array.filter(i => !i)
[]  // 疎の要素は評価対象にならない

// map
> array.map(i => i)
[ <4 empty items>, 4 ]
> array.map(i => 'a')
[ <4 empty items>, 'a' ] // 疎の要素は処理されない

スキップされたら困るんか？

そもそも疎の要素を維持したまま扱いたいというケースがどれほどあるでしょうか？スキップしたり undefined に置き換えてしまっても多くの場合は問題ないのではないでしょうか。

ほとんどの場合、疎な配列であっても map や filter などそのまま利用して問題になることは無いでしょう。しかし疎な配列で map や filter した場合に疎の要素がスキップされることを、知っててやるのと知らないでやるのでは大きな違いがあります。予期せぬ結果を招かない為にも、これらの挙動を理解しておくことは重要です。

スキップされたら困るんや

どうしてもこれらのメソッドで疎の要素を扱いたい（認識したい）のであれば、密な配列（Dense Arrays、疎の要素を含まない配列です）で map を呼び出し、callback の中でインデックスを用いたアクセスをすることで疎の要素を扱うことができます。

const array = [, 1, 2, undefined, , 5]
Array.from(array).map(
  (value, index) => (index in array ? array[index] : 'sparse')
)
// > [ 'sparse', 1, 2, undefined, 'sparse', 5 ]

しかしこれでは非常に分かり辛いコードになってしまいますので、疎の要素をスキップしたくないという意図（逆に言うとこのような実装を行う必然性）をドキュメントやコメントで明確化するととても良いと思います。

疎の要素を作りたい

既に値が入っている要素を疎の要素に入れ替えたい場合や、既存の配列に疎の要素を追加したい場合などでそれぞれ方法があります。

delete

既存の要素を疎の要素に入れ替えたい場合はdeleteを使います。

> array = [1,2,3,4,5]
[ 1, 2, 3, 4, 5 ]
> delete array[2]
true
> array
[ 1, 2, <1 empty item>, 4, 5 ]

delete を使うとオブジェクトのプロパティを削除することができます。なので delete された要素はプロパティが無い状態、つまり疎の要素となります。

逆に疎の要素を作るつもりがないのに delete を使ってしまうと予期せぬ動作を招く危険があります。配列の要素を削除し、長さを詰めたい場合は shift、pop、splice を使いましょう。

length

既存の配列に疎の要素を追加したい場合はlength を拡張します。

> array = [1,2,3,4,5]
[ 1, 2, 3, 4, 5 ]
> array.length += 1
6
> array
[ 1, 2, 3, 4, 5, <1 empty item> ]

length プロパティを元の長さ以上に書き換えた時、配列はその長さまで拡張されますが、拡張された要素は全て疎の要素になります。

メソッド毎の動作の違い

Array のインスタンスメソッド別に疎な配列をどのように扱うかを見ていきたいと思います。

以下の分類は私が大まかなイメージで行ったものなので、詳細は個別に見てください。

ちゃんと見る系のメソッド

置換、連結といった操作を行うメソッドは、ちゃんと疎の要素を認識して動作します。また、一部の検索メソッドもここに含まれます。

concat

疎な配列を維持したまま連結してくれます。

> Array(2).concat([,,,])
[ <5 empty items> ]

copyWithin

疎の要素ごとシフトしてくれます。

> array = [,1,2,,4]
[ <1 empty item>, 1, 2, <1 empty item>, 4 ]
> array.copyWithin(1)
[ <2 empty items>, 1, 2, <1 empty item> ]

fill

ちゃんと指定した分だけ埋めてくれます。

> array = [,,,,4,]
[ <4 empty items>, 4 ]
> array.fill(0, 2)
[ <2 empty items>, 0, 0, 0 ]

indexOf

疎の要素は undefined として判定しないので、下記例の前者のように undefined で検索しても見つかりません。しかし要素としてはカウントされますので、後者のように見つかった場合のインデックスは正しいです。

> array = Array(5)
[ <5 empty items> ]
> array.indexOf(undefined)
-1

> array = [,,,,4,]
[ <4 empty items>, 4 ]
> array.indexOf(4)
4

lastIndexOf

indexOf と同じですね。後ろから検索するだけです。

> array = Array(5)
[ <5 empty items> ]
> array.lastIndexOf(undefined)
-1

> array = [,4,4,,4,]
[ <1 empty item>, 4, 4, <1 empty item>, 4 ]
> array.lastIndexOf(4)
4

join

疎の要素は空白として結合されます。

> array = [,,,,4,]
[ <4 empty items>, 4 ]
> array.join()
',,,,4'

keys

疎な配列でもちゃんとキーのイテレータが取得できます。

> array = Array(3)
[ <3 empty items> ]
> iterator = array.keys()
{}
> iterator.next()
{ value: 0, done: false }
> iterator.next()
{ value: 1, done: false }
> iterator.next()
{ value: 2, done: false }
> iterator.next()
{ value: undefined, done: true }

push

push する配列が疎な配列であっても関係ありません。追加できます。

> array = Array(3)
[ <3 empty items> ]
> array.push('A')
4
> array
[ <3 empty items>, 'A' ]

reverse

ちゃんと疎の要素ごとリバースされます。

> array = [,,,,4,]
[ <4 empty items>, 4 ]
> array.reverse()
[ 4, <4 empty items> ]

slice

疎の要素を無視せず切り取ってくれます。

> array = [,,,3,4,,]
[ <3 empty items>, 3, 4, <1 empty item> ]
> array.slice(2, 4)
[ <1 empty item>, 3 ]

sort

疎の要素もちゃんと並べ替えしてくれます。

> array = [, 8, , undefined, 4, , 7]
[ <1 empty item>, 8, <1 empty item>, undefined, 4, <1 empty item>, 7 ]
> array.sort()
[ 4, 7, 8, undefined, <3 empty items> ]

> array = [, 8, , undefined, 4, , 7]
[ <1 empty item>, 8, <1 empty item>, undefined, 4, <1 empty item>, 7 ]
> array.sort((x, y) => y - x)
[ 8, 7, 4, undefined, <3 empty items> ]

しかし疎の要素は全て末尾に追いやられるようです。条件を変えてやってみても全て末尾に移動します。

> array = [, 8, , undefined, 4, , 7]
> array.sort((x, y) => 1)
[ 4, 8, 7, undefined, <3 empty items> ]

> array = [, 8, , undefined, 4, , 7]
> array.sort((x, y) => 0)
[ 7, 8, 4, undefined, <3 empty items> ]

> array = [, 8, , undefined, 4, , 7]
> array.sort((x, y) => -1)
[ 7, 8, 4, undefined, <3 empty items> ]

splice

切り出す範囲に疎の要素が含まれる場合、戻り値は疎な配列になります。また、元の配列の疎の要素も維持されます。

> array = [,,,,4,]
[ <4 empty items>, 4 ]
> array.splice(3, 2, undefined)
[ <1 empty item>, 4 ]
> array
[ <3 empty items>, undefined ]

toLocaleString

疎の要素は単純に空白として出力されます。

> array = [,,undefined,null,'',5,]
[ <2 empty items>, undefined, null, '', 5 ]
> array.toLocaleString()
',,,,,5'

toString

toLocaleString と同様、空白として出力されます。

> array = [,,undefined,null,'',5,]
[ <2 empty items>, undefined, null, '', 5 ]
> array.toString()
',,,,,5'

unshift

疎な配列に unshift で要素を追加すると、疎の要素ごとシフトします。

> array = [,,,,4,]
[ <4 empty items>, 4 ]
> array.unshift(undefined)
6
> array
[ undefined, <4 empty items>, 4 ]

シカトする系のメソッド

ループや判定といった操作を行うメソッドは、疎の要素をスキップして動作します。

every

疎の要素は評価対象になりません。

> array = [,,,,4,]
[ <4 empty items>, 4 ]
> array.every(i => i)
true

> array.every(i => !i)
false

filter

疎の要素は評価対象になりませんので、戻り値の配列では全てカットされます。

> array = [,,,,4,]
[ <4 empty items>, 4 ]
> array.filter(i => i)
[ 4 ]
> array.filter(i => !i)
[]

forEach

これも同じ、疎の要素はスキップします。

> array = [,,,,4,]
[ <4 empty items>, 4 ]
> array.forEach(i => console.log(i))
4
undefined

map

これも疎の要素はスキップされますが、戻り値の配列は疎な配列で得ることができます。（つまりcallbackを通らないだけで、配列の長さや要素のインデックスは維持される）

> array = [,,,,4,]
[ <4 empty items>, 4 ]
> array.map(() => 'A')
[ <4 empty items>, 'A' ]

reduce

reduce も疎の要素自体がスキップされます。

> array = [,,,,4,]
[ <4 empty items>, 4 ]
> array.reduce((acc, cur, index) => { acc.push(index); return acc; }, [])
[ 4 ]

reduceRight

reduce と同じですね。逆から畳み込むというだけです。

> array = [,,,,4,]
[ <4 empty items>, 4 ]
> array.reduceRight((acc, cur, index) => { acc.push(index); return acc; }, [])
[ 4 ]

some

some も疎の要素を評価対象としません。

> array = [,,,,4,]
[ <4 empty items>, 4 ]
> array.some(i => i)
true
> array.some(i => !i)
false

undefined を返す系メソッド

要素を返すといった操作を行うメソッドは、疎の要素を認識していますが、疎の要素を返す時は undefined を返します2。

entries

疎の要素をちゃんと認識していますが、返される value は undefined です。

> array = [,,,,4,]
[ <4 empty items>, 4 ]
> iterator = array.entries()
{}
> iterator.next()
{ value: [ 0, undefined ], done: false }
> iterator.next()
{ value: [ 1, undefined ], done: false }
> iterator.next()
{ value: [ 2, undefined ], done: false }
> iterator.next()
{ value: [ 3, undefined ], done: false }
> iterator.next()
{ value: [ 4, 4 ], done: false }
> iterator.next()
{ value: undefined, done: true }

find

疎の要素を undefined として見ているから undefined が返ってきているのか、見つからなくて undefined を返しているのか、動作だけを見ても分からないです。

> array = [,,,,undefined,]
[ <4 empty items>, undefined ]
> array.find(v => v === undefined)
undefined

> Array(5).find(v => v === undefined)
undefined

ただ Polyfill を見る限り疎の要素も undefined として判定しているようです。（後述）

findIndex

疎の要素を undefined として検索を掛けます。なので以下の例では最初の疎の要素がヒットしています。

> array = [0,,,,undefined,]
[ 0, <3 empty items>, undefined ]
> array.findIndex(v => v === undefined)
1

includes

疎の要素は undefined として判定します。なので以下は true です。

> array = Array(5)
[ <5 empty items> ]
> array.includes(undefined)
true

pop

疎の要素もちゃんと pop してくれます。戻り値は undefined です。

> array = [,,,,4,,]
[ <4 empty items>, 4, <1 empty item> ]
> array.pop()
undefined
> array
[ <4 empty items>, 4 ]

shift

shift も pop と同様に疎の要素を undefined で返します。

> array = [,,,,4,]
[ <4 empty items>, 4 ]
> array.shift()
undefined
> array
[ <3 empty items>, 4 ]

indexOf(lastIndexOf) と find(findIndex)の違い

indexOf(lastIndexOf) と find(findIndex)は共に検索をするメソッドですが、前者は疎の要素を疎の要素のまま扱う（検索にヒットしない）のに対し、後者は疎の要素を undefiend として扱います。（検索にヒットする）

indexOf の Polyfill を見ると、値の比較をする箇所でプロパティ有無の判定を行っています。

if (k in t && t[k] === searchElement) {
  return k
}

しかし find の Polyfill では単純に要素を取得して判定しています。

var kValue = o[k]
if (predicate.call(thisArg, kValue, k, o)) {
  return kValue
}

ECMAScript の仕様書にもこの違いは記載されています。3

22.1.3.11 Array.prototype.indexOf ( searchElement [ , fromIndex ] )

  1. Repeat, while k<len
    a. Let kPresent be HasProperty(O, ToString(k)).

22.1.3.8 Array.prototype.find ( predicate [ , thisArg ] )

  1. Repeat, while k < len
    a. Let Pk be ToString(k).
    b. Let kValue be Get(O, Pk).

そういう仕様なんですね。

さいごに

疎な配列自体あまり身近ではないかもしれませんし、疎の要素も undefined も関係ねーよという場合がほとんどかもしれません。しかし疎な配列かどうかを意識したり、各メソッドがどのような挙動を取るかを知っておくことは、予期せぬ動作を防ぐためにも有益だと思います。

参考

もちろん keys()などを使ってインデックスでアクセスするようにすれば for...of でも疎の要素の識別は可能です。

  1. ↩

  2. というより undefined 以外返しようが無い ↩

  3. そりゃそうだ ↩

34
25
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
34
25

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?