JavaScript - Starting with the basics - Arrays and Lists(sorted words(alphabetical order), bisection search(binary search) vs indexOf)

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 9(Arrays and Lists)の Exercise 9-10.を JavaScript で取り組んでみる。

Exercise 9-10.

words.txt

コード(Emacs)

HTML5

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

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

<script src="sample10.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 bisect = (array, item) => {
    let len = array.length;

    if (len === 0) {
        return false;
    }
    
    let idx = Math.floor(len / 2),
        middle = array[idx];

    if (item === middle) {
        return true;
    }
    if (item < middle) {
        return bisect(array.slice(0, idx), item);
    }
    return bisect(array.slice(idx + 1), item);
};

let find = (array, item) => {
    for (let i = 0, max = array.length; i < max; i += 1) {
        if (array[i] === item) {
            return true;
        }
    }
    return false;
};

let bisect1 = (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);
};


let output = () => {
    let reader = new FileReader();

    reader.onload = () => {
        let words = reader.result.split('\n')
            .filter((word) => word !== '')
            .map((word) => word.trim());

        range(0, 5).forEach(() => {
            words = words.concat(words);
        });
        words.sort();
        ['think', 'perl', '6', 'aa', 'zymurgy', 'a', 'zzzzzzzzzz']
            .forEach((word) => {
                p(word);

                let t = new Date().getTime(),
                    b = bisect(words, word);

                t = new Date().getTime() - t;
                p(`bisect:  ${b} ${t}ms`);
                
                t = new Date().getTime(),
                b = find(words, word);
                t = new Date().getTime() - t;
                p(`find:    ${b} ${t}ms`);

                t = new Date().getTime(),
                b = bisect1(words, word);
                t = new Date().getTime() - t;
                p(`bisect1: ${b} ${t}ms`);

                t = new Date().getTime(),
                b = words.indexOf(word) !== -1;
                t = new Date().getTime() - t;
                p(`indexOf: ${b} ${t}ms`);
                
            });
    };
    reader.readAsText(input_file0.files[0]);
};

input_file0.onchange = output;
btn0.onclick = output;
btn1.onclick = () => pre0.textContent = '';

// output();