Two Sumで始めるパフォーマンス改善

leetcodeの問題を一つ取り上げてみようと思います。想定する読者は1~3年目エンジニアと、1~3年目にこれらを教える立場にいるエンジニアです。
https://leetcode.com/problems/two-sum/
Two Sumを効率性(Runtime, Memory)、可読性観点で解説してみます。選択言語はJavascriptです。
※leetcodeとは、プログラミング問題が解けるサービスです。他にもAOJとか似たようなサービスはいくつかあります。

効率性(Runtime)重視

Submission Detailを参考にしています(一部フォーマットかけています。もしかしたら解いてないとアクセスできないかも。)。
Runtimeを重視するときに気をつけるポイントは、繰り返し回数・処理コスト(I/Oとか)です。特に、SQLでID検索などで扱うデータの総量を減らすとか、arrayにfilterをかけてから処理するとかは、繰り返し回数の観点ですね。
特にコストのかかる処理がないので、この問題では繰り返し回数にフォーカスを当てます。

コード

var twoSum = function(nums, target) {
    sumMap = {};

    for(let i = 0; i < nums.length; i++){
        let diff = target - nums[i];
        if(sumMap[diff] !== undefined) {
            return [sumMap[diff],i]; break;
        } else {
            sumMap[nums[i]] = i;
        }
    }
    return [];
};

解説(なぜこのコードが速いか)

ポイントは2つありまして、繰り返し回数とsumMap(厳密にはこれも繰り返し回数にかかる仕掛けですが)になります。
効率性(Runtime)重視の繰り返し回数が最大nums.lengthである一、効率性(Memory)重視と可読性重視は最大nums.length * (nums.length - 1)です。ここに大きな差が出ています。
numsの数が大きくなればなるほど差は大きく出ます。例えば、nums.lengthが5の時の差は5:20で、10の時10:90となります。
この例は分かりやすいかな、、正確性を欠くのであくまでイメージですが、一次関数と二次関数の差のイメージです。

そして、この繰り返し回数を減らす仕掛けとしてsumMapを利用しています。ざっくりいうとsumMapをobject型で宣言して一度処理したnum再利用しやすくしています。
なぜobject型で再利用性が高まるかというところは、線形探索とかハッシュ法とかで調べてみると幸せになれると思います。
不正試合という声も上がりそうですが、おおよそこんなところで試してみてもいいかもです。

const performance = require('perf_hooks').performance;

const length = 100000
const arr = [...Array(length).keys()]
const obj = Object.assign({}, arr);
const sw = (fn) => {
    const start = performance.now()
    fn()
    console.log(performance.now() - start)
}

sw(() => arr.find(_ => _ === length))
sw(() => obj[length])

効率性(Memory)重視

Submission Detailを参考にしています（もしかしたら解いてないとアクセスできないかも。）。

Memoryを重視するときに気をつけるポイントは、変数の数です(演算途中もメモリにpoolされるのかな。。)。

コード

var twoSum = function(nums, target) {
    if(nums.length > 0) {
        let res = [];
        for(let i = 0; i < nums.length; i++) {
            for(let j = nums.length - 1; j > 0; j --) {
                if(j == i) continue;
                
                if(nums[i] + nums[i + 1] == target) {
                    return [i, i + 1];
                    break;
                } else if(nums[j] + nums[j - 1] == target) {
                    return [j, j - 1];
                    break;
                } else if(nums[i] + nums[j] == target) {
                    return [i, j];
                    break;
                }
            }
        }
    } else {
        return [];
    }
};

解説(なぜこのコードのメモリ効率がいいか)

Memoryで使っている変数は、res(array), i(number), j(number)、Runtimeは、sumMap(object), i(number), diff(number)です(nums, targetは共通なので割愛)。
res(array)が空配列なので使っている変数は実質数値のみですね。letで宣言して領域を使い回しているのもポイントかと思います。

可読性重視

そして可読性(好みの世界でもあるのであくまで一例として)。こういうのを書いてみました。

コード

var twoSum = function(nums, target, offset = 0) {
  for (let i = offset + 1;i < nums.length; i++) {
    if ((nums[offset] + nums[i]) === target) return [offset, i];
  }
  return twoSum(nums, target, offset + 1);
};

解説(なぜこのコードの可読性が高いか)

ミソはtwoSumを再起呼び出ししているところです。
これによりレビューする必要があるコードが実質3行であるところです。
ちなみにパフォーマンスはこんな感じ。Runtime:138 ms, Memory:40.2 MB

まとめ

さて、いかがだったでしょうか。実は初投稿なのでドキドキしています。

参考になったでしょうか。
今やMemoryが安価で時は金なりなので、多くの場合速度や可読性が重視されることが多いかと思います。
本件は、あくまでサンプルで、大切なのはどういうものを求められていてアウトプットするか(そしてそれを説明できるか)だと思うので、仕事などフォーマルな場で使うときには取捨選択してください。
また、今回は分かりやすさを重視してあえて語らなかったこともあるので、レベルアップしたいかたはぜひ自己学習してみてください。

余談ですが、弊社では採用・ワークショップにleetcodeを使い始めています。
その辺りの話も徐々にできたらと思います。