ある配列が別の配列の部分配列になっているか判定する【javascript】

概要

ある配列が別の配列の部分配列になっていることを判定する関数を作りました。
例えば、[1,2]は[1,2,3,4]の部分配列になっているので、そういうときにtrueを返すことを目指しました。

(追記)今のところ最適と思われる実装

だいぶ長くなってしまったので、冒頭に結論だけまとめます。(@akebi_mh さまのコメントをかなり参考にさせていただきました。ありがとうございました）

リストや配列が要素になることを考慮しない場合

forを２重に回して、arrayの部分配列とsubarrayを1要素ずつ比較していきます。

function isSubarray3(subarray, array){
  //subarrayが空のとき常にtrue
  if(subarray.length == 0)return true;
  //subarrayがarrayよりも長いとき、常にfalse
  if(subarray.length > array.length)return false;

  for(let i=0;i<array.length - subarray.length + 1; i++){
    for(let j=0;j<subarray.length;j++){
      if(array[i+j]!=subarray[j]) break;
      if(j == subarray.length-1) return true;
    }
  }
  return false;
}

console.log(isSubarray3([1,2],[1,2,3,4]));//true
console.log(isSubarray3([1,3],[1,2,3,4]));//false
console.log(isSubarray3([1],[1,2,3,4]));//true
console.log(isSubarray3([1],[12,2,3,4]));//false
console.log(isSubarray3([],[12,2,3,4]));//true。subarrayが空のときは常にtrueです
console.log(isSubarray3("12","1234"));//true。subarrayとarrayが両方stringのときは一応機能します。
console.log(isSubarray3("1,2", [1,2,3,4]));//false。subarrayがstringでarrayがlistのときはfalseになります。
console.log(isSubarray3([1,2],["1,2",3,4]));//false

リストや連想配列が要素になることを考慮する場合

リストのリストや連想配列のリストなどにも対応したい場合には、上記関数では不十分です(配列同士の比較は参照先の比較になってfalseになるため)。
そこで、再帰関数を使って、深い要素を持つ配列も比較できるようにします。

function typeOf(obj) {
    return Object.prototype.toString.call(obj).slice(8, -1).toLowerCase();
}

function isSameObject(object1, object2){
    const type1 = typeOf(object1);
    const type2 = typeOf(object2);
    if(type1 != type2)return false;
    if(["undefined","null","boolean","number","string"].includes(type1)){
        return object1 == object2;
    }else if(type1 == "array"){
        if(object1.length != object2.length)return false;
        for(let i=0;i<object1.length;i++){
            if(!isSameObject(object1[i], object2[i]))return false;
        }
        return true;
    }else if(type1 == "object"){
        if(object1.length != object2.length)return false;
        for(let k in object1){
            if(k in object2 == false) return false;
            if(!isSameObject(object1[k], object2[k]))return false;
        }
        return true;
    }else{//mapとかsetとかsymbolとか
        console.log("warning: unsupposed type", type1, "is detected!");
        return object1 === object2;
    }
}
function isSubarray7(subarray, array){
    if(subarray.length == 0) return true;
    if(subarray.length > array.length) return false;
    for(let i=0; i<array.length - subarray.length + 1; i++) {
        for(let j=0; j<subarray.length;j++){
            if(!isSameObject(subarray[j],array[i+j]))break;
            if(j == subarray.length-1) return true;
        }
    }
    return false;
}

console.log(isSubarray7([[5,6],7],  [1,2,3,4,[5,6],7,8,[9,10]])); // true
console.log(isSubarray7([[6],7],    [1,2,3,4,[5,6],7,8,[9,10]])); // false
console.log(isSubarray7([8,9,10],   [1,2,3,4,[5,6],7,8,[9,10]])); // false
console.log(isSubarray7([8,[9,10]], [1,2,3,4,[5,6],7,8,[9,10]])); // true
console.log(isSubarray7([8,{9:[10,1]}], [1,2,3,4,[5,6],7,8,{9:[10,1]}])); // true

おまけ

以下、試行錯誤の過程としていろいろ思いついたやり方を残しておきます。

JSON.stringifyしてからincludes

まず最初に思いついたのは、JSON.stringifyで文字列に直してから、includeで判定する方法です。
厳密に部分文字列のときだけtrueを返すようにはなっていないので注意が必要です。

//subarrayがarrayの部分配列になっているか判定する
function isSubarray(subarray, array){
  //subarrayの長さが1のときはincludeで判定する
  if(subarray.length == 1){
    return array.includes(subarray[0]);
  }
  //subarrayの長さが1以上のとき、json文字列に直して比較する
  let subarray_str = JSON.stringify(subarray).slice(1,-1);//前後のカッコを除くためsliceする
  let array_str = JSON.stringify(array).slice(1,-1);//前後のカッコを除くためsliceする

  return array_str.includes(subarray_str);
}

console.log(isSubarray([1,2],[1,2,3,4]));//true
console.log(isSubarray([1,3],[1,2,3,4]));//false
console.log(isSubarray([1],[1,2,3,4]));//true
console.log(isSubarray([1],[12,2,3,4]));//false
console.log(isSubarray([],[12,2,3,4]));//true。subarrayが空のときは常にtrueです
console.log(isSubarray("12","1234"));//true。subarrayとarrayが両方stringのときは一応機能します。
console.log(isSubarray("1,2", [1,2,3,4]));//true。引数がlistじゃないときは正しく機能しません
console.log(isSubarray([1,2],["1,2",3,4]));//true。意地悪な配列を考えると誤った結果を返させる事ができるので注意してください。

先頭が一致する部分配列を見つけてから、JSON.stringifyで比較

より厳密に判定したい場合は、subarrayの最初の要素がarrayに含まれているかをまず確認し、含まれていればその位置から、subarrayの長さだけsliceしたarrayの部分配列とsubarrayを比較するとよいです。

function isSubarray2(subarray, array){
  //subarrayが空のとき常にtrue
  if(subarray.length == 0)return true;
  //subarrayがarrayよりも長いとき、常にfalse
  if(subarray.length > array.length)return false;

  let subarray_str = JSON.stringify(subarray);

  for(let i=0;i<array.length - subarray.length + 1; i++){
    if(array[i]!=subarray[0])continue;
    //もしsubarray[0]と同じ文字があれば、そこからsubarray長さ分だけsliceして比較
    let array_str = JSON.stringify(array.slice(i,i+subarray.length));
    if(subarray_str == array_str) return true;    
  }
  return false;
}
console.log(isSubarray2([1,2],[1,2,3,4]));//true
console.log(isSubarray2([1,3],[1,2,3,4]));//false
console.log(isSubarray2([1],[1,2,3,4]));//true
console.log(isSubarray2([1],[12,2,3,4]));//false
console.log(isSubarray2([],[12,2,3,4]));//true。subarrayが空のときは常にtrueです
console.log(isSubarray2("12","1234"));//true。subarrayとarrayが両方stringのときは一応機能します。
console.log(isSubarray2("1,2", [1,2,3,4]));//false。subarrayがstringでarrayがlistのときはfalseになります。
console.log(isSubarray2([1,2],["1,2",3,4]));//false

JSON.stringifyせずに要素ごと比較

あるいは部分配列を比較するときにJSON.stringifyをせずに1要素ずつ比較してもよいです。（@akebi_mh 様のコメントを参考にさせていただきました。ありがとうございました）
冒頭で示したisSubarray3がこの方法になりますので、ここでは割愛します。

先頭をせずに、部分配列ごとに、JSON.stringifyで比較

isSubarray2やisSubarray３だと二重のリストに対して上手く判定できないケースがあります（リスト同士の比較は参照先の比較になって異なると判定されるため）。

console.log(isSubarray2([[1,2],3],[[1,2],3,4]));//falseになってしまう
console.log(isSubarray3([[1,2],3],[[1,2],3,4]));//falseになってしまう

これを改善するためには、要素同士の比較をするときに、必ずJSON.stringifyするようにします。ただしisSubarray2やisSubarray3よりも遅くなるケースが多くなります。

function isSubarray4(subarray, array){
  //subarrayが空のとき常にtrue
  if(subarray.length == 0)return true;
  //subarrayがarrayよりも長いとき、常にfalse
  if(subarray.length > array.length)return false;

  let subarray_str = JSON.stringify(subarray);
  for(let i=0;i<array.length - subarray.length + 1;i++){
    //arrayのi番目からsubarray長さ分だけsliceして比較
    let array_str = JSON.stringify(array.slice(i,i+subarray.length));
    if(subarray_str == array_str) return true;
  }
  return false;
}

console.log(isSubarray4([1,2],[1,2,3,4]));//true
console.log(isSubarray4([1,3],[1,2,3,4]));//false
console.log(isSubarray4([1],[1,2,3,4]));//true
console.log(isSubarray4([1],[12,2,3,4]));//false
console.log(isSubarray4([],[12,2,3,4]));//true。subarrayが空のときは常にtrueです
console.log(isSubarray4("12","1234"));//true。subarrayとarrayが両方stringのときは一応機能します。
console.log(isSubarray4("1,2", [1,2,3,4]));//false。subarrayがstringでarrayがlistのときはfalseになります。
console.log(isSubarray4([1,2],["1,2",3,4]));//false
console.log(isSubarray4([[1,2],3],[[1,2],3,4]));//true

全体を大雑把に比較してから細かく比較

isSubarray4はループが最後までいくと遅くなるので、isSubarrayでtrueの場合だけ、isSubarray4でより厳密に比較するような処理をしても良いかもしれません。

function isSubarray5(list1,list2){
  if(isSubarray(list1,list2)){
    return isSubarray4(list1, list2);
  }else{
    return false;
  }
}

console.log(isSubarray5([1,2],[1,2,3,4]));//true
console.log(isSubarray5([1,3],[1,2,3,4]));//false
console.log(isSubarray5([1],[1,2,3,4]));//true
console.log(isSubarray5([1],[12,2,3,4]));//false
console.log(isSubarray5([],[12,2,3,4]));//true。subarrayが空のときは常にtrueです
console.log(isSubarray5("12","1234"));//true。subarrayとarrayが両方stringのときは一応機能します。
console.log(isSubarray5("1,2", [1,2,3,4]));//false。subarrayがstringでarrayがlistのときはfalseになります。
console.log(isSubarray5([1,2],["1,2",3,4]));//false
console.log(isSubarray5([[1,2],3],[[1,2],3,4]));//true

二重リストを解消してから要素ごとに比較

あるいは要素にobject(array含む)が含まれるときだけ、文字列化しておいてから、isSubarray3を実行する処理でも良いと思います。

function isSubarray6(subarray, array){
  //要素にobjectがある場合、文字列化しておく
  let onedim_subarray = []
  for(let v of subarray){
    if(typeof v == "object") onedim_subarray.push(JSON.stringify(v));
    else onedim_subarray.push(v);    
  };
  //要素にobjectがある場合、文字列化しておく
  let onedim_array = []
  for(let v of array){
    if(typeof v == "object") onedim_array.push(JSON.stringify(v));
    else onedim_array.push(v);    
  };

  return isSubarray3(onedim_subarray, onedim_array);
}

console.log(isSubarray6([1,2],[1,2,3,4]));//true
console.log(isSubarray6([1,3],[1,2,3,4]));//false
console.log(isSubarray6([1],[1,2,3,4]));//true
console.log(isSubarray6([1],[12,2,3,4]));//false
console.log(isSubarray6([],[12,2,3,4]));//true。subarrayが空のときは常にtrueです
console.log(isSubarray6("12","1234"));//true。subarrayとarrayが両方stringのときは一応機能します。
console.log(isSubarray6("1,2", [1,2,3,4]));//false。subarrayがstringでarrayがlistのときはfalseになります。
console.log(isSubarray6([1,2],["1,2",3,4]));//false
console.log(isSubarray6([[1,2],3],[[1,2],3,4]));//true

再帰関数でJSON.stringifyせずに比較

JSON.stringifyは基本的に時間がかかるので避けるにこしたことはないです。
再帰関数を使うと、無限深さの配列や連想配列でもちゃんと比較することができます。
これが冒頭で示したisSubarray7になります。

速度比較

以下のコードをGoogleChromeで実行してみました。

let pair0 = [[1,2,3], [1,2,3,4,5,6,7,8,9,10]] //ループの最初で見つかるケース
let pair1 = [[8,9,10], [1,2,3,4,5,6,7,8,9,10]] //ループの最後で見つかるケース
let pair2 = [[0,1,2], [1,2,3,4,5,6,7,8,9,10]] //先頭マッチもせず見つからないケース
let pair3 = [[1,2,3], [0,0,0,0,0,1,1,1,1,1]] //先頭マッチを5回するが見つからないケース
let pair4 = [[1,2,3], [1,1,1,1,1,1,1,1,1,1]] //先頭マッチを10回するが見つからないケース
let pair5 = [[[0],[2]], [[1],[2],[3],[4],[5],[6],[7],[8],[9],[10]]] //2重リストで見つからないケース
let pair6 = [[[9],[10]], [[1],[2],[3],[4],[5],[6],[7],[8],[9],[10]]] //2重リストでループの最後で見つかるケース
let pair7 =  [[8,[9,10]], [1,2,3,4,[5,6],7,8,[9,10]]]; //2重リストでループの最後で見つかるケースその2
let pair8 = [[8,{9:[10,1]}], [1,2,3,4,[5,6],7,8,{9:[10,1]}]]; //配列要素で結果が見つかる

let loop = 100000;
let pairs = [pair0,pair1,pair2,pair3,pair4,pair5,pair6,pair7,pair8]
for(let i=0;i<pairs.length;i++){

  console.time("isSubarray_pair"+i);
  for(let j=0;j<loop;j++)isSubarray(pairs[i][0],pairs[i][1])
  console.timeEnd("isSubarray_pair"+i);

  console.time("isSubarray2_pair"+i);
  for(let j=0;j<loop;j++)isSubarray2(pairs[i][0],pairs[i][1])
  console.timeEnd("isSubarray2_pair"+i);

  console.time("isSubarray3_pair"+i);
  for(let j=0;j<loop;j++)isSubarray3(pairs[i][0],pairs[i][1])
  console.timeEnd("isSubarray3_pair"+i);

  console.time("isSubarray4_pair"+i);
  for(let j=0;j<loop;j++)isSubarray4(pairs[i][0],pairs[i][1])
  console.timeEnd("isSubarray4_pair"+i);

  console.time("isSubarray5_pair"+i);
  for(let j=0;j<loop;j++)isSubarray5(pairs[i][0],pairs[i][1])
  console.timeEnd("isSubarray5_pair"+i);

  console.time("isSubarray6_pair"+i);
  for(let j=0;j<loop;j++)isSubarray6(pairs[i][0],pairs[i][1])
  console.timeEnd("isSubarray6_pair"+i);

  console.time("isSubarray7_pair"+i);
  for(let j=0;j<loop;j++)isSubarray7(pairs[i][0],pairs[i][1])
  console.timeEnd("isSubarray7_pair"+i);

  console.log("");
}

結果は以下のとおりです。

//ループの最初で見つかるケース
isSubarray_pair0: 75.30517578125 ms
isSubarray2_pair0: 59.427001953125 ms
isSubarray3_pair0: 8.81201171875 ms
isSubarray4_pair0: 59.181884765625 ms
isSubarray5_pair0: 117.64697265625 ms
isSubarray6_pair0: 22.134033203125 ms
isSubarray7_pair0: 48.377197265625 ms

//ループの最後で見つかるケース
isSubarray_pair1: 87.3310546875 ms
isSubarray2_pair1: 53.096923828125 ms
isSubarray3_pair1: 4.239990234375 ms
isSubarray4_pair1: 229.39501953125 ms
isSubarray5_pair1: 285.39501953125 ms
isSubarray6_pair1: 14.848876953125 ms
isSubarray7_pair1: 88.8388671875 ms


//先頭マッチもせず見つからないケース
isSubarray_pair2: 51.414794921875 ms
isSubarray2_pair2: 23.537841796875 ms
isSubarray3_pair2: 1.901123046875 ms
isSubarray4_pair2: 258.015869140625 ms
isSubarray5_pair2: 53.743896484375 ms
isSubarray6_pair2: 11.031982421875 ms
isSubarray7_pair2: 70.532958984375 ms

//先頭マッチを5回するが見つからないケース
isSubarray_pair3: 53.73486328125 ms
isSubarray2_pair3: 105.1259765625 ms
isSubarray3_pair3: 2.205810546875 ms
isSubarray4_pair3: 233.666015625 ms
isSubarray5_pair3: 54.947021484375 ms
isSubarray6_pair3: 9.90576171875 ms
isSubarray7_pair3: 97.64990234375 ms


//先頭マッチを10回するが見つからないケース
isSubarray_pair4: 57.091796875 ms
isSubarray2_pair4: 234.51708984375 ms
isSubarray3_pair4: 2.89599609375 ms
isSubarray4_pair4: 228.984130859375 ms
isSubarray5_pair4: 58.477783203125 ms
isSubarray6_pair4: 10.912109375 ms
isSubarray7_pair4: 136.288818359375 ms


//二重リストで見つからないケース
isSubarray_pair5: 200.166015625 ms
isSubarray2_pair5: 53.93896484375 ms //２重リストに対して正しく機能しないため参考
isSubarray3_pair5: 30.64404296875 ms //２重リストに対して正しく機能しないため参考
isSubarray4_pair5: 510.492919921875 ms
isSubarray5_pair5: 175.716796875 ms
isSubarray6_pair5: 262.864990234375 ms
isSubarray7_pair5: 163.60791015625 ms


//二重リストでループの最初で見つかるケース
isSubarray_pair6: 172.57080078125 ms
isSubarray2_pair6: 52.055908203125 ms //２重リストに対して正しく機能しないため参考
isSubarray3_pair6: 6.968017578125 ms //２重リストに対して正しく機能しないため参考
isSubarray4_pair6: 477.635009765625 ms
isSubarray5_pair6: 655.263916015625 ms
isSubarray6_pair6: 281.468994140625 ms
isSubarray7_pair6: 190.325927734375 ms


//2重リストでループの最後で見つかるケースその2
isSubarray_pair7: 98.823974609375 ms
isSubarray2_pair7: 171.75 ms //２重リストに対して正しく機能しないため参考
isSubarray3_pair7: 38.298095703125 ms //２重リストに対して正しく機能しないため参考
isSubarray4_pair7: 291.704833984375 ms
isSubarray5_pair7: 394.912841796875 ms
isSubarray6_pair7: 88.56298828125 ms
isSubarray7_pair7: 90.63818359375 ms


//配列要素で結果が見つかる
isSubarray_pair8: 203.32080078125 ms //配列要素に対して正しく機能しないため参考
isSubarray2_pair8: 242.027099609375 ms //配列要素に対して正しく機能しないため参考
isSubarray3_pair8: 37.7578125 ms //配列要素に対して正しく機能しないため参考
isSubarray4_pair8: 390.35595703125 ms //配列要素に対して正しく機能しないため参考
isSubarray5_pair8: 607.825927734375 ms //配列要素に対して正しく機能しないため参考
isSubarray6_pair8: 179.095947265625 ms //配列要素に対して正しく機能しないため参考
isSubarray7_pair8: 133.27099609375 ms

ざっくりと以下のことがわかります。

• 二重リストを考慮しない場合
  • isSubarray3(要素同士をシンプルに比較)が判定も厳密で、ダントツ速い
• 二重リストを考慮する場合
  • isSubarray7(再帰関数でJSON．stringifyを使わずに比較)が判定も厳密で、安定して速い
• その他
  • JSON.stringifyは基本的に遅い

したがって、リストが一重であることがわかっているなら、isSubarray3を使い、そうでなければ、isSubarray7を使うのがいいかと思います。
JSON.stringifyは基本的に遅いですが、考え方が簡単なので、速度を気にしない場面でサクッと判定するために使うのはありだと思います。