アルゴリズムとデータ構造の辞典（Dictionary of Algorithms and Data Structures）

 (xlinux.nist.gov)
3 ポイント 投稿者 GN⁺ 2023-09-30 | 1件のコメント | WhatsAppで共有
  • アルゴリズム、アルゴリズム技法、データ構造、典型的な問題、関連する定義を集めて整理したオンライン辞典
  • Ackermann's function のような共通関数を含む アルゴリズム 項目を収録
  • traveling salesman、Byzantine generals など 典型的な問題 の項目を含む
  • 一部の項目では 実装（implementation） や追加情報へのリンクを提供し、項目は領域（area）別・種類（type）別の索引で整理
  • business data processing、AI、graphics などの特定分野は除外し、「一般（general）」なアルゴリズムとデータ構造 に集中

サイト概要と運営主体

  • NIST の Information Technology Laboratory 傘下の Software and Systems Division がホスティング
  • 辞典の開発は 1998 年に Paul E. Black の編集のもとで開始
  • アルゴリズム、アルゴリズム技法、データ構造、典型的な問題および関連定義を扱う辞典形式

収録項目の構成

  • アルゴリズム 項目には Ackermann's function のような共通関数を含む
  • 問題項目には traveling salesman、Byzantine generals を含む
  • 一部の項目では 実装（implementation） および追加情報につながるリンクを提供
  • 索引ページは項目を 領域（area）別 と 種類（type）別 に一覧化
  • two-level index は全体のダウンロード容量がこのページの 1/20 規模

利用案内

  • 不正行為（cheat）目的での使用は禁止、教師は支援が必要な場合は連絡するよう案内
  • 提案、修正、意見は Paul Black へ連絡するよう案内

扱わない範囲

  • 現在、次の分野に特化したアルゴリズムは未収録
    • business data processing、communications、operating systems または distributed algorithms
    • programming languages、AI、graphics、numerical analysis
  • 「一般（general）」なアルゴリズムとデータ構造だけでも扱うのが十分に難しいという理由で範囲を限定

索引および参考事項

  • n-way、m-dimensional、p-branching のように先行変数が付く用語は k- 項目の下に分類
  • A Glossary of Computer Oriented Abbreviations and Acronyms で有用な項目を確認可能

関連記事

1件のコメント

 
GN⁺ 2023-09-30
Hacker News のコメント

  • 関連する過去記事:
    Dictionary of Algorithms and Data Structures (1998) - https://news.ycombinator.com/item?id=12758176 - 2016年10月（コメント18件）
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=8905348 - 2015年1月（コメント4件）
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=5525893 - 2013年4月（コメント15件）
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=2496539 - 2011年4月（コメント16件）
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=2351074 - 2011年3月（コメント1件）

  • この資料を好きになりたいのだが、私が知っているもののうち Fenwick tree と union-find アルゴリズム/データ構造 が抜けている
    Fenwick tree を初めて見たのはここだった: https://www.youtube.com/watch?v=uSFzHCZ4E-8&t=479s
    union-find はたぶんここで見たと思う: https://www.youtube.com/watch?v=PGZ64ob440I
    ただし記憶では、固定サイズ配列ではなく辞書/ハッシュマップ実装だった

    • かなり多くが抜けているように思う。Fenwick は別名でも載っていると思ったが見当たらず、union-find がないのはさらに不思議だ。本当に優れていて有用なデータ構造なので、隠れていそうな別名も思い浮かばない
      すぐ思い付く範囲で見つけられなかったものは、平方分割、heavy-light decomposition、そして範囲最小値クエリ（Range Minimum Query）全般。個人的に範囲最小値クエリは一般的な問題としてかなり好きな部類で、時間をかけて集中する手法群としてはソートよりずっと興味深いと思う
      union-find データ構造は通常、固定配列で示されることが多いが、その方がアルゴリズム解析が少し面白くなる。参照コストが O(1) を超えると、解析上の面白い部分が埋もれてしまうと思う。もちろんデータ構造自体はどの方式でもうまく動く
    • 有限のコレクションなので、ほぼ何でも抜けてしまうのは避けられない。soft heap や finger tree もなく、Okasaki が扱う純粋関数型データ構造も多く抜けている

  • 素晴らしい資料だが、データ構造とアルゴリズムの授業は応用にもっと焦点を当ててほしい
    単にそれが何かを知ることより、なぜ有用で、どの文脈で取り出して使うべきかを知ることにより関心がある

    • https://www.redblobgames.com/ は文脈を多く提供しつつ、技術的な詳細も避けない、とても良い資料だ
    • 似た方向で記事を書いたことがある。応用そのものというより、Blind 75 の問題セットを解きながら学んだ内容をもとに、どの問題にどのデータ構造やアルゴリズム的アプローチを適用するかを選ぶためのガイド/意思決定ツリーだった
      まだ専門家ではないので権威ある資料ではないが、面白いかもしれない: https://sebinsua.com/algorithmic-bathwater#what-kind-of-prob...
    • 私の経験では、授業ではすでにそうしている。与えられた関数の時間・空間計算量とその解析が核心だ
    • Skiena がこのテーマで良い講義をしていた気がする
    • 文脈と歴史を知ると確実に面白くなるし、たいてい学習にも役立つ

  • 目を引く項目が1つ: Marlena
    https://xlinux.nist.gov/dads/HTML/marlena.html
    これが何を意味するのか知っている人はいる？

  • アルゴリズムをアルファベット順に並べたリストが、学習者にとって良い出発点かどうかは分からない
    始めたばかりの人、またはこのテーマをしっかり身につけたい人には、この古典的な本が定番だと思う。[1]
    開発者として成長し、FAANG のコーディング面接を通過することが目標なら、これが最も強力なレバレッジかもしれない
    [1] https://books.google.com/books/about/Introduction_To_Algorit...

    • 出発点としては、おそらく違う。だが参考資料としては素晴らしい

  • このリストを逆引き検索するにはどうすればいいのか気になる
    例えば、あるアルゴリズムの動作の仕方はおおよそ説明できるが名前は知らず、このリストに載っているか知りたいことがある。今なら擬似コードにして ChatGPT に渡し、名前を聞くこともできるかもしれないが、それ以外はよく分からない

    • Discord に行って聞けば、誰かが教えてくれるはず

  • プルリクエストを受け付けてくれるといいのに。acceleration structure のような基本的な項目が抜けている

  • 本当に素晴らしい資料だ。予算削減のようなものを耐え抜いて残ってほしいし、アーカイブしておくべきだ