Jsmanga.github.io

GitHub - Ref - Neetsha - 〒

はじめてのデータ構造と関数

データの種類 typeof

typeof 1;       // => 'number'
typeof(_ => 1); // => 'function'

typeof を使うことで、データの種類がわかります。 大まかには次の表のようになってます。

型 例
number 1, 2.0, ...
string "a", "abc", ...
boolean true, false
function x => x, ...
object 配列など

最後のオブジェクトは、他のデータを組み合わせて作るデータ構造です。

配列・オブジェクト

オブジェクトは言語によって辞書と呼ばれる機能で、key (項目名) を与えると、 対応した value (内容) が返ってきます。 そのため、配列は 0 から連続した数字の key を持つオブジェクトです。

// Array (配列)
const array = [1,2,3];
array[0]; // => 1

// Object
const member = {takeuchi: "ゲイツ", linus: "松本"} // {key: value} と呼ぶ
member.takeuchi // => "ゲイツ"
member["takeuchi"] // 配列っぽい使い方

気をつけたいのは、他のデータと異なり = 演算子 はコピーではなく参照になります。

// データ型のとき
const a = 1:
let b = a; // コピー
b = 2; // このとき a は 1 のまま

// オブジェクト型のとき
const c = [0, 1];
let d = c; // 参照：実態は a と同じ
d[0] = 2; // このとき a も [2, 1]

関数を出力する関数

これまで「階乗」、「フィボナッチ」、「竹内関数」といった再帰関数がでてきました。 彼らは自身に再度小さな引数を入力するので、一度入力された値の出力を「メモ」しておけば高速化できます。

メモはオブジェクトを使うのがいいでしょう。 というわけでメモ化関数を例に「関数を入出力する関数」の登場です。

// 例. 竹内関数
const f = (x, y, z) => x <= y ? y : f(f(x-1, y, z), f(y-1, z, x), f(z-1, x, y));

const memf = memoize(f); // 入力の関数をメモ化した関数を出力

// 前回の時間計測する time 関数
time(_=> memf(14, 1, 0)); // 3260 ms
time(_=> memf(14, 1, 0)); // 0.00849 ms

二回目以降は軽快に動作するようになって嬉しいですね。 メモ化関数 memoize の中身はこんな感じです。

// 入力 func をメモ化
const memoize = func =>
{
    let memo = {};

    // メモ化した無名関数を出力
    return _ =>
    {
        if (!(arguments in memo))
        {
            memo[arguments] = func.apply(this, arguments);
        }
        return memo[arguments];
    };
};

チェックポイント

  • この関数はクロージャになっています、返り値の関数毎に memo は独立して作られ、 それぞれのメモを保存します。クロージャの詳細はまた今度紹介したいですね。

  • arguments 関数の入力(引数)全部を表す特殊なデータです。 関数が何個引数をとるやつでも対応させたいときの裏ワザです。

    • if (!(arguments in memo)) メモされていない引数なら、新しく計算してメモします。
    • func.apply(this, arguments) 特殊な変数なので値呼び出しをするには特殊な書き方になります。

データ構造の登場でかなり便利になった気がします。 次回は配列に注目します。

次へ