LoginSignup
0
0

More than 1 year has passed since last update.

@hu-yu

JavaScriptでのedge caseの勉強ノート

Last updated at Posted at 2022-04-26

Edge caseとは

エッジケースは、限界値（最高値／最小値）が起こす特別な問題や状態を指している。アルゴリズムの使用など、極端なケースを避けるべきだとよく指摘されています。
今回はこちらの文章に参考して書いた勉強ノートです。
Algorithms: Common edge cases in JS | by Jeremy Gottfried |

前回は課題としてソートを書きました。この著者のようにバブルソートを使ってデモしていきたいと思います。
Bubble Sort

bubbleSort.js
function bubble(arr) {
  // let bigger number always stay on right side
  // if arr[n] > arr[n+1], arr[n] <=> arr[n+1]
  // if arr[n] < arr[n+1], arr[n => n+1], arr[n+1 => n+1+1]
  let temp = 0
  for (let i = 0; i < arr.length; i++) {
    temp = 0
    for (let j = temp + 1; j < arr.length - i; j++) {
      // console.log('temp:', temp, 'j:', j)
      if (arr[temp] > arr[j]) {
        [arr[temp], arr[j]] = [arr[j], arr[temp]]
        temp++
        // console.log('temp>j: ', arr)
      } else {
        temp++
        // console.log('temp<j: ', arr)
      }
    }
  }
  return arr
}

Data Structure

事前に受け入れられるデータ構造をチェックする。
ソートは基本的に配列しか受け入れない構造で、もしほかのデータ型を入れたらどんなことが起きるでしょう。

const str = '123'
const num = 456
const true = true
const bigNum = bigInt()
const symbol = symbol()
const undefinde = undefinde
const null = null

const obj = {
  0: 0,
  1: 1,
  2: 2,
  3: 3
}
console.log(bubble(obj)) // { '0': 0, '1': 1, '2': 2, '3': 3 }
console.log(bubble('123')) // 123
console.log(bubble(456)) // 456
console.log(bubble(true)) // true
console.log(bubble(BigInt(123))) // 123n
console.log(bubble(Symbol())) // Symbol()
console.log(bubble(Symbol(42))) // Symbol(42)
console.log(bubble(Symbol('foo'))) // Symbol(foo)
console.log(bubble(undefined)) // TypeError: Cannot read property 'length' of undefined
console.log(bubble(null)) // TypeError: Cannot read property 'length' of null

undefinedとnullは長さが読めないので動きませんでしたが、オブジェクト、文字列やブーリアンなどそのまま返されました。しかしソートには、その後何かほかの処理のために使用されているはずなので、処理できない値ソートに入れるへきではないと考えられます。
なので、一番最初にArray.isArray()でチェックします。

if (!Array.isArray(arr)) return false

Empty values

データ型チェック入れたとしても、[]みたい空の値も受け入れるようになっている。

console.log(bubble([])) // []

そこで空値のチェックも一緒に入れます。

if (!arr[0]) return false // [] is falsy value
//
if (arr.length === 0) return false // empty values have no length

でも入れ子構造になっている配列は、データ型と空値の検査も通ってしまいます。参考文章には解決方法に触れていないので、前に多次元配列を書いたコードを使って解決してみようと思います。
flatten multidimensional array（多次元配列の一次元化）

function bubble(arr) {
  if (!Array.isArray(arr)) return false
  if (flatArr(arr).length === 0) return false
...
}

function flatArr(arr) {
  // if it's an array, callback & return
  // if arr is not an array, push into newArr
  let newArr = []
  for (let i = 0; i < arr.length; i++) {
    if (typeof arr[i] === 'object') {
      flatArr(arr[i])
    } else {
      newArr.push(arr[i])
    }
  }
  return newArr
}

console.log(bubble([[], [], [], [[]], [[[]]]])) // false

Accepted types

ここから少し複雑な話になっていくと思います。配列の中身としては、数字のほか、文字列やオブジェクトなど基本的に何でも入れます。一般的にソートは数学や文字列の処理に当たっていると思いますが、実際にデータベースからもらったデータは綺麗な状態ではない可能性が大きいです。参考文章のように、

bubbleSort([a,A,b,B])
---> [A,B,a,b]
...
if (arr[j-1].toLowerCase > arr[j].toLowerCase) {
var temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}

toLowerCaseを使ってアルファベット文字列の大文字と小文字問題を解決していく。なので、数字も前段階で整理しなければならないと思います。（日本語文字列のソートはほかの問題も絡んでいるので今回はとりあえず数字だけ）

普通の整数と巨大数字のソート

まずデータベースからのデータの状態を想定してみます。

  • JSにおける安全な整数の最大値(2^53 - 1)を超える巨大な数字の出現が可能、データがstringとして保存されていることを前提に。
  • 処理できない数字ではない'[]','abc','!@#','{}'などのデータが混在している。
  • 数字だけソートに入れて、それ以外を排除したい。
  • 負数は存在しない。
testData
const test = [
  '123456789012345678901234567890123456789012345678901234567894',
  '123456789012345678901234567890123456789012345678901234567891',
  '123456789012345678901234567890123456789012345678901234567890',
  '123456789012345678901234567890123456789012345678901234567892',
  '123456789012345678901234567890123456789012345678901234567890',
  '12345678901234567890123456789012345678',
  '1234567890123456789012345678901234567',
  '123456789012345678901234567890123456',
  '12345678901234567890123456789012345',
  '1234567890123456789012345678901234',
  'null',
  'undefined',
  'abc',
  '!@#',
  '[]',
  '{}',
  '123',
  '4567',
  '0',
  [[], [], [], [[]], [[[]]]],
  '123abc456',
  'NaN'
]

バブルソートの前に、正確の整数と巨大な数字に分ける

function isNormalNum(arr) {
  let result = []
  arr.map((item) => {
    if (Number.isNaN(Number(item)) !== true) { // or (typeof Number(item) === 'number' && Number(item) !== NaN)
      if (Number(item) < Number.MAX_SAFE_INTEGER) {
        result.push(item)
      }
    }
  })
  return result
}

function isBigNum(arr) {
  let result = []
  arr.map((item) => {
    if (Number.isNaN(Number(item)) !== true) { // or (typeof Number(item) === 'number' && Number(item) !== NaN)
      if (Number(item) > Number.MAX_SAFE_INTEGER) {
        result.push(item)
      }
    }
  })
  return result
}
// note: about Number.isNaN(), please take a look at the below

配列ではないデータと、多次元配列と、空値を排除してから、
正確の整数と巨大な数字、別々に処理を行います。

function numSort(arr) {
  if (!Array.isArray(arr)) return false
  arr = flatArr(arr)
  if (arr.length === 0) return false

  let normalNum = bubble(isNormalNum(arr))
  let bigNum = isBigNum(arr).sort(function compare(str1, str2) {
    if (str1.length < str2.length) {
      return -1
    } else if (str1.length > str2.length) {
      return 1
    }

    let max = Math.ceil(str1.length / 15)
    let digits = 0
    for (let i = 1; i <= max; i++) {
      // 0~14,15~29
      let a = Number(str1.substring(0 + 15 * digits, 15 * i))
      let b = Number(str2.substring(0 + 15 * digits, 15 * i))

      if (a - b < 0) {
        // a < b
        // return str1
        return -1
      } else if (a - b > 0) {
        // a > b
        // return str2
        return 1
      }
      digits++
    }
    return 0
  })
  return normalNum.concat(bigNum)
}

console.log(numSort(test))
// [
//   '0',
//   '123',
//   '4567',
//   '1234567890123456789012345678901234',
//   '12345678901234567890123456789012345',
//   '123456789012345678901234567890123456',
//   '1234567890123456789012345678901234567',
//   '12345678901234567890123456789012345678',
//   '123456789012345678901234567890123456789012345678901234567890',
//   '123456789012345678901234567890123456789012345678901234567890',
//   '123456789012345678901234567890123456789012345678901234567891',
//   '123456789012345678901234567890123456789012345678901234567892',
//   '123456789012345678901234567890123456789012345678901234567894'
// ]

Number.isNaNの使用について

console.log(Number.MAX_SAFE_INTEGER) // 9007199254740991

// seems like it's no problem with the number over MAX_SAFE_INTEGER
console.log(Number.isNaN(9007199254740998954)) // false
console.log(Number.isNaN('9007199254740998954')) // false
console.log(Number.isNaN(Number(9007199254740998954))) // false
console.log(Number.isNaN(Number('9007199254740998954'))) // false

// but these cases will give a weird result without using Number()
console.log(Number.isNaN(Number('[]'))) // true
console.log(Number.isNaN('[]')) // false
console.log(Number.isNaN(Number('!@#'))) // true
console.log(Number.isNaN('!@#')) // false
console.log(Number.isNaN(Number('9007740abc954'))) // true
console.log(Number.isNaN('9007740abc954')) // false

グローバルの isNaN() 関数とは異なり、 Number.isNaN() は強制的に引数が数値に変換される問題の影響をうけません。これは、通常 NaN に変換されるが実際には NaN ではない値が、安全に渡されることを意味します。つまりこの関数は、数値型であり、かつ NaN である値が渡されたときのみ、 true を返すということです。

Number.isNaN() - JavaScript | MDN

感想

今回はEdge caseの勉強ノート、実際は受け入れるデータの構造を理解し、厄介もの？どうやって排除していくかをいろいろ工夫しなければならないと思います。資料を調べたら、ほかに巨大整数の四則演算があります...。引き続き頑張ります。

参考資料のまとめ

外部資料
Algorithms: Common edge cases in JS | by Jeremy Gottfried |
Number.isNaN() - JavaScript | MDN
自分の公開ノート
Bubble Sort
flatten multidimensional array（多次元配列の一次元化）

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0