配列の比較方法（ロジックを理解したいだけなので言語は特に問いません）

Question

実現したいこと

2つの多次元配列を比較し、配列の要素が一致していればtrueを返し、一致していなければfalseを返す関数の書き方について知りたいです

困っていること
純粋な配列であれば、比較する関数処理を書けるのですが、多次元配列のような配列の場合、どう比較し合う処理を書けば良いか分からずに困っています

function compare(a, b){
  // 処理を書いていくのだが分からない...
  return false;
}
// true
const arrA = ["C", "E", ["B", "D", ["A"]]];
const arrB = ["C", "E", ["B", "D", ["A"]]];
console.log(compare(arrA, arrB))
// false: BとCの位置が異なっているため
const arrC = ["C", "E", ["B", "D", ["A"]]];
const arrD = ["B", "E", ["C", "D", ["A"]]];
console.log(compare(arrC, arrD))
// false: Aが配列になっているかどうかを見ている
const arrE = ["C", "E", ["B", "D", ["A"]]];
const arrF = ["C", "E", ["B", "D", "A"]];
console.log(compare(arrE, arrF))

JSON.stringifyを使った解

// true
const arrA = ["C", "E", ["B", "D", ["A"]]];
const arrB = ["C", "E", ["B", "D", ["A"]]];
console.log(JSON.stringify(arrA) == JSON.stringify(arrB))
// res: true

// false: BとCの位置が異なっているため
const arrC = ["C", "E", ["B", "D", ["A"]]];
const arrD = ["B", "E", ["C", "D", ["A"]]];
console.log(JSON.stringify(arrC) == JSON.stringify(arrD))
// res: false

// false: Aが配列になっているかどうかを見ている
const arrE = ["C", "E", ["B", "D", ["A"]]];
const arrF = ["C", "E", ["B", "D", "A"]];
console.log(JSON.stringify(arrE) == JSON.stringify(arrF))
// res: false

JSON.stringifyを利用すると求めている解を出すことができますが、JSONにして配列が一致しているかどうかを見るだけだとロジックを考える上であまり勉強にはならないため、考え方のロジックについてご教示いただけると幸いです。

Comments

[miyabi_pudding]

配列の要素は、文字列のみですか？
数値や、オブジェクトを含む事はありますか？
（若干難易度変わる）

[nanase21]

現在の質問では、「文字列」のみで回答の条件は満たせますが、出来れば、「数値や、オブジェクト」を含む形でご教示いただけると幸いです。
なお、「JSON.stringify」を使用しない方法でご教示いただけると嬉しいです。

[tanat]

> なお、「JSON.stringify」を使用しない方法でご教示いただけると嬉しいです。

この条件とその理由を質問に追記して下さい。

要素をシリアライズしてから一致することを確認するのは多くの言語で使用できる汎用的な考え方であり、
JSON.stringifyで出来るのに何を困って質問してるの？となるとともに、JSON.stringifyでは出来ない何か隠された要件がある場合には回答が無駄になってしまいます。

[miyabi_pudding]

まず、ご自分でやってみたコードを記載してください。
今のままでは、丸投げになってしまっています。

[nanase21]

質問に質問の意図を追記してみましたが、引き続き考えてみます。

[tanat]

otnさんの回答にある、再帰の概念については把握されていますか？
もし把握されていないのであれば
`リスト 走査 再帰`あたりで調べてみると、otnさんの回答が理解しやすいかと思います。
次元が不定の多次元データ構造を走査/操作する際によく使われる方法で、言語を問わず使われる概念です（使えない言語もあるとは思いますが）

[nanase21]

＠tanatさん
再帰関数というものは知っているのですが使い方について理解できていない状況です...（一旦、otnさんのヒントを元にやってみたいと思います。）

[tanat]

状況と質問意図について把握しました。
補足ありがとうございます。
再帰は取っ付きにくいですが、今回の質問内容には必須かと思います。

[nanase21]

ありがとうございます。
関数内でLoopを回して、値がArrayだったら再帰関数を呼ぶようにして解決できました

[tanat]

（すみません、回答を見逃していたのでコメントを削除します）

Answer 1

compareの仕様としては、再帰呼び出しを使って、
・単純な値同士ならそれらが等しいか？
・リスト同士なら
・・長さが等しいか？
・・対応する要素同士全てについてcompareして等しいか？

#追記
これを読んで、そのままコードに出来ないとは思いませんでした。
言語問わないと言うことなので、Arrayかどうかの判断以外はArrayのメソッドは使わず。

function compare(a, b){
    if(Array.isArray(a) && Array.isArray(b)){
        if(a.length != b.length) return false;
        for(let i=0; i<a.length; i++){
            if(!compare(a[i],b[i])) return false;
        }
        return true;
    }else{
        return a === b;
    }
}

Comments

[nanase21]

ご教示いただきありがとうございます。
アドバイスを元に試してみます。

Answer 2

ロジック

配列の比較方法（ロジックを理解したいだけなので言語は特に問いません）

ロジックを理解したいなら、ロジックを書き出す事から始めてください。
(コードを書く必要はありません)

1. 型が不一致なら、return false
2. Symbol.toStringTag 値が不一致なら、return false
3. 対象がPrimitive型かつ値が不一致ならば、return false (NaN 値が存在しうるなら、Object.is())
4. 対象が配列(Array.isArray())かつ length プロパティ値が不一致ならば、return false
5. 対象が配列ならば、Array.prototypeforEach または for + hasOwnProperty で走査し、1-4を実行する(length値以下のindex値を持つ要素が全て存在しているならば、for-of を使用しても良い)
6. 全ての処理が完了したならば、return true

JSON.stringify()

JSON.stringifyを利用すると求めている解を出すことができますが、JSONにして配列が一致しているかどうかを見るだけだとロジックを考える上であまり勉強にはならないため、

JSON.stringify() のロジックは公式文書があります。

• 24.5.2 JSON.stringify - ECMAScript® 2020 Language Specification

Re: nanase21 さん

Comments

[nanase21]

ロジックのついての考え方について懇切にご教示いただきありがとうございました。
次回から、コードを書き出す前にロジックを書き出してからコードを考えるようにします。

Answer 3

再帰処理を使うといいかと。

function compare(a, b){
  if (
    a !== null &&
    b !== null &&
    (typeof a == 'object' && typeof b == 'object')
  ) {
    return Object.entries(a).every(aei => {
      // entriesは、オブジェクトデータ型をキー別に配列として返すメソッド。配列型も実行可能
      if (typeof b[aei[0]] == 'undefined') {
        // bにそもそもキーが存在しなければ、違うのでfalseを返す
        return false;
      } else {
        // オブジェクトの要素が両方配列かオブジェクト、関数の場合、再帰実行
        if (
          aei[1] !== null &&
          b[aei[0]] !== null &&
          (
            (typeof aei[1] == 'object' && typeof b[aei[0]] == 'object') ||
            (typeof aei[1] == 'function' && typeof b[aei[0]] == 'function')
          )
        ) {
          // オブジェクトか関数なので再帰
          return compare( aei[1], b[aei[0]]);
        }
        // プリミティブ値の場合、そのまま比較
        return aei[1] === b[aei[0]];
      }
    });
  } else if (typeof a == 'function' && typeof b == 'function') {
    // 両者が関数の場合は、単純に関数名を比較（細かくやるのはかなり複雑になる）
    return a.name == b.name;
  }

  return a === b;
}


const arrA = ["C", "E", ["B", "D", ["A"]]];
const arrB = ["C", "E", ["B", "D", ["A"]]];
console.log(compare(arrA, arrB))
// res: true

// false: BとCの位置が異なっているため
const arrC = ["C", "E", ["B", "D", ["A"]]];
const arrD = ["B", "E", ["C", "D", ["A"]]];
console.log(compare(arrC, arrD));
// res: false

// false: Aが配列になっているかどうかを見ている
const arrE = ["C", "E", ["B", "D", ["A"]]];
const arrF = ["C", "E", ["B", "D", "A"]];
console.log(compare(arrE, arrF));

一応オブジェクト型には対応してますが、
Map型（厳密には型ではない）などには対応していませんのであしからず。
（もっと処理複雑になります）

追記

関数に関しては、もっと比較せねばならないものが激増するため、関数名が一致するかどうかの比較に留めています。

また、配列はそもそもオブジェクトのため、オブジェクトかどうかを比較し、
再帰させるようにしました。
これにより、オブジェクトの入れ子などにも対応させています。

Comments

[nanase21]

ご教示いただきありがとうございます。
私の関数と比較しながら勉強させていただきます。

[think49]

- null値でTypeErrorを返す -> compare([null],[{}]);
- [undefined] と [] を区別できない
- 関数が「プリミティブ値同士なのでそのまま比較」の処理に含まれる(動作上は問題ありませんが、コメントが...)

細かい指摘ですが、null値のTypeErrorが特に気になりました。

typeof演算子には仕様バグがあります。
https://www.262.ecma-international.org/11.0/index.html#sec-typeof-operator
https://think49.hatenadiary.org/entry/20120114/1326554107
厳密な話をすれば、typeof演算子の評価値が既定外の文字列("foo" や "bar" など)でもObject型と見なすのが正解ですが、typeof演算子で実装するのは面倒なので、Object() で変換後の値と比較するのがお勧めです。

[miyabi_pudding]

ご指摘ありがとうございます！
修正やっていきます。

[miyabi_pudding]

think49さん >
修正し、null時のTypeErrorを解消できました。
typeofのバグ、非常に勉強になりました・・・。
ありがとうございます。

Answer 4

以下の関数でそれっぽく解決できました（条件3のみfalse返るはずがtrueでなってしまうのですが、一旦回答としては再帰関数を使ってやってみました）

function compare(a, b){
  for (let i = 0; i < arr1.length; i++) {
    if (Array.isArray(arr1[i])) {
      return compare(arr1[i], arr2[i])
    } else if (Array.isArray(arr2[i])) {
      return compare(arr1[i], arr2[i])
    } else if (arr1[i] != arr2[i]) {
      return false
    }
  }
  return true;
}

const arrE = ["C", "E", ["B", "D", ["A"]]];
const arrF = ["C", "E", ["B", "D", "A"]];
console.log(compare(arrE, arrF));

Comments

[think49]

BA回答の要件を満たしていないように思います。
https://jsfiddle.net/03qr8jwn/