2023年2月9日

配列

オブジェクトを使用すると、キー付きの値のコレクションを格納することができます。

しかし、実際には多くの頻度で 順序付されたコレクション が必要であることがわかります。それは、1つ目、2つ目、3つ目… と言った要素であり、例えばユーザ、商品、HTML要素など何かのリストを格納します。

ここでオブジェクトを使うのは便利ではありません。なぜなら、オブジェクトには要素の順序を管理するためのメソッドは提供されていないからです。既存のリストの “間に” 新しいプロパティを挿入することはできません。オブジェクトはこのように使うものではありません。

順序付けされたコレクションを格納するために、Array と呼ばれる特別なデータ構造があります。

宣言

空の配列を作る2つの構文があります:

let arr = new Array();
let arr = [];

ほぼすべてのケースで2つ目の構文が使われます。角括弧の中に初期値となる要素を指定することができます:

let fruits = ["Apple", "Orange", "Plum"];

配列要素はゼロから始まる番号が付けられます。

角括弧にその番号を指定することで、該当する要素を取得することができます:

let fruits = ["Apple", "Orange", "Plum"];

alert( fruits[0] ); // Apple
alert( fruits[1] ); // Orange
alert( fruits[2] ); // Plum

要素の置き換えも可能です:

fruits[2] = 'Pear'; // now ["Apple", "Orange", "Pear"]

…もしくは、配列に新しいものを追加することもできます:

fruits[3] = 'Lemon'; // now ["Apple", "Orange", "Pear", "Lemon"]

配列内の要素の総数は、その length で取得できます:

let fruits = ["Apple", "Orange", "Plum"];

alert( fruits.length ); // 3

alert を使うことで、すべての配列を表示することも可能です。

let fruits = ["Apple", "Orange", "Plum"];

alert( fruits ); // Apple,Orange,Plum

配列はどんな型の要素も格納することができます。

例:

// 値の混在
let arr = [ 'Apple', { name: 'John' }, true, function() { alert('hello'); } ];

// インデックス 1 のオブジェクトを取得し、その名前を表示
alert( arr[1].name ); // John

// インデックス 3 の関数を取得し、実行
arr[3](); // hello
末尾のカンマ

配列は、オブジェクトのようにカンマで終わる場合があります:

let fruits = [
  "Apple",
  "Orange",
  "Plum",
];

すべての行が同じようになるので、“末尾のカンマ” は項目の挿入や削除が容易になります。

pop/push, shift/unshift メソッド

キュー(queue) は配列で最も一般的に使われるものの1つです。コンピュータ・サイエンスでは、これは2つの操作をサポートする要素の順序付きコレクションを意味します。:

  • push は要素を末尾に追加します。
  • shift は最初から要素を取得し、2番目の要素が1番目になるようにキューを進めます。

配列は両方の操作をサポートします。

実践では、非常に頻繁にこれを見ます。例えば画面に表示が必要なメッセージのキューです。

配列の別のユースケースもあります – スタック(stack) と呼ばれるデータ構造です。

これは2つの操作をサポートします。

  • push は要素を末尾に追加します.
  • pop は末尾から要素を取り出します。

なので、新しい要素は常に “末尾” から追加または取得されます。

スタックは、通常カードのパックとして例えられます。新しいカードが上に追加されるか、カードが上から取り出されます:

スタックの場合、最新のプッシュされたアイテムが最初に受け取られます。これはLIFO(Last-In-First-Out)の原則とも呼ばれます。 キューの場合、FIFO(First-In-First-Out)があります。

JavaScriptの配列は、キューとスタックどちらとしても動作します。これらの要素を使用すると、要素を先頭または最後に追加/削除することができます。

コンピュータサイエンスでは、それを許可するデータ構造を両端キュー/デック(deque)と呼びます。

配列の末尾で動作するメソッド:

pop

配列の最後の要素を抽出して返します。:

let fruits = ["Apple", "Orange", "Pear"];

alert( fruits.pop() ); // "Pear" を削除し alert する

alert( fruits ); // Apple, Orange
push

配列の末尾に要素を追加します。:

let fruits = ["Apple", "Orange"];

fruits.push("Pear");

alert( fruits ); // Apple, Orange, Pear

fruits.push(...) 呼び出しは fruits[fruits.length] = ... と同じです。

配列の先頭で動作するメソッド:

shift

配列の先頭の要素を抽出して返します。:

let fruits = ["Apple", "Orange", "Pear"];

alert( fruits.shift() ); // Apple を削除し alert する

alert( fruits ); // Orange, Pear
unshift

配列の先頭に要素を追加します。:

let fruits = ["Orange", "Pear"];

fruits.unshift('Apple');

alert( fruits ); // Apple, Orange, Pear

メソッド pushunshift は一度に複数の要素を操作することができます:

let fruits = ["Apple"];

fruits.push("Orange", "Peach");
fruits.unshift("Pineapple", "Lemon");

// ["Pineapple", "Lemon", "Apple", "Orange", "Peach"]
alert( fruits );

内部詳細

配列は特別な種類のオブジェクトです。プロパティ arr[0] にアクセスするために使う角括弧は、実際にはオブジェクト構文から来ています。数字がキーとして使用されます。

配列はデータの順序付きコレクションと、length プロパティを処理する特別なメソッドを提供するようオブジェクトを拡張します。しかし、コアではまだオブジェクトです。

JavaScriptには7つの基本タイプしかないことに注意してください。 配列はオブジェクトであるため、オブジェクトのように動作します。

例えば、これは参照としてコピーされます:

let fruits = ["Banana"]

let arr = fruits; // 参照によるコピー (2つの変数は同じ配列を参照する)

alert( arr === fruits ); // true

arr.push("Pear"); // 参照から配列を変更する

alert( fruits ); // Banana, Pear - 2 つの項目になっています

…しかし配列を本当に特別にするのは、その内部表現です。エンジンは、このチャプターの図に示されているように連続したメモリ領域に要素を格納しようとします。そして配列を非常に高速にするために、他の最適化も行われます。

しかし、“順序付けられたコレクション” として配列を処理するのをやめ、普通のオブジェクトのように扱い始めると、それらはすべて壊れます。

例えば、技術的にはこうすることもできます:

let fruits = []; // 配列を作ります

fruits[99999] = 5; // その length よりも非常に大きなインデックスでプロパティを割り当てます

fruits.age = 25; // 任意の名前でプロパティを作成します

配列のベースはオブジェクトなので、これは可能です。任意のプロパティを追加することができます。

しかし、エンジンは我々が配列を通常のオブジェクトとして処理していることを知るでしょう。配列固有の最適化は、このような場合には適しておらず無効になります。その利点は消えます。

配列の誤った使い方:

  • arr.test = 5 のように非数値プロパティを追加する。
  • 穴を作る: arr[0] を追加した後、arr[1000] を追加する(その間は無し)。
  • 逆順で配列を埋める: arr[1000], arr[999] など。

順序付きデータ を処理するための特別な構造として配列があると考えてください。配列はそのための特別なメソッドを提供します。配列は連続した順序付きデータを処理するため、JavaScriptエンジン内部で注意深くチューニングされています。このために配列を使ってください。そして、任意のキーが必要なときは、通常のオブジェクト {} が必要な可能性が高いです。

パフォーマンス

メソッド push/pop は処理が速く、shift/unshift は遅いです。

なぜ、配列の最初よりも最後を処理する方が速いのでしょうか?実行中起こっている事を見てみましょう:

fruits.shift(); // 先頭から1要素を取る

数値 0 の要素を取得して削除するだけでは不十分です。他の要素も同様に番号をつけ直す必要があります。

shift 操作は3つのことをしなければなりません:

  1. インデックス 0 の要素を削除します。
  2. 全ての要素を左に移動させます。インデックス 1 から 02 から 1 と言うように番号をつけ直します。
  3. length プロパティを更新します。

配列内の要素が増えれば増えるほど、移動に必要な時間とメモリ内の操作が増えます。

unshift でも似たようなことが起きます: 配列の先頭に要素を追加しますが、最初に存在する要素を右に移動させる必要があり、それらのインデックスを増やします。

そして、push/pop はどうでしょう?それらは何も移動させる必要がありません。末尾から要素を抽出するため、pop メソッドはインデックスを消去し、length を短くするだけです。

pop 操作のアクション:

fruits.pop(); // 末尾から1要素取る

他の要素のインデックスは変わらないので、pop メソッドは何も移動させる必要はありません。そのため非常に高速です。

push メソッドも同じです。

ループ

配列アイテムを循環させる最も古い方法の1つは、インデックス上の for ループです:

let arr = ["Apple", "Orange", "Pear"];

for (let i = 0; i < arr.length; i++) {
  alert( arr[i] );
}

しかし、配列のための for..of という別のループの形式があります:

let fruits = ["Apple", "Orange", "Plum"];

// 配列要素の反復処理
for (let fruit of fruits) {
  alert( fruit );
}

for..of は現在の要素の番号へアクセスすることはできず、単に値のみです。しかし、殆どのケースではそれで十分です。また、より短い構文です。

技術的には、配列はオブジェクトなので for..in を利用することもできます:

let arr = ["Apple", "Orange", "Pear"];

for (let key in arr) {
  alert( arr[key] ); // Apple, Orange, Pear
}

しかし、実際にこれは良くないアイデアです。そこには潜在的な問題があります:

  1. ループ for..in は数値のものだけでなく、 全てのプロパティ を繰り返し処理します。

    ブラウザや他の環境では 配列のように見える いわゆる “配列のような” オブジェクトがあります。つまり、それらは length とインデックスプロパティを持っています。しかし、それらは通常は必要のない他の非数値プロパティやメソッドも持っています。for..in ループはそれらもリストします。なので、もし配列のようなオブジェクトを処理する必要があるとき、それらの “余分な” プロパティが問題になる場合があります。

  2. for..in ループは配列ではなく、汎用オブジェクトに対して最適化されているため、10から100倍遅くなります。もちろんそれでもとても速いです。高速化はボトルネックの場合にのみ問題なり、それ以外ではさほど重要でないこともあります。しかしそれでも私たちは違いに気をつけるべきです。

一般的に、配列に対しては for..in は使うべきではありません。

“length” について

配列を変更したとき、length プロパティは自動的に更新されます。正確には、それは配列の実際の値の数ではなく、最大の数値インデックスに1を加えたものです。

例えば、大きなインデックスの1つの要素は大きなlengthを返します:

let fruits = [];
fruits[123] = "Apple";

alert( fruits.length ); // 124

通常、そのように配列を使わないことに注意してください。

length プロパティの別の興味深い点は、書き込み可能と言う点です。

手動で増やした場合、面白いことは起きません。しかし、それを減らしたとき、配列は切り捨てられます。この処理は不可逆です。これはその例です:

let arr = [1, 2, 3, 4, 5];

arr.length = 2; // 2つの要素に切り捨てる
alert( arr ); // [1, 2]

arr.length = 5; // length を戻す
alert( arr[3] ); // undefined: 値は返ってきません

なので、配列をクリアする最もシンプルな方法は arr.length = 0; です。

new Array()

配列を作るもう1つの構文があります:

let arr = new Array("Apple", "Pear", "etc");

角括弧 [] がより短く書けるので、ほとんど使われません。また、トリッキーな特徴があります。

もし数値の1つの引数で new Array が呼ばれたとき、アイテムはありませんが、与えられた長さを持った 配列が作られます。

それがどのように墓穴を掘るか見てみましょう:

let arr = new Array(2); // [2] の配列を作成しますか?

alert( arr[0] ); // undefined! 要素がありません.

alert( arr.length ); // length は 2 です

このような驚きを避けるため、何をしているのか本当に分かっていない限り、通常は角括弧を使います。

多次元配列

配列は配列も持つことができます。我々は行列を格納するために、それを多次元配列として使うことができます。:

let matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];

alert( matrix[1][1] ); // 中央の要素

toString

配列は、要素のカンマ区切りのリストを返す独自の toString メソッドの実装を持ってます。

例:

let arr = [1, 2, 3];

alert( arr ); // 1,2,3
alert( String(arr) === '1,2,3' ); // true

もしくは、これを試してみましょう:

alert( [] + 1 ); // "1"
alert( [1] + 1 ); // "11"
alert( [1,2] + 1 ); // "1,21"

配列は Symbol.toPrimitive を持っておらず、valueOf もなく、toString 変換のみを実装しているため、ここでは [] は空文字列になり、[1]"1" に、[1,2]"1,2" になります。

二項演算子プラス "+" が文字列に何かを加えたとき、同様に文字列に変換します。なので、その次のステップはこのように見えます:

alert( "" + 1 ); // "1"
alert( "1" + 1 ); // "11"
alert( "1,2" + 1 ); // "1,21"

配列を == で比較しないでください

JavaScript の配列は他のプログラミング言語とは異なり、== 演算子で比較すべきではありません。

この演算子は配列に対して特別な扱いせず、他のオブジェクトと同様に動作します。

ルールを思い出してみましょう:

  • 2つのオブジェクトは、同じオブジェクトを参照しているときにだけ、等価 == です。
  • == の引数の一方がオブジェクトで、もう一方がプリミティブの場合、オブジェクトはチャプター オブジェクトからプリミティブへの変換 で説明したように、プリミティブに変換されます。
  • …互いに == で等価である nullundefined を除いては、他には何もありません。

厳密比較 === は、型変換をしないためよりシンプルです。

なので、== で配列を比較する場合、全く同じ配列を参照している2つの変数を比較しない限り、決して等価にはなりません。

例:

alert( [] == [] ); // false
alert( [0] == [0] ); // false

これらの配列は技術的には異なるオブジェクトです。したがって、等しくはなりません。== 演算子は要素毎の比較は行いません。

プリミティブとの比較では、以下のように、一見すると奇妙な結果がでることがあります:

alert( 0 == [] ); // true

alert('0' == [] ); // false

ここでは、両方のケースで配列オブジェクトとプリミティブを比較しています。なので、配列 [] は比較のためにプリミティブに変換され、空文字 '' になります。

次に、チャプター 型変換 で説明されているように、比較のプロセスがプリミティブで続行されます。

// [] の変換後は '' です
alert( 0 == '' ); // true, '' は数値 0 に変換されるため

alert('0' == '' ); // false, 型変換はされません、異なる文字列です

では、どうやって配列を比較しましょう?

簡単です: == 演算子を使いません。代わりにループや次のチャプターで説明するイテレーションメソッドを使用して比較します。

サマリ

配列はオブジェクトの特別な種類であり、順序付けされたデータ項目を格納するのに適しています。

  • 宣言:

    // 角括弧 (通常)
    let arr = [item1, item2...];
    
    // new Array (例外的、ほとんど使われません)
    let arr = new Array(item1, item2...);

    new Array(number) への呼び出しは与えられた長さの配列を作りますが、要素を持ちません。

  • length プロパティは配列の長さです。正確にはその最後の数値インデックスに1を加えたものです。それは配列のメソッドにより、自動的に調整されます。

  • もし手動で length を短くした場合、配列は切り捨てられます。

以下の操作で配列を両端キュー(deque)として使用できます。:

  • push(...items)items を末尾に追加します。
  • pop() は末尾の要素を削除し、それを返します。
  • shift() は先頭の要素を削除し、それを返します。
  • unshift(...items) はアイテムを先頭に追加します。

配列の要素をループするために:

  • for (let i=0; i<arr.length; i++) – 最も速く動作し、古いブラウザ互換です。
  • for (let item of arr) – アイテムだけのための、現代の構文です。
  • for (let i in arr) – 決して使いません。

配列を比較するには、== 演算子(>, < なども同様)は使用しません。これらは配列に対して特別な処理はしません。単にオブジェクトとして扱い、それは通常期待することではありません。

代わりに、配列を要素毎に比較するために for..of ループが使用できます。

私たちは、チャプター 配列のメソッド で配列に戻り、追加、削除、要素の抽出や配列のソートと言ったより多くのメソッドを学びます。

タスク

重要性: 3

このコードはどのように表示されますか?

let fruits = ["Apples", "Pear", "Orange"];

// 新しい値を "コピー" へプッシュ
let shoppingCart = fruits;
shoppingCart.push("Banana");

// fruits の中身は何?
alert( fruits.length ); // ?

結果は 4 です:

let fruits = ["Apples", "Pear", "Orange"];

let shoppingCart = fruits;

shoppingCart.push("Banana");

alert( fruits.length ); // 4

配列はオブジェクトです。なので shoppingCartfruits は同じ配列への参照です。

重要性: 5

5つの配列操作をしてみましょう。

  1. アイテム “Jazz” と “Blues” を持つ配列 styles を作ります。
  2. 末尾に “Rock-n-Roll” を追加します。
  3. 中央の値を “Classics” で置換します。中央値を見つけるコードは奇数の長さの配列で動作する必要があります。
  4. 配列の最初の値を外して表示します。
  5. 配列の先頭に RapReggae を追加します。

処理中の配列はこのようになります:

Jazz, Blues
Jazz, Bues, Rock-n-Roll
Jazz, Classics, Rock-n-Roll
Classics, Rock-n-Roll
Rap, Reggae, Classics, Rock-n-Roll
let styles = ["Jazz", "Blues"];
styles.push("Rock-n-Roll");
styles[Math.floor((styles.length - 1) / 2)] = "Classics";
alert( styles.shift() );
styles.unshift("Rap", "Reggie");
重要性: 5

結果は何でしょうか?それはなぜでしょう?

let arr = ["a", "b"];

arr.push(function() {
  alert( this );
})

arr[2](); // ?

呼び出し arr[2]() は、構文的には古き良き obj[method]() であり、arrobj の役割を、2method の役割を持っています。

従って、arr[2] の関数をオブジェクトメソッドとして呼び出します(訳注: arr[2] には function() { alert( this ); }push されています)。当然のことながら、この関数はオブジェクト arr を参照している this を受け取るため、配列 arr を出力します。:

let arr = ["a", "b"];

arr.push(function() {
  alert( this );
})

arr[2](); // "a","b",function

配列は 3つの値をもっています: 初期に2つを持っているのに加えて、関数です。

重要性: 4

次のような関数 sumInput() を書きなさい:

  • 値に関して、prompt を使ってユーザに訪ね、配列にその値を格納します。
  • ユーザが非数値、空文字、または “キャンセル” を選択したとき、数値を尋ねるのを終了します。
  • 配列のアイテムを計算し、合計を返します。

P.S. ゼロ 0 は有効な数値です。ゼロで入力をストップしないでください。

デモを実行

些細ですが重要な解法の詳細に注意してください。私たちは、prompt のあと、すぐに value を数値に変換しません。なぜなら、value = +value の後に、ゼロ(有効数字)と空の文字列(停止のサイン)を区別することができないからです。私たちは後ほど代わりにそれを行います。

function sumInput() {

  let numbers = [];

  while (true) {

    let value = prompt("A number please?", 0);

    // should we cancel?
    if (value === "" || value === null || !isFinite(value)) break;

    numbers.push(+value);
  }

  let sum = 0;
  for (let number of numbers) {
    sum += number;
  }
  return sum;
}

alert( sumInput() );
重要性: 2

入力は数値の配列です。e.g. arr = [1, -2, 3, 4, -9, 6].

タスクは次の通りです: アイテムの最大合計で arr の連続した部分配列を探します。

そのような返却をする関数 getMaxSubSum(arr) を書いてください。

例えば:

getMaxSubSum([-1, 2, 3, -9]) = 5 (ハイライトされたアイテムの合計)
getMaxSubSum([2, -1, 2, 3, -9]) = 6
getMaxSubSum([-1, 2, 3, -9, 11]) = 11
getMaxSubSum([-2, -1, 1, 2]) = 3
getMaxSubSum([100, -9, 2, -3, 5]) = 100
getMaxSubSum([1, 2, 3]) = 6 (すべて)

もしすべてのアイテムが負値の場合、何も取らないことを意味します(サブ配列は空)、なので合計はゼロです:

getMaxSubSum([-1, -2, -3]) = 0

早い解法を考えてみてください。: 可能なら O(n2) もしくは O(n) です。

テストと一緒にサンドボックスを開く

遅い解法

すべての可能性のあるサブ合計を計算することができます。

最もシンプルな方法はすべての要素を取り、それから始まるすべてのサブ配列の合計を計算することです。

例えば、 [-1, 2, 3, -9, 11] に対しては:

// -1 から開始:
-1
-1 + 2
-1 + 2 + 3
-1 + 2 + 3 + (-9)
-1 + 2 + 3 + (-9) + 11

// 2 から開始:
2
2 + 3
2 + 3 + (-9)
2 + 3 + (-9) + 11

// 3 から開始:
3
3 + (-9)
3 + (-9) + 11

// -9 から開始
-9
-9 + 11

// -11 から開始
-11

コードは実際には入れ子のループです: 配列要素に対する外部ループ、および現在の要素で始まる内部カウントのサブ合計です。

function getMaxSubSum(arr) {
  let maxSum = 0; // もし要素を取らない場合、ゼロが返却されます

  for (let i = 0; i < arr.length; i++) {
    let sumFixedStart = 0;
    for (let j = i; j < arr.length; j++) {
      sumFixedStart += arr[j];
      maxSum = Math.max(maxSum, sumFixedStart);
    }
  }

  return maxSum;
}

alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100

この解法は O(n2) の時間の複雑さを持っています。言い換えると、もし配列のサイズが2倍に増加すると、アルゴリズムは4倍長くなります。

大きな配列(1000, 10000 またはより多くのアイテム)に対しては、このようなアルゴリズムは深刻なレベルで低速になる可能性があります。

早い解法

配列を歩いて変数 s に現在の要素の部分合計を持ちましょう。s がある点で負になる場合は s=0 を代入します。このような s の最大値が答えになります。

説明にあまりピンとこない場合は、コードを参照してください、それは十分短いです:

function getMaxSubSum(arr) {
  let maxSum = 0;
  let partialSum = 0;

  for (let item of arr) { // for each item of arr
    partialSum += item; // add it to partialSum
    maxSum = Math.max(maxSum, partialSum); // remember the maximum
    if (partialSum < 0) partialSum = 0; // zero if negative
  }

  return maxSum;
}

alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100
alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([-1, -2, -3]) ); // 0

このアルゴリズムは1回の配列ループを必要とするので、時間複雑度は O(n) です。

あなたはここで、このアルゴリズムについてのより詳細な情報を見つけることができます: Maximum subarray problem. もしも、なぜそれが動作するのかがまだはっきりしていない場合は、上の例のアルゴリズムをトレースして、どのように動作するかを見てください。それはどんな言葉よりも優れています。

function getMaxSubSum(arr) {
  let maxSum = 0;
  let partialSum = 0;

  for (let item of arr) {
    partialSum += item;
    maxSum = Math.max(maxSum, partialSum);
    if (partialSum < 0) partialSum = 0;
  }
  return maxSum;
}

サンドボックスでテストと一緒に解答を開く

チュートリアルマップ

コメント

コメントをする前に読んでください…
  • 自由に記事への追加や質問を投稿をしたり、それらに回答してください。
  • 数語のコードを挿入するには、<code> タグを使ってください。複数行の場合は <pre> を、10行を超える場合にはサンドボックスを使ってください(plnkr, JSBin, codepen…)。
  • 記事の中で理解できないことがあれば、詳しく説明してください。