【Javascript】計算量を減らして処理時間を短くする【2重ループとMap】
こんにちは、株式会社エムアイ・ラボ のエンジニアです。
DynamoDBの各テーブルから取得したデータを組み合わせて新しいデータを作成することがあります。
このとき、コードの書き方によって終了までの時間が大きく変わります。
今回は計算量に着目しながら実際の処理時間を比較検証することで効率の良いアルゴリズムについて理解を深めたいと思います。
※JavascriptのビルトインオブジェクトのMapが登場しますが、配列メソッドのmapとは異なるので注意してください。
検証
前提条件
今回の検証内容です。
ユーザーと住所をDynamoDBの各テーブルから全件取得し、それを結びつける作業を想定しています。
言語は弊社メイン開発言語のTypescriptを使用します。
2重ループ
まずはfor文を重ねるやり方です。
// ユーザーのデータをテーブルから取得したと仮定して作成
const users: {id, name}[] = [];
for (let i = 0; i < 100000; i++) {
users.push({id: i, name: `name_${i}`});
}
// 住所のデータをテーブルから取得したと仮定して作成
const addresses: {id, state, userId}[] = [];
for (let i = 0; i < 100000; i++) {
addresses.push({id: i, state: `state_${i}`, userId: i});
}
// 時間の計測開始
console.time();
const userAndState: { userName, state }[] = [];
users.forEach(user => {
addresses.forEach(address => {
if (user.id === address.userId) {
userAndState.push({ userName: user.name, state: address.state });
}
});
});
console.log(userAndState.length); // 100000
console.timeEnd(); // default: 4:16.717 (m:ss.mmm)
結果が出るまで4分16秒ほどかかりました。
users配列の各要素に対して内部のaddresses配列を線形探索しています。
この処理は二重ループなので、計算量は
計測開始から終了まで百億回の計算が行われています。
もし仮に同じ条件で三重ループになった場合の計算量は
日が暮れそうです。
Map
次はMapを使って効率良く実装した場合です。
// ユーザーのデータをテーブルから取得したと仮定して作成
const users: {id, name}[] = [];
for (let i = 0; i < 100000; i++) {
users.push({id: i, name: `name_${i}`});
}
// 住所のデータをテーブルから取得したと仮定して作成
const addresses: {id, state, userId}[] = [];
for (let i = 0; i < 100000; i++) {
addresses.push({id: i, state: `state_${i}`, userId: i});
}
// 時間の計測開始
console.time();
// 配列からハッシュテーブルであるMapに変換
const addressesMap = new Map();
for (const address of addresses) {
addressesMap.set(address.userId, address);
}
const userAndState: {userName, state}[] = [];
users.forEach(user => {
const address = addressesMap.get(user.id);
userAndState.push({userName: user.name, state: address.state});
});
console.log(userAndState.length); // 100000
console.timeEnd(); // default: 29.788ms
結果が出るまで約0.029秒です。
先程の例と比べて圧倒的に早いです。
住所データをMapに変換しているので、各ユーザーの住所を取得する際にはMapのget()メソッドを使ってハッシュテーブルから直接取得できます。
計算量は
100000(userAndStateの作成) + 100000(Mapの作成) = 200000
計測開始から終了まで20万回になりました。
まとめ
何も考えずにループを重ねてしまうと莫大な計算量になる可能性があります。
今回ご紹介したMapを利用するなど、計算量を削減する工夫を考えることでアルゴリズムについて少しずつ詳しくなるはずです。
自分もまだ学習中ですが、お互いにより良いコードを書けるように成長を続けていきましょう。
参考文献
採用情報
エムアイ・ラボでは一緒に働くメンバーを募集しています。
ぜひお気軽にご連絡ください！
Wantedlyアカウントをお持ちでない方はTwitterのDMからでも大丈夫です。
お待ちしております。
Discussion