多次元配列を比較したい

Question

発生している問題、目指している形

arr0=[["a",1], ["b",2], ["c",3]]
arr1=[["c",3], ["a",1], ["b",2]]
のような２次元配列があるときに、両者の配列は同じと判定するようにしたいです。

arr3=["a", "b", "c"]
arr4=["a", "b", "c"]
のような１次元で中身の順番が同じものではforやJSON等で比較し同じ配列と判定できたのですが、多次元、順不同の場合ではできませんでした。

ご教授お願いします。

Comments

[jun68ykt]

要件を確認させてください。
arr0=[["a",1], ["b",2], ["c",3]]
と
arr1=[["c",3], ["a",1], ["b",2]]
とを等しいと判定させたいことは分かりましたが、
arr0=[["a",1], ["b",2], ["c",3]]
と
arr2=[[3, "c"], [1, "a"], [2, "b"]]
も等しいと判定させたいのでしょうか？
つまり、「要素の順番が変わっていてもよい」というルールは、入れ子になっている子のほうの配列にも適用したいのでしょうか？

[jsrookie]

早速のコメントありがとうございます。

> つまり、「要素の順番が変わっていてもよい」というルールは、入れ子になっている子のほうの配列にも適用したいのでしょうか？

今のところは子の方の配列に適用する必要はないと考えています。
つまり、arr0とarr2は違う配列になります。
しかし、同じ配列と判定されても問題はないと考えていますので、jun68ykt様のやりやすい方でお答えいただけると幸いです。
よろしくお願いいたします。

[jun68ykt]

ご回答ありがとうございます。
了解しました。
とりあえず、

> 今のところは子の方の配列に適用する必要はないと考えています。

とのご趣旨に従って、子の配列については、要素の順序が違っていれば異なるものとするという考え方で、回答を書きました。参考になれば幸いです。

Answer 1

数が多くないなら、組み込みのJSON.stringifyとsortを使うという手もあります。
※数が多いとパフォーマンスとメモリがきついけど・・・

stringifyで中身の配列を文字列に固め、それをソートした配列を作って、さらにその配列をstringifyして比較します。こんな感じ。

function check(a, b) {
  const astr = a.map(v => JSON.stringify(v)).sort();
  const bstr = b.map(v => JSON.stringify(v)).sort();
  return JSON.stringify(astr) === JSON.stringify(bstr)
}

動くサンプルは以下です。
https://jsbin.com/mezekidigu/edit?js,console,output

注意点は、

• 内部配列内の順序は無視してます(する場合は、内部配列に対しても要素のstringfyとsortをやる)
• 内部配列内の型によっては、stringifyで形が変わる可能性がある(Dateとか)ので、型が問題ないか確認する。とりあえずstringとnumberしか使ってないなら問題ない。
• 前述したが、数が多いと遅いとかメモリ使い過ぎとかなる。(stringifyと配列コピー生成のコストが多い)

Comments

[jsrookie]

回答ありがとうございます。
自分ではできていませんが、私もJSONで挑戦していたのでとても勉強になります。
本当にありがとうございました！

Answer 2

こんにちは

lodash を使うとうまくやれそうと思ったので、lodash でこのような問題の解を求める質問を探したところ、以下がありました。

• stackoverflow.com: using lodash to compare arrays (items existence without order)

これのベストアンサー にある

_.isEqual(_.sortBy(array1), _.sortBy(array2))

が使えるのでは思います。以下、そのサンプルです。

• https://jsfiddle.net/jun68ykt/g98n34pL/4/

以上、参考になれば幸いです。

補足

上記の

_.isEqual(_.sortBy(array1), _.sortBy(array2))

について、 配列array1 と array2 の要素もまた配列で、その配列の要素は数値だったり文字列だったりと、型が一定していない状況で、_.sortBy の第２引数を与えないときに、どのようなソートになるのかが不明確だったので、少し調べてみましたが、「このようなソートになる」ということを明確に把握することは（今の時点では）できませんでした。

そこで、ランダムな内容の arr0 を作成し、これをシャッフルして arr1 を作り、

_.isEqual(_.sortBy(arr0), _.sortBy(arr1))

が常に true になる（と言ってもさしつかえない）かを試してみました。以下、試してみたコードです。

index.js

const _ = require('lodash')

const makeSubArry = () => {
  const len = _.sample([...Array(16)].map((e, i) => 5 + i));
  return [...Array(len)].map(e => {
    const type = _.sample(['bool', 'int', 'string', 'object']);
    switch(type) {
      case 'bool':
        return _.sample([true, false]);
      case 'int':
        return Math.floor(1000.0 * Math.random()) % 100
      case 'string':
        return _.sample('abcdefghijklmnopqrstuvwxyz'.split(''))
      case 'object':
        return _.sample([
          { x: 1, y: 2, z: 3 },
          { x: 10, y: 20  },
          { x: 11, z: 33 }
        ])
    }
  })
}

const LENGTH = 100;

let equalCount = 0;
let notEqualCount = 0;

const test = () => {
  const arr0 =  [...Array(LENGTH)].map(makeSubArry);

  for (let i=0; i < 10; i ++ ) {
    const arr1 = _.shuffle(arr0);
    const eq = _.isEqual(_.sortBy(arr0), _.sortBy(arr1));

    if (eq)
      equalCount ++;
    else
      notEqualCount ++;
  }
}

for (let i=0; i < 1000; i ++ ) {
  test();
}

console.log(`equalCount: ${equalCount}, notEqualCount: ${notEqualCount}`)

package.json

{
  "name": "q208845",
  "version": "0.0.1",
  "main": "index.js",
  "dependencies": {
    "lodash": "^4.17.15"
  }
}

上記のコードでは、以下の内容を一回の試行とし、これを１０００回、行います。

• arr0 を長さ100の配列として作る。
• arr0 の要素は以下を満たす配列

・長さが、5以上 20以下
・その要素は以下の a)〜 d)のいずれか
a) 真偽値（trueまたはfalse）
b) 0以上99以下の整数
c) 小文字のアルファベット1文字から構成される文字列
d) 以下の３つのうちいずれかのオブジェクト
{ x: 1, y: 2, z: 3 }
{ x: 10, y: 20 }
{ x: 11, z: 33 }

• 上記の arr0 をシャッフルして arr1 を作成する。
• arr0 と arr1 に対して

　　　const eq = _.isEqual(_.sortBy(arr0), _.sortBy(arr1));
を行い、eq の値が true になる回数と、 false になる回数をカウントする。

• 上記をひとつの arr0 に対して、10回行う。

期待している結果は、true になる回数が 1000 × 10 = 10000、 false になる回数がゼロというものでしたが、何回か実行してみたところ、期待どおりになりました。

Comments

[jsrookie]

前回に引き続き回答ありがとうございます。
海外で質問を探すのは盲点でした。
こんなに簡単にできるとは驚きです。
本当にありがとうございました！

[jun68ykt]

どういたしまして。

> １次元で中身の順番が同じものではforやJSON等で比較し同じ配列と判定できた

ということで、まず最も簡単なものについて、自作して作ることができたので、次に、

> 多次元、順不同

の比較に発展させようという試みは、大変よいと思います。ただ、

> １次元で中身の順番が同じもの

の比較が出来てからの次のステップとして、"多次元かつ順不同"　にいっぺんに行くのは、ちょっと欲張り過ぎたのかもしれません。（欲張りたい気持ちも分からなくはないのですけれども。）

なので、次は
　1) １次元のまま順不同での比較
と
　2) 順番は同じ比較で２次元
とを別々にやってみて、その後、1) かつ 2) すなわち、今回のご質問の課題をやってみるとよいかもしれません。（もうすでに 1) と 2) は出来ており楽勝だった、ということでしたらすみません）

さらに 2) の発展で、

　3) 順番は同じで n 次元

というのも挑戦しがいがあると思います。これらをやってくときに、配列の要素としては、とりあえずオブジェクトは除外するとよいでしょう。オブジェクトの比較が入ってくると途端に面倒になってきます。

２つの配列の内容が等しいかの判定、あるいは、２つのオブジェクトの内容が等しいとか判定するというコードを最も単純なところから初めて、徐々に汎用的にしていく作業を一度でも自作してみると、「何が来ても大丈夫」なものを作るのがいかに大変か分かります。そうすると「かなわぬ時の lodash 様頼み」ということになってきますので、lodash のドキュメント
https://lodash.com/docs
についても一度上から下まで、どんなメソッドがあるかざっと見ておくとよいかもしれません。
英語を正確に和訳しながら読めなくてもいいです。
逆にサンプルコードを読めば、どういうことをしてくれるメソッドかは大体分かるので、そこから逆に、
「こういうことをやることを、英語では ○○○というのか」
という感じで、メソッドによる効果と英語がつながってきて、すばやく有用な情報にたどりつける検索キーワードでググれるようになってきます。

今回のご質問の課題だと

lodash compare two arrays

といったキーワードでGoogle検索すると、キーワードが適切なら、Stackoverflow の投稿がヒットします。（今回の回答員挙げた Stackoverflow の投稿も検索結果上位に出てくると思います。）その中で、多くのGood がついている回答をありがたく拝借しましょう。

まとめますと

・ある程度のところまでは自分で書ける。（これは前提）

・楽勝で書けたコードを踏み台にして、さらに汎用的なものを自作しようとして大変だった。
　どこがどう大変になるかも分かった。

・その上で lodash のような便利なものを使いこなせる。

というのが望ましいかと思います。

上記３点目の「使いこなす」とは、どんなメソッドがあるかを暗記するのではなく、自分のやりたいことを端的に表す英文を作るか、英文になっていなくても、英単語を並べてググって、有用な情報に素早くたどり着いて、そこに書いてあることを自分の課題に適用できる、というような意味です。