トップ > 【Power Query】List.FirstN+List.Sumの累計処理がO(N²)で重くなる理由をBig O記法から解説

【Power Query】List.FirstN+List.Sumの累計処理がO(N²)で重くなる理由をBig O記法から解説

はじめに

Power Query（M言語）で累計列を作るとき、List.FirstN で先頭から現在行までを切り出し、List.Sum で合計する——という書き方は直感的でわかりやすい一方、行数が増えると急激に処理が重くなることがあります。

この記事では、その原因である Big O（ビッグオー）記法 の考え方と、Power Queryでの改善アプローチを整理します。Big Oは直感に反する部分が多く、初めて学ぶときに誤解しやすいポイントがいくつかあるため、随所に「間違えやすいポイント」として補足しています。

Big O記法とは何か

Big O記法は、アルゴリズムの計算効率を表す標準的な指標です。ポイントは以下の1文に尽きます。

Big O記法は「今何秒かかるか」を表すものではなく、「データ量 N が増えたとき、処理量がどのような割合で増えていくか」を表す記法です。

具体的な秒数ではなく、データが増えたときの増え方（オーダー） を見る指標だという点が重要です。

間違えやすいポイント 「O(N)なら処理は10,000回」「O(N²)なら処理は50,000,000回」のように、Big Oの記法そのものが具体的な回数を意味していると捉えてしまいがちです。実際には、Big Oは「Nが増えたときにどのくらいの勢いで処理量が増えるか」という増加の傾向（オーダー）を表すものであり、具体的な回数はあくまでイメージをつかむための目安です。

代表的なBig Oパターン

はじめてBig Oを学ぶ場合、まずは以下の3つを押さえるのがおすすめです。

記法 特徴
O(1) データ量に関わらずほぼ一定（配列の先頭を取得）
O(N) データ量に比例して増える（シンプルな1重ループ）
O(N²) データ量の2乗に比例して増える（2重ループに相当）

この3つを理解した後、次のふたつを追加すると理解が進みます。

記法 特徴
O(log N) 増えてもあまり遅くならない（二分探索）
O(N log N) 効率的なソート処理など

なぜ List.FirstN + List.Sum は O(N²) になるのか

「各行ごとに、先頭から現在行までをスライスして合計する」処理は、計算量の観点では2重ループに相当する構造になっています。

  • 外側：全 N 行を1行ずつ処理する → N回
  • 内側：その行までの要素を合計する
    • 1行目：1個を加算
    • 2行目：2個を加算
    • 3行目：3個を加算
    • …
    • N行目：N個を加算

このとき、List.FirstN は「先頭からi個を取り出す」処理、List.Sum は「そのi個を走査して合計する」処理であり、少なくとも List.Sum は行番号 i に比例するコストがかかります。

全体の処理規模は次の等差数列の合計になります。

1 + 2 + 3 + … + N = N(N+1) / 2

Big O記法では最も影響の大きい項（N²）だけを残し、係数や低次の項を無視するため、この処理は O(N²) と表記されます。

間違えやすいポイント 「内部で2重ループを行っている」という説明は、実装として本当に2重のfor文があるという意味ではありません。List.FirstNとList.Sumという別々の関数呼び出しでも、計算量の観点で見ると2重ループに相当する規模の処理になっている、という意味です。実装の見た目と計算量の構造は分けて考える必要があります。

データ量による増加イメージ

O(N)（理想的な処理）と O(N²)（今回の処理）で、データ量に対する処理規模がどう変わるかを比較します。

データ件数 N O(N) の処理規模 O(N²) の処理規模（概算） 実際の累計対象数 N(N+1)/2
100 約100 約10,000 5,050
1,000 約1,000 約1,000,000 500,500
10,000 約10,000 約100,000,000 50,005,000
100,000 約100,000 約10,000,000,000 5,000,050,000

データが10倍になると、O(N) は約10倍で済みますが、O(N²) は約100倍に増加します。これが数千〜数万行を超えたあたりで処理が急激に重くなる理由です。

間違えやすいポイント 上の表の「処理規模」は、対象要素へのアクセスや加算が発生する規模のイメージであり、CPUが実行する命令数そのものではありません。「O(N²)だから実際に1億回CPUが処理する」という受け取り方は正確ではなく、あくまで増え方の分類を示す近似値として捉えるのが適切です。

O(N²)は「常に悪い処理」ではない

Big Oを学び始めると「O(N²)は悪い処理、O(N)は良い処理」と思いがちですが、これは正確ではありません。O(N²)が問題になるのは、データ量が大きくなったときに処理量が急増しやすいという性質であり、データ量が小さいうちは大きな問題にならないケースもあります。

例えば N=10 なら N²=100 で大きな影響はありませんが、N=1,000,000 なら N²=1,000,000,000,000 となり、桁が大きく変わります。また、係数の大きいO(N)（例：100N）と係数の小さいO(N²)を比べると、Nが小さい間はO(N²)の方が実測で速いケースもあります。Big Oは、データ量が大きくなったときの伸び方を比較するための指標であり、小さいデータでの優劣を保証するものではありません。

「Power QueryはO(N²)だから遅い」という一般化に注意

間違えやすいポイント 今回の話は「Power QueryそのものがO(N²)で遅い」という意味ではありません。正確には、今回採用したMコード（List.FirstN + List.Sum）のアルゴリズムがO(N²)的な計算量になっているという、実装依存の話です。Power Query（M言語）とDAX（Formula Engine / Storage Engine / VertiPaq）は別レイヤーの仕組みであり、混同しないよう整理しておくと理解がぶれません。

Power QueryでO(N)に近づける改善アプローチ

「前の行の累計値に、現在の行の値だけを足す（走査累計）」という考え方を、Power QueryのMコードで実現する際の現実的な方法を紹介します。

推奨パターン：List.Accumulate

List.Accumulate を使うと、リストを1回だけ走査しながら累計を構築できます。概念的な流れは以下の通りです。

初期値: [acc = {}, sum = 0]
各要素 x に対して:
    sum = sum + x
    acc = acc & {sum}
結果: acc が累計リスト

対象列をリスト化し、List.Accumulate で累計リストを作成してテーブルに再結合する形が一般的です。この方式であれば、リストを1回なぞるだけで済むためO(N)になります。

間違えやすいポイント 「1つ前の行の累計列を参照して足す」という書き方をそのままMで実装しようとすると、Power Queryの評価モデル上、各行で式が再評価される形になりやすく、結果的にO(N²)に近い挙動になることがあります。列同士を再帰的に参照する書き方よりも、値リストを取り出してList.Accumulateで処理する書き方の方が、計算量・実測の両面で安定して軽くなります。

前提：ソート順序

累計の意味を正しく保つには、日付やIDなど特定の順序でソートしてから累計を取る必要があります。順序が保証されていないと、アルゴリズム以前に累計の結果自体が意味をなさなくなります。ソート自体はO(N log N)ですが、O(N²)ほど急激には増加しないため、全体としては「O(N²) → O(N log N) + O(N)」という形に改善され、大幅に軽くなります。

改善後の処理時間について

O(N²)からO(N)に近いアルゴリズムへ改善できれば、データ量が増えたときの処理時間の増加を大幅に抑えられます。

間違えやすいポイント 「O(N)に改善すれば数万行でも必ず一瞬で終わる」とは限りません。Power Queryの実際の処理時間は、アルゴリズムの計算量だけでなく、列数・データソース・他の変換ステップ・ソート・結合・Table.Bufferの有無・クエリの折りたたみ・PCの性能など多くの要因に左右されます。計算量の改善は「処理時間の増加を抑える」ことを保証するものであり、絶対的な速さを保証するものではありません。

実測時の確認方法

Power BIやExcelのプレビュー自動更新がオンだと、UI側の再評価が加わり体感の処理時間がさらに重く感じられることがあります。アルゴリズムの差を正確に確認したい場合は、プレビュー自動更新をオフにした状態でクエリを単独実行して計測するのがおすすめです。

まとめ

  • Big O記法は「今何秒かかるか」ではなく「データ量が増えたときの処理量の増え方」を表す指標
  • List.FirstN + List.Sum による累計処理は、1+2+…+N = N(N+1)/2 の規模になり、Big Oでは O(N²) と分類される
  • O(N²)は「常に悪い処理」ではなく、「データ量が大きくなると急増しやすい」という性質を示すもの
  • 改善する場合は List.Accumulate による1回走査パターンが有効。行を再帰参照する実装ではO(N²)的な挙動が残るため注意
  • ソート順序の前提や、Power QueryとDAX/VertiPaqのレイヤーの違いを混同しないことも、正確な理解のポイント