JavaScript - Starting with the basics - Hashes(Storing the Word List into a Hash, Memorizing the Ackermann Function)

Think Perl 6

開発環境

• macOS Sierra - Apple (OS)
• Emacs (Text Editor)
• JavaScript (プログラミング言語)
• Node.js, Safari(JavaScript エンジン)
• Learning JavaScript [邦訳](参考書籍)

Think Perl 6: How to Think Like a Computer Scientist (Laurent Rosenfeld(著)、Allen B. Downey(著)、Oreilly & Associates Inc)の Part 1(Starting with the basics)、Chapter 10(Hashes)の Exercise: 10-1、10-2.を JavaScript で取り組んでみる。

Exercise: 10-1、10-2.

コード(Emacs)

HTML5

<pre id="output0"></pre>
<input id="file0" type="file">

<button id="run0">run</button>
<button id="clear0">clear</button>

<script src="sample1.js"></script>

JavaScript

let btn0 = document.querySelector('#run0'),
    btn1 = document.querySelector('#clear0'),
    pre0 = document.querySelector('#output0'),
    input_file0 = document.querySelector('#file0'),
    p = (x) => pre0.textContent += x + '\n',
    range = (start, end, step=1) => {
        let result = [];

        for (let i = start; i < end; i += 1) {
            result.push(i);
        }
        return result;
    };

let reader = new FileReader();

let bisect = (array, item) => {
    let inner = (idx1, idx2) => {
        if (idx1 > idx2) {
            return false;
        }

        let idx = Math.floor((idx1 + idx2) / 2),
            middle = array[idx];

        if (item === middle) {
            return true;
        }
        if (item < middle) {
            return inner(idx1, idx - 1);
        }
        return inner(idx + 1, idx2);
    };
    return inner(0, array.length - 1);
};
reader.onload = () => {
    p('1.');
    let words = reader.result
        .split('\n')
        .filter((word) => word !== '')
        .map((word) => word.trim()),
        wordsObj = {};

    words.forEach((word) => wordsObj[word] = 1);

    let words0 = 'think perl 6 aa zymurgy a zzzzzzzzzz'.split(' ');

    range(0, 10).forEach(() => {
        words0 = words0.concat(words0);
    });

    let t = new Date().getTime();
    words0.forEach((word) => {
        if (wordsObj[word] === 1) {}
    });
    p(`${new Date().getTime() - t}ms`);

    t = new Date().getTime();
    words0.forEach((word) => {
        if (bisect(words, word)) {}
    });
    p(`${new Date().getTime() - t}ms`);
};
input_file0.onchange = () => {
    reader.readAsText(input_file0.files[0]);
};

let ack = (m, n) => {
    if (m === 0) {
        return n + 1;
    }
    if (n === 0) {
        return ack(m - 1, 1);
    }
    return ack(m - 1, ack(m, n - 1));
};

let memo = {};
let ackMemo = (m, n) => {
    if (m === 0) {
        return n + 1;
    }
    memo[m] = memo[m] || {};
    if (memo[m][n]) {
        return memo[m][n];
    }
    if (n === 0) {
        memo[m][n] = ackMemo(m - 1, 1);
    } else {
        memo[m][n] = ackMemo(m - 1, ackMemo(m, n - 1));
    }
    return memo[m][n];
};
let f = (o) => Object.keys(o).map((k) => `${k} => ${o[k]}`).join(', ');

let output = () => {    
    p('2.');
    let t = new Date().getTime();
    p(ack(3, 4));
    p(`${new Date().getTime() - t}ms`);

    t = new Date().getTime();
    p(ackMemo(3, 4));
    p(`${new Date().getTime() - t}ms`);    
    
    Object.keys(memo).forEach((k) => p(`${k}: ${f(memo[k])}`));

    try {
        ackMemo(4, 4);
    } catch (e) {
        p(e);
    }
    range(5, 8).forEach((m) => {
        p(`ack(3, ${m})`);
        t = new Date().getTime();        
        p(ack(3, m));
        p(`${new Date().getTime() - t}ms`);
        t = new Date().getTime();
        p(ackMemo(3, m));
        p(`${new Date().getTime() - t}ms`);
        
    });
};

let clear = () => pre0.textContent = '';

btn0.onclick = output;
btn1.onclick = clear;

output();