純粋なSQLで実装したAdvent of Code 2024

• 純粋なSQLでAdvent of Code 2024に挑戦

• 概要

  • 筆者は今年のAdvent of Codeを純粋なSQLで解くことにした。
  • この経験は問題を違う視点で考えさせる内容で、非常に興味深かった。すべての問題をSQLで解くことができた。
  • SQLは意外に快適に使える場合が多かった。

• Day 11の例

  • 問題の入力を含む、全体の解法を提示している。
  • SQLで入力をパースするのは少し面倒だが、不可能ではない。
  • アルゴリズムは比較的短く、再帰的なフィールド探索を行う。
  • SQLは小規模な探索作業に適している。

• 他の日の挑戦

  • Day 16では、フィールドの最短探索距離を計算する同様のタスクを行った。
  • SQLで表現するのは簡単だが、評価効率はよくない。
  • 大きな入力を処理する際には多くの状態を保持する必要があり、200GB以上のメモリが必要だった。
  • 一部のDBMSはこの問題を解決する機能を持たない。

• 再帰SQLの限界

  • Day 23では、疎なグラフで最大クリークを見つける必要があった。
  • Bron-Kerboschアルゴリズムを使えばよいが、再帰SQLで表現すると複雑になる。
  • 再帰SQLは単一の集合しか渡せないため、複数の集合を保持する必要があるアルゴリズムとは相性が悪い。

• 結論

  • 複雑なアルゴリズムをSQLでコーディングすることは可能で、SQLコードは意外と快適な場合がある。
  • 状態を更新する仕組みがあれば、再帰SQLはより効率的で使いやすいものになる。
  • 複雑な状態操作のメカニズムを導入すれば、SQLはデータベース内で複雑なアルゴリズムを実行する強力な選択肢になり得る。

[GN⁺]

Hacker Newsコメント

• 新しいメニュー項目への反応は、欲望、羞恥、そして人間の創造性への感嘆が混ざり合ったものだ
• 経歴のほとんどを通じて最も多く書いたのはSQLで、ここ5年間はあまり使っていなかったが、それでも楽しかった
• 反復的に考えるのをやめて集合演算として考え始めると、より自然で強力になる
• Google SheetsでAoCを試していて、Day 6まで到達したが、一部の入力では文字数制限にぶつかった
  • モバイルでは開かないことを推奨している
• 過去に運用職のインタビューで大規模データセットの請求書レポート作成問題を受けた
  • データサイエンティストではなかったため、解法を構成するのが難しかった
  • Crystal Reportsのようなレポートパッケージを使うだろうと説明した
  • SQLで問題を解決したが、多くの技術が必要だった
• EdgeQLでAoCを試み、面白い経験だった
  • 関連するツイートを共有した
• SQLでキューイング/コンテナ化システムを作成し、一部の拡張機能を使った
  • 基本的なアルゴリズムはSQLの機能とよく相性が合っていた
  • いくつかの側面はSQLに合わせるのが難しかった
• AoC2024をGoogle Sheetsで進めており、これを文書化する予定だ
• 純粋なSQLで作業する姿は印象的で、古いブログを運用し続けることで「ニッチ・マスタリー」を示している