JavaScriptでのアルゴリズムとデータ構造 part1

初めに

連結リスト、スタックやキューなどデータ構造のコア概念を模索しながらC言語で練習してみて思ったのは、理解したうえでどんな場面で応用していくかが大事なんですね。

しかし応用の前段階から、アルゴリズムの理解に時間がかかったり不慣れなところ（解決法の仕組みとかどうしてそういう発想ができるのかとか）もあったりして、自分はやはり初歩的な段階からもう一度勉強してみたいと思います。

今回はリハビリを兼ねて長い間触れてないJavaScriptでアルゴリズムとデータ構造の実現を理解してまとめていきたいと思います。（箇条書きが多い。）

教材はこちらです。

（この記事では単なる自分の理解や気になるところをトピックにして書いたメモです。トピックは基本的に教材と関連しているが、語る方向が全然違う可能性もあります。なお、有料映像であったため、映像のコードそのまま出すのを控えております。なので記事に書いてあるのは正確性を問わず自分なりに考えたコードだったり、あるいはほかの参考文章から挙げたものでもあります。）

Memo

• 文字の検査では、普通にif条件式でコードポイント（code point）にするほうが正規表現より早い可能性は十分ある。（可読性が悪くなるんですが...。）
  • 正規表現は文字列の中身をチェックしたり、メソッドにより無害化して置き換えたりするメリットがある。それに可読性が高い。

Big O Notation

時間計算量（Time complexity）

• O(n^2)、O(n log n)、O(n)、O(log n)、O(1)。
  • linear: O(n), quadratic: O(n^2), constant: O(1)
• 基本的にループの実行回数で分けられている。
• O(n)とO(1)との違いは、O(n)はインプットのnでループの回数を決める。O(1)はnはどうであれ最大は固定された回数で実行する。
  • 場合によってO(n)とO(1)の計算量が同じだったこともある。

O(1)

function atMost5(n) {
  for (let i = 1; i <= Math.min(n, 5); i++) {
    console.log(i);
  }
}
atMost5(10);
// 1
// 2
// 3
// 4
// 5
atMost5(3);
// 1
// 2
// 3
atMost5(-3); // not work

---

O(n)

function atLeast5(n) {
  for (let i = 1; i <= Math.max(n, 5); i++) {
    console.log(i);
  }
}
atLeast5(5);
// 1
// 2
// 3
// 4
// 5
atLeast5(7);
// 1
// 2
// 3
// 4
// 5
// 6
// 7

• O(log n)は基数2ベースにして、毎回の処理ずつ入力データの半分を除外することで、全探索O(n)より少ない。

log2(8) = x => 2^3 = 8, x = 3
log2(n) = exponent => 2^exponent = n

空間計算量（Space complexity）

• 処理が実行される際にどのぐらいのメモリが使われるかを表す。
• 空間計算量（Space complexity）＝（実行のための）補助的メモリ空間（Auxiliary space）＋入力データが占めるメモリ空間（Input space）
• JavaScriptではboolean、number、undefined、nullは定数空間（constant space）とされている。
• 文字列は長さnで大きさを決めるのでO(n)となる。
• 配列は長さ、オブジェクトはキーの数でO(n)となる。

// there is one number every time => O(1) space
function sum(arr) {
  let result = 0;
  for (let i = 0; i < arr.length; i++) {
    result += arr[i];
  }
  return result;
}
console.log(sum([1, 2, 3])); // 6

// arr: n, newArr: n => O(n) space
function doubledArr(arr) {
  let newArr = [];
  for (let i = 0; i < arr.length; i++) {
    newArr.push(arr[i] * 2);
  }
  return newArr;
}
console.log(doubledArr([1, 2, 3])); // [ 2, 4, 6 ]

Arrays, Objects, Built-in Methods in JavaScript

Objects

• Insertion: O(1)
• Removal: O(1)
• Searching: O(n)
• Access: O(1)

Built-in Methods

• Object.keys(): O(n)
• Object.values(): O(n)
• Object.entries(): O(n)
• hasOwnProperty(): O(1)

Arrays

• Insertion: push()はunshift()より早い。
• Removal: pop()はshift()より早い。
• Searching: O(n)
• Access: O(1)

Built-in Methods
push(): O(1)
pop(): O(1)
shift(): O(n) *reindex
unshift(): O(n) *reindex
sort(): O(n log n)
...

Explore examples

• 一般的な事例
• さらに複雑な事例
• 端的な事例
  • 空（empty）や有効ではない（Invalid）入力の検証など。

Problem solving patterns

基本的に自分で考えたコードですが、アイディア・発想は映像の影響を受けております。

Frequency Counter

出現頻度などの問題は基本的に二重ループでなくオブジェクトで解決する。
オブジェクトのこの使い方をあまり考えたことありませんでした。とても賢い方法だと思います。

function validAnagram(str1, str2) {
  // length check
  if (str1.length !== str2.length) {
    return false;
  }
  // type check
  if (
    Object.prototype.toString.call(str1) !== '[object String]' ||
    Object.prototype.toString.call(str2) !== '[object String]'
  ) {
    return false;
  }

  // basically the input is assumed to be lower case. just making sure
  str1.toLowerCase();
  str2.toLowerCase();

  let obj1 = {};

  // not like array is indexing with index number,
  // object key is efficient and get value precisely
  for (let letter of str1) {
    obj1[letter] ? ++obj1[letter] : (obj1[letter] = 1);
  }

  for (let i = 0; i < str2.length; i++) {
    if (!obj1[str2[i]]) {
      return false;
    } else {
      obj1[str2[i]]--;
    }
  }
  return true;
}
console.log(validAnagram('aaz', 'zza')); // false
console.log(validAnagram('anagram', 'nagaram')); // true

Practices

function sameFrequency(num1, num2) {
  const typeChecker = Object.prototype.toString;
  if (
    typeChecker.call(num1) !== '[object Number]' ||
    typeChecker.call(num2) !== '[object Number]'
  ) {
    return 'Invalid input';
  }
  let str1 = JSON.stringify(num1);
  let str2 = JSON.stringify(num2);
  if (str1.length !== str2.length) return false;

  let obj = {};
  for (let num of str1) {
    obj[num] ? ++obj[num] : (obj[num] = 1);
  }
  for (let num of str2) {
    if (!obj[num]) {
      return false;
    } else {
      obj[num]--;
    }
  }
  return true;
}
console.log(sameFrequency(182, 281)); // true
console.log(sameFrequency(34, 14)); // false

Mutiple pointers

先頭・最後尾のポインタで両者の和が0になるペア探し出す。

function sumZeroPair(arr) {
  let left = 0;
  let right = arr.length - 1;
  let newArr = [];
  while (right > left) {
    let sum = arr[left] + arr[right];
    if (sum === 0) {
      newArr.push([arr[left], arr[right]]);
      right--;
      left++;
    } else if (sum > 0) {
      right--;
    } else {
      left++;
    }
  }
  if (!newArr.length) {
    return 'No pair';
  }
  return newArr;
}
console.log(sumZeroPair([-4, -3, -2, -1, 0, 1, 2, 3, 10]));
// [ [ -3, 3 ], [ -2, 2 ], [ -1, 1 ] ]
console.log(sumZeroPair([-4, -3, -2, -1, 0, 10]));
// No pair

Practices

一部違うタイプの入力も考えてみました。

const typeChecker = Object.prototype.toString;
function areThereDuplicates() {
  // check value type
  const type = typeChecker.call(arguments[0]);
  for (let [index, value] of Object.entries(arguments)) {
    if (typeChecker.call(value) !== type) {
      return differentType(...arguments);
    }
  }

  let obj = {};
  for (let [index, value] of Object.entries(arguments)) {
    // skip empty string
    if (value === '') {
      continue;
    }
    obj[value] ? ++obj[value] : (obj[value] = 1);
    if (obj[value] >= 2) return true;
  }
  return false;
}

function differentType() {
  let arr = [];
  for (let [index, value] of Object.entries(arguments)) {
    // skip empty string
    if (value === '') {
      continue;
    }
    arr.push([value, 1]);
  }

  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i][0] === arr[j][0]) {
        ++arr[i][1];
        if (arr[i][1] >= 2) {
          return true;
        }
      }
    }
  }
  return false;
}

console.log(areThereDuplicates(1, 2, 3)); // false
console.log(areThereDuplicates('a', 'b', 'c', 'a')); // true
console.log(areThereDuplicates('1', 1, '2', 3)); // false
console.log(areThereDuplicates('', '', '1', '2')); // false
console.log(areThereDuplicates('', '', '1', 1, 2, 2)); // true

配列風オブジェクトの処理はfor...ofとObject.entries()の組み合わせよりもっといい方法（Array.from()、...argsなど）があると思います。リンク先はオブジェクトのイテレータについてです。

---

そして一意のキーしか置かれないSetも使えることに気づいて、

function areThereDuplicates() {
  // Set only store unique value, whether primitives or objects
  // also the empty string ''
  let set = new Set();
  let emptyCount = 0;
  for (let i = 0; i < arguments.length; i++) {
    if (arguments[i] !== '') {
      set.add(arguments[i]);
    }
  }
  if (set.size - emptyCount === 0 || set.size === arguments.length) {
    return false;
  }
  return true;
}

console.log(areThereDuplicates(1, 2, 3)); // false
console.log(areThereDuplicates('a', 'b', 'c', 'a')); // true
console.log(areThereDuplicates('1', 1, '2', 3)); // false
console.log(areThereDuplicates('', '')); // false
console.log(areThereDuplicates('', '', '1', 1, 2, 2)); // true

Count unique values

重複しない要素の個数を求める。

function countUniqueValues(arr) {
  if (Object.prototype.toString.call(arr) !== '[object Array]') {
    return 'Invalid input';
  }
  if (arr.length === 0) return 0;

  let obj = {};
  let count = 0;

  for (let key of arr) {
    obj[key] ? ++obj[key] : (obj[key] = 1);
  }
  for (let [key, value] of Object.entries(obj)) {
    count++;
  }
  return count;
}
console.log(countUniqueValues([1, 1, 1, 1, 1, 2])); // 2
console.log(countUniqueValues([1, 2, 3, 4, 4, 4, 7, 7, 12, 12, 13])); // 7
console.log(countUniqueValues([])); // 0
console.log(countUniqueValues([-2, -1, -1, 0, 1])); // 4

---

下は元の配列から重複しない要素の配列を新しく作る解法です。

function countUniqueValues(arr) {
  if (Object.prototype.toString.call(arr) !== '[object Array]') {
    return 'Invalid input';
  }
  if (arr.length === 0) {
    console.log([]);
    return 0;
  }

  let left = 0;
  let newArr = [];
  newArr.push(arr[left]);

  for (let i = 1; i < arr.length; i++) {
    if (arr[left] !== arr[i]) {
      ++left;
      arr[left] = arr[i];
      newArr.push(arr[left]);
    }
  }
  console.log(newArr);
  return left + 1;
}
console.log(countUniqueValues([1, 1, 1, 1, 1, 2]));
// [ 1, 2 ]
// 2
console.log(countUniqueValues([1, 2, 3, 4, 4, 4, 7, 7, 12, 12, 13]));
// [1, 2, 3, 4, 7, 12, 13];
// 7
console.log(countUniqueValues([]));
// []
// 0
console.log(countUniqueValues([-2, -1, -1, 0, 1]));
// [ -2, -1, 0, 1 ]
// 4

Practices

配列から指定された平均値で数字のペアを見つけ出す。

// arr is sorted
function averagePair(arr, average) {
  if (arr.length === 0) return false;

  let left = 0;
  let right = arr.length - 1;
  let tempAverage = 0;
  while (right > left) {
    tempAverage = (arr[left] + arr[right]) / 2;
    if (tempAverage > average) {
      right--;
    } else if (tempAverage < average) {
      left++;
    } else {
      return true;
    }
  }
  return false;
}
console.log(averagePair([1, 2, 3], 2.5)); // true
console.log(averagePair([1, 3, 3, 5, 6, 7, 10, 12, 19], 8)); // true
console.log(averagePair([-1, 0, 3, 4, 5, 6], 4.1)); // false
console.log(averagePair([], 4)); // false

---

二つ文字列の入力で、前者の文字要素が後者に入っているかどうか。（前者の文字順に追う必要がある。）

function isSubsequence(str1, str2) {
  const typechecker = Object.prototype.toString;
  if (
    typechecker.call(str1) !== '[object String]' ||
    typechecker.call(str2) !== '[object String]'
  ) {
    return 'Invalid input';
  }

  let compareIndex = 0;
  for (let i = 0; i < str2.length; i++) {
    // we have to follow str1's order
    if (str2[i] === str1[compareIndex]) {
      compareIndex++;
    }
  }
  if (compareIndex === str1.length) return true;
  return false;
}

console.log(isSubsequence('hello', 'hello world')); // true
console.log(isSubsequence('sing', 'sting')); // true
console.log(isSubsequence('abc', 'abracadabra')); // true
console.log(isSubsequence('abc', 'acb')); // false

Sliding window

指定の長さで配列最大和を求める。
counterがdigitsに到達するまでtempTotalに今までの和を保存させる。digitsに到達するとtempTotalが返り値のresultと比べてresultより大きいならresultにアサインする。
startIndexは0から、毎回の間隔digitsが終わると+1をして新しいスタートになります。これは毎回の間隔が終わるとスタートが更新されるので二重ループと似た仕組みになっている気がします。

function maxSubarraySum(arr, digits) {
  const typeChecker = Object.prototype.toString;
  if (
    typeChecker.call(arr) !== '[object Array]' ||
    typeChecker.call(digits) !== '[object Number]'
  ) {
    return 'Invalid input';
  }
  if (arr.length < digits) return null;

  let startIndex = 0;
  let tempTotal = 0;
  let counter = 0;
  let result = -Infinity;

  for (let j = 0; j < arr.length; j++) {
    tempTotal += arr[j];
    ++counter;
    if (counter === digits) {
      if (tempTotal > result) {
        result = tempTotal;
      }
      tempTotal = 0; // reset
      counter = 0; // reset
      ++startIndex;
      j = startIndex - 1; // -1 for j++
    }
  }
  return result;
}
console.log(maxSubarraySum([1, 2, 5, 2, 8, 1, 5], 2)); // 10
console.log(maxSubarraySum([1, 2, 5, 2, 8, 1, 5], 4)); // 17
console.log(maxSubarraySum([4, 2, 1, 6], 1)); // 6
console.log(maxSubarraySum([4, 2, 1, 6, 2], 4)); // 13
console.log(maxSubarraySum([], 4)); // null

少し前にC言語アルゴリズムの練習で少し触れたので取り入れてみました。

これだとスタート位置を更新せず、さきの解法より早くなると思います。

function maxSubarraySum(arr, digits) {
  const typeChecker = Object.prototype.toString;
  if (
    typeChecker.call(arr) !== '[object Array]' ||
    typeChecker.call(digits) !== '[object Number]'
  ) {
    return 'Invalid input';
  }
  if (arr.length < digits) return null;

  let startIndex = 0;
  let tempTotal = 0;
  let result = -Infinity;

  for (let i = 0; i < arr.length; i++) {
    tempTotal += arr[i];
    if (i >= digits - 1) {
      if (tempTotal > result) {
        result = tempTotal;
      }
      tempTotal -= arr[startIndex];
      startIndex++;
    }
  }
  return result;
}

Practices

function maxSubarraySum(arr, digits) {
  if (
    arr.length < digits ||
    Object.prototype.toString.call(arr) !== '[object Array]'
  ) {
    return null;
  }

  let temp = 0;
  let result = -Infinity;
  for (let i = 0; i < digits; i++) {
    temp += arr[i];
  }

  result = temp;
  for (let i = digits; i < arr.length; i++) {
    temp = temp - arr[i - digits] + arr[i];
    if (temp > result) {
      result = temp;
    }
  }
  return result;
}
console.log(maxSubarraySum([100, 200, 300, 400], 2)); // 700
console.log(maxSubarraySum([1, 4, 2, 10, 23, 3, 1, 0, 20], 4)); // 39
console.log(maxSubarraySum([-3, 4, 0, -2, 6, -1], 2)); // 5
console.log(maxSubarraySum([3, -2, 7, -4, 1, -1, 4, -2, 1], 2)); // 5
console.log(maxSubarraySum([2, 3], 3)); // null

Recursion

いまでも苦手なトピックです。これを機に練習ができてよかったと思います。

Practices

function reverseStr(str) {
  if (!str) return '';
  return str[str.length - 1].concat(reverse(str.slice(0, str.length - 1)));
}
console.log(reverseStr('awesome')); // emosewa
console.log(reverseStr('rithmschool')); // loohcsmhtir

---

function isPalindrome(str) {
  // special case
  if (str.length === 1) return true;
  if (str.length === 2) return str[0] === str[1];
  // base case
  // String.prototype.slice(-1): extract the last element
  if (str[0] === str.slice(-1)) {
    return isPalindrome(str.slice(1, -1));
  }
  return false;
}
console.log(isPalindrome('awesome')); // false
console.log(isPalindrome('foobar')); // false
console.log(isPalindrome('tacocat')); // true

---

const isOdd = (value) => value % 2 !== 0;
function someRecursive(arr, callback) {
  // special case, base case
  if (arr.length === 0) return false;
  // other base case
  if (callback(arr[0])) return true;
  return someRecursive(arr.slice(1), callback);
}
console.log(someRecursive([1, 2, 3, 4], isOdd)); // true
console.log(someRecursive([4, 6, 8, 9], isOdd)); // true
console.log(someRecursive([4, 6, 8], isOdd)); // false
console.log(someRecursive([4, 6, 8], (val) => val > 10)); // false

---

function flatten(arr) {
  let newArr = [];
  for (let i = 0; i < arr.length; i++) {
    if (Array.isArray(arr[i])) {
      newArr = newArr.concat(flatten(arr[i]));
    } else {
      newArr.push(arr[i]);
    }
  }
  return newArr;
}
console.log(flatten([1, 2, 3, [4, 5]])); // [ 1, 2, 3, 4, 5 ]
console.log(flatten([1, [2, [3, 4], [[5]]]])); // [ 1, 2, 3, 4, 5 ]
console.log(flatten([[1], [2], [3]])); // [ 1, 2, 3 ]
console.log(flatten([[[[1], [[[2]]], [[[[[[[3]]]]]]]]]])); // [ 1, 2, 3 ]

これを見て、前も配列の平坦化をやったことあると思いだしました。まだまだ書き方に慣れてないときだったんですが、振り返りとして残しておきます。

---

function capitalizeFirst(arr) {
  if (arr.length === 0) return [];
  let newArr = [];
  newArr.push(arr[0][0].toUpperCase().concat(arr[0].slice(1)));
  return newArr.concat(capitalizeFirst(arr.slice(1)));
}
console.log(capitalizeFirst(['car', 'taco', 'banana'])); // [ 'Car', 'Taco', 'Banana' ]

---

const obj1 = {
  outer: 2,
  obj: {
    inner: 2,
    otherObj: {
      superInner: 2,
      notANumber: true,
      alsoNotANumber: 'yup',
    },
  },
};
const obj2 = {
  a: 2,
  b: { b: 2, bb: { b: 3, bb: { b: 2 } } },
  c: { c: { c: 2 }, cc: 'ball', ccc: 5 },
  d: 1,
  e: { e: { e: 2 }, ee: 'car' },
};

function nestedEvenSum(obj) {
  let sum = 0;
  for (let key of Object.keys(obj)) {
    if (typeof obj[key] === 'object') {
      // traverse next depth of obj
      sum += nestedEvenSum(obj[key]);
    } else if (typeof obj[key] === 'number' && obj[key] % 2 === 0) {
      // only even number can add
      sum += obj[key];
    }
  }
  return sum;
}
console.log(nestedEvenSum(obj1)); // 6
console.log(nestedEvenSum(obj2)); // 10

オブジェクトのコピーや探索について、

---

function capitalizeWords(arr) {
  if (arr.length === 0) return [];
  let newArr = [];
  newArr.push(arr[0].toUpperCase());
  return newArr.concat(capitalizeWords(arr.slice(1)));
}

console.log(capitalizeWords(['i', 'am', 'learning', 'recursion']));

---

let obj2 = {
  num: 1,
  test: [
    {
      num: 2,
    },
    [5],
  ],
  data: {
    val: 4,
    info: {
      isRight: true,
      random: 66,
    },
  },
};
// change olo obj
function stringifyNumbers(obj) {
  for (let key of Object.keys(obj)) {
    if (typeof obj[key] === 'object') {
      stringifyNumbers(obj[key]);
    } else if (typeof obj[key] === 'number') {
      obj[key] = obj[key].toString();
    }
  }
  return obj;
}
// return new obj
function stringifyNumbers(oldObj) {
  let copy = {};
  for (let key of Object.keys(oldObj)) {
    copy[key] = oldObj[key];
  }
  function recursivePart(newObj) {
    for (let key of Object.keys(newObj)) {
      if (typeof newObj[key] === 'object') {
        recursivePart(newObj[key]);
      } else if (typeof newObj[key] === 'number') {
        newObj[key] = newObj[key].toString();
      }
    }
  }
  recursivePart(copy);
  return copy;
}
console.log(stringifyNumbers(obj2));

Number→Stringは簡単にできますが、String→Numberはそうはいきませんでした。

（ちなみに'0O0'はNumber型にtrue判定されたのは8進数の0o000、'0X0'は16進数の0x0000。大文字小文字問わず、ここでは分かりやすいように小文字にしました。2進数なら'0b'/'0B'から始まる。）

---

const obj = {
  stuff: 'foo',
  data: {
    val: {
      thing: {
        info: 'bar',
        moreInfo: {
          evenMoreInfo: {
            weMadeIt: 'baz',
          },
        },
      },
    },
  },
};
function collectStrings(obj) {
  let arr = [];
  for (let key of Object.keys(obj)) {
    if (typeof obj[key] === 'object') {
      arr = arr.concat(collectStrings(obj[key]));
    } else if (typeof obj[key] === 'string') {
      arr.push(obj[key]);
    }
  }
  return arr;
}
console.log(collectStrings(obj));