利用者:Ef3/js/アルゴリズム

出典: フリー教科書『ウィキブックス(Wikibooks)』
ナビゲーションに移動 検索に移動

この章では、JavaScriptの言語特性を、実際のアルゴリズム記述を使って評価する。

素数を求める[編集]

/**
 * 素数を求める
 * @param {Number} 求める個数
 * @return {Number []} 素数の配列
 */
function primes(n) {
    const primes = [2];
    for (let x = 1, j = 0, k = 1; k < n; /**/ ) {
         x += 2;
         for (let j = 0; j < k; j++) {
             const pJ = primes[j];
             if (x % pJ == 0) {
                 break;
             }
             if (pJ * pJ >= x) {
                 primes[k++] = x;
                 break;
             }
         }
    }
    return primes;
}
let t = Date.now();
primes(10 ** 3);
console.log(`${Date.now() - t } [msec]`)
  1. primes[j] がループの一番内側で頻回に使われており、プロパティの参照も相応の時間を要するの、一時変数に確保。
  2.  :

フィボナッチ数列BigIntジェネレータ関数版[編集]

/**
 * フィボナッチ数列BigIntジェネレータ関数版 (@function・@generator 省略)
 * @yields {number} フィボナッチ数列
 */
function* fib() {
    let cur = 0n,
        next = 1n;
    for (;;) {
        let reset = yield cur;
        [cur, next] = [next, next + cur];
        if (reset) {
            cur = 0n,
            next = 1n;
        }
    }
}

const seq = fib();
for (i = 0; i < 10; i++)
    console.log(seq.next().value);
console.log("reset");
console.log(seq.next(true).value);
for (i = 0; i < 10; i++)
    console.log(seq.next().value);

for (const n of fib()) {
  if (n > 100) break;
  console.log(n);
}
  1. function* ジェネレータ関数
  2. for (;;) 無限ループ。フォーエヴァーと読みます
  3. yield 文は .next() に渡されたパラメータを返します(パラメータを与えなければ undefined が返ります)
  4. 多値代入を使って中間変数を使わないで済ませた
  5. for-of 文の右項にジェネレータ関数が使える(.next() プロトコルに準拠しているので)