早計の擁護

プログラミング界には「早計な最適化」という言葉があって、色んな場面で繰り返し使われています。その言葉自体は私たちの多くが生まれる前からあって、本当にドナルド・E・クヌースが書いた時からあるんです。

本当の問題は、プログラマーが効率について間違った場所、間違った時にあまりにも多くの時間を悩んでいることです。早計な最適化こそが、プログラミングにおける全ての悪の根源（少なくとも大部分の）です。

1974年のこの引用には、心の底から同意します。でも、多くのプログラマーがこの「この段階では効率のことを心配しなくていい」という考えを過剰に適用していると思います。その言葉が生まれた頃、プログラマーは最も一般的なユースケースにおいてパフォーマンスを考えないという贅沢はできませんでした。当時のハードウェアはアルゴリズムよりも遥かに劣っており、コンパイラレベルの最適化は初期段階で、ライブラリを共有することにも大きな物流上の問題がありました。要するに、ソフトウェア開発プロセスはまったく異なるものであり、効率について心配することはコマンドごとの格闘であり、したがって大きな時間の浪費となる可能性がありました。

もちろん、これが現代のプログラミングに当てはまらないという意味ではありません。適用されるべきですが、初期段階での効率に関するすべての考えにキャンセルスタンプを押すべきではありません。例えば大きなOの時間計算複雑さ、ネットワークのペイロードサイズ、読み書きの頻度、テキスト検索のインデックスなどについて考えなければならないことがあります。コードを一行も書く前に少なくとも部分的に対処する必要のある効率性の問題です。開発者がこれらの問題の重要性についてどのような判断を下すかは、全体のアーキテクチャに長期的な影響を与える可能性があります。たとえ「ただのプロトタイプ」であっても、最終成果物の一部となる可能性が高いですし、多くの実装上の決定が「そちらでやっているようにやる」となるでしょう。そうは言っても、これらの問題の多くは尊重され、少なくともエンジニアによっては有効と見なされています（マネージャーは異なる意見かもしれません）。したがって、これらのユースケースについてはこの記事では触れません。誰かが検索実装の時間計算複雑さを問われたときにあなたを早計な最適化をする人だと言うなら、その人をコンピュータサイエンスの入門講座に戻す必要があります。

私がしたいのは、ちょっとした最適化の短い議論や配慮が無関係で時間の無駄であり、結果として読みにくいコードになるという考えを払拭することです。ここで強調したいのは、**パフォーマンスの向上はコードの可読性のコストとして実施されるべきではありません。しかし、多くのパフォーマンス向上は、同じ読みやすさを維持しながら、それを実装するのにほとんど追加の時間を必要とせずに行うことができます。**以下の例では、JavaScriptのアロー関数が一般的にどのように使用されているかを見て、最小限の変更が時間をかけてどれだけの影響を与えるかを見ていきます。

例

新しいJSフレームワークのためのクラシックなHello Worldプロジェクトを作りましょう - Todoアプリです。実際、この例を使って本当のビューライブラリの細かな部分に入らずにパフォーマンスの影響をデモンストレーションするためには、もう少し複雑な例が必要なので、Trelloのクローンにすることにします。もしTrelloを使ったことがなければ、それは基本的にプラグインオプションをたくさん持った非常にカスタマイズ可能なtodoアプリですが、この例で関連するものはありません。

私たちのクローンの機能セットと要件は次の通りです：

todoはカードで表される
カードにはユーザーを割り当てることができる
カードにはラベル（テキスト + 色）を持つことができる
カードはリストの一部
リストはボードの一部
ユーザーはボードごとに役割を持ち、それによって：
- ボードとそのコンテンツを見るだけができる（GUEST）
- 既存のカードを編集し、新しいカードを作成できる（MEMBER）
- カードとリストの両方を管理（作成、編集、または削除）できる（ADMIN）
各ボードには、所有者がひとりだけいる
ボードはワークスペースにグループ化される
ワークスペースにも所有者がひとりだけいる
ワークスペースにグループ化されていないボードは、所有者の「個人ワークスペース」と見なされる

元々は、記述したエンティティのシンプルなクラス図をここに追加する予定でしたが、図のラインのアライメントに神経を使いすぎてしまうと判定し、やめました。すべてのクラスはかなりシンプルで、一つのオブジェクトがいくつかの他のオブジェクトを参照しなければならないコレクションを持っています（1:NおよびN:Mの関係）。この記述なしでもコードは理解できるはずですし、何かがはっきりしない場合は気にしないでください。パフォーマンスの部分に到達すると、すべてがドメインに依存しなくなります。

少し先取りして、あなたがこのアプリを好きなライブラリ/フレームワークで頭の中で構築したと仮定します（そのエディタータブを閉じてください）。新しい要求が入ってきました。クライアントはアナリティクススクリーンを望んでいますが、彼らが最初に求めているデータ選択は次のようになっています：

私の個人ワークスペースボードの「DESIGN」ラベルのカードに割り当てられた全ユーザーを見つけてください。または「DESIGN」と呼ばれるワークスペースにある任意のボードで「MEMBER」または「ADMIN」の権限を持つ人。または「DESIGN」と呼ばれるワークスペース内のボードの所有者である人も見つけてください。idによって重複を排除します。

だいぶ長ったらしいですが、これが要求のより良い理解を得るための実装です。以下のコードでは Array.prototype メソッドのみに依存していますので、馴染みのないものがあれば MDNに目を通してください。

function getDesigners_v1(targetUser) {
  return []
    .concat(
      [].concat(
        ...targetUser.personalWorkspaceBoards.map((_board) =>
          [].concat(
            ..._board.lists.map((_list) =>
              _list.cards
                .filter((_card) =>
                  _card.labels.some((_label) => _label.name === 'DESIGN')
                )
                .map((_card) => _card.users)
            )
          )
        )
      ),
      [].concat(
        ...targetUser.workspaces
          .find((_workspace) => _workspace.name === 'DESIGN')
          .boards.map((_board) =>
            _board.boardUsers
              .filter((_boardUser) =>
                ['MEMBER', 'ADMIN'].includes(_boardUser.role)
              )
              .map((_boardUser) => _boardUser.user)
          )
      ),
      targetUser.workspaces
        .find((_workspace) => _workspace.name === 'DESIGN')
        .boards.map((_board) => _board.owner)
    )
    .filter(
      (_user1, _index1, _array) =>
        !_array.some(
          (_user2, _index2) => _index1 > _index2 && _user1.id === _user2.id
        )
    );
}

最初に見た目はアロー関数のめちゃくちゃな使い方のように見えるかもしれませんが、コード自体は非常に直接的です。以下の3つのリストを結合します：

ターゲットユーザーの個人ワークスペースのボードの「DESIGN」カードから取得したユーザー
ターゲットユーザーの「DESIGN」ワークスペースで「MEMBER」または「ADMIN」の役割を持つユーザー
ターゲットユーザーの「DESIGN」ワークスペース内のボードの所有者

その後に、idによって重複を除外します。同じidプロパティを持つ要素が既にあるかを見ています。

このような「シングルクエリ」スタイルのコーディングは、いくつかのJavaScriptプロジェクトでデータ操作ユースケースにおいてかなり一般的です。これは、データベース用の様々なクエリビルダーライブラリに影響を受けたものであったり、単にプログラマーが「見て、私は余分な変数なしでこれをやることができる」と自慢するためであったりします（私たち全員がそこにいたことがあります）。しかしこのクエリを、大きなOの時間計算複雑さの観点から見れば、最適化は次のいずれかが最大である限り無意味です：

COUNT(personalWorkspaceBoards) * COUNT(lists) * COUNT(cards) * MAX(COUNT(labels), COUNT(users)) [段階1.1]
COUNT(workspaces) * COUNT(boards) * COUNT(boardUsers) [段階1.2]
COUNT(users) * COUNT(users) [段階2]

例えば、最初に思いつく最適化のアイデアは、リターンの上に結果を抽出することで、手順1.2と1.3の「ワークスペースを見つける」部分を組み合わせることです。これは上記リストの2番目にのみ関連しますが、実行は同じままです。別のアイデアは、連続した filter と map の呼び出しを一つの reduce メソッドに組み合わせることです。これはリストの2つに影響を与え、実行の一番内側の部分に影響を与えるため、大きな差が出る可能性があります（ネタバレですが、そうでしたが、あなたが考える理由とは違います）。しかし大きなOに戻して、これはまだ同じ時間計算複雑さの順です。実行時間は半分になりますが、それは一定の要素ですので、アルゴリズム的な観点からは無意味です。3つ目のアイデアは、この奇妙な [].concat(…list.map(/*…*/)) の構文の代わりに flatMap を使用することです。それは構築、展開、そして再構築によって引き起こされる余分なオブジェクトと反復を排除し、コードをはるかに素敵に見せます。しかし、これはES 2019の機能(提案リンク)であり、全てのユーザーの環境で利用可能であるわけではありません。でも、2021年です、IEは死にました、caniuse.com は92%のカバレッジと言っているので、それでいいです、バン、実装しました。そして...これは reduce が最終的になったものと同じタイプの最適化です。それはリストに関連したカウントを乗算するだけの一定の要素です。

このことは考えてみればあまり驚くべきことではありません。結局のところ、データ自体の構造が要求しているのは、記述された要素すべてをイテレートすることです。アルゴリズム的な観点からできる最大のことは、計算をスキップできるループを見つける試みであり、そのループが行う結果の

こちらの記事はdev.toの良い記事を日本人向けに翻訳しています。
https://dev.to/5ar/in-defense-of-being-premature-5dlk

早計の擁護

例

タグ

最新の記事