B+木入門：PHPで理解する データベースインデックスの仕組み/b-plus-tree-101
k-d tree のお手軽実装について
こんにちは、競技プログラミングをやっている tatyam と申します。私のお気に入りのデータ構造は k-d tree です。 PAST-N : kDTree書くのたのし〜 pic.twitter.com/s5tB9e4piP — tatyam (@tatyam_prime) May 3, 2020 kDTree さいこー！https://t.co/diMEs3KAhM — tatyam (@tatyam_prime) March 28, 2021 E : kDTree ありがとう… 平面走査したくないので 3 次元 kDTree をする O(n + m log m + k m^(2/3)) TLE する印象しかなかったんだけど 795 ms で通った — tatyam (@tatyam_prime) June 7, 2021 できること k-d tree は、k 次元空間上の点の集合を管理
爆速ビームサーチライブラリを作る - Qiita
この記事では非常に高速なビームサーチライブラリの実装と、そのいくつかの具体的な使用例を紹介します。ビームサーチはDPを拡張し、上位M個を保持するようにしたもので、AHC系のコンテストで主に使われる非常に汎用的な手法の一つなのですが、高速なライブラリ設計に関する知見はあまり整備されていないと認識しています。そこで本記事では何種類かの典型的なケースに対応する高速なビームサーチの実装方法とそれらのライブラリ化の手法を紹介します。この方法では、問題固有のコードとライブラリ側のコードの大部分が分離されため、本質の探索以外を実装する必要がなくなり、しかも非常に高速な動作させることが可能になります。 本記事ではビームサーチの存在を知っていることが前提となっています。そのためビームサーチの入門のような内容は含みません。知らない方はまずビームサーチに関する記事を読むか実際にビームサーチが有効な問題を解いてみ
2 ポインタ/ノード で親方向を探索する二分木 - noshi91のメモ
概要 最もシンプルなポインタによる二分木の実装は、各ノードが左子と右子を保持することでしょう。 一方でこの実装では親方向へ遡ることが出来ません。すると例えば平衡二分探索木のイテレータを実装するときなどに問題になります。 親へのポインタを保持すれば解決しますが、本稿では空間計算量を抑える手法を紹介します。 XOR木 ポインタ領域を削減するデータ構造として、XOR連結リストが知られています。 XOR連結リスト - Wikipedia XOR連結リストとは、双方向連結リストで左右へのポインタの xor のみを保持する物です。 どちらかのポインタが分かっていればもう一方が復元できるため、左右いずれの端からも走査が可能となります。 この手法をポインタ二分木に応用してみましょう。 左子、右子、親の 3 つのポインタを適切に xor して 2 つに圧縮します。 どれを xor しても良いのですが、対称性
Algorithms by Jeff Erickson
🔥1st edition, June 2019 🔥 (Amazon links: US, UK, DE, ES, FR, IT, JP) This web page contains a free electronic version of my self-published textbook Algorithms, along with other lecture notes I have written for various theoretical computer science classes at the University of Illinois, Urbana-Champaign since 1998. More information Get the book More algorithms lecture notes Models of computation n
Gale-Shapleyアルゴリズム実装の高速化 - LIVESENSE Data Analytics Blog
こんにちは、リブセンスでデータサイエンティストをしている北原です。前回に続き今回もGale-Shapleyアルゴリズムを扱います。前回の記事で紹介した実装のボトルネックを把握し、少し改良することで計算量を大幅に削減します。コードはJuliaです。なお、今回の記事は下記の前回記事を読んでいることを前提として書かれています。 analytics.livesense.co.jp ボトルネック 選好順位判定行列 実装 実行時間の計測 まとめ ボトルネック まず、ボトルネックを見つけましょう。以下は前回記事で紹介した実装です。よく見ると一見簡潔に書かれているものの計算時間がかかりそうなところが2箇所見つかります。 function gs(user1_prefs, user2_prefs, unmatched_user1_stack) matched_user2 = fill(-1, length(u
指数時間アルゴリズム入門
2. 自己紹介 TopCoder: ◎wata TCO2010Marathon優勝など Twitter: @wata_orz 東京大学情報理工学系研究科コンピュータ科学専攻 理論計算機科学 (アルゴリズムの理論的な解析とか) プログラミングコンテスト チャレンジブック 2 3. 本日の内容 NP困難問題を解くためのアルゴリズムを扱います 𝑂𝑃𝑇 𝐼 ≤ 𝐴 𝐼 ≤ 𝑐𝑂𝑃𝑇(𝐼) 近似アルゴリズム ヒューリスティック 𝑓 𝑘 𝑝 𝑛 FPT アルゴリズム max 𝑐𝑥|𝐴𝑥 ≤ 𝑏, 𝑥: 整数} { 𝑂∗ 𝑐 𝑛 整数計画 厳密指数時間アルゴリズム 3 4. 効率的な指数時間アルゴリズム 何の指数？ 頂点数? 辺の数? それとも… • 2 𝐸 のアルゴリズムはまず役に立たないが，2 𝑉 のアル ゴリズムならコンテストでもよ
# 「ゲームで学ぶ探索アルゴリズム実践入門」のサンプルコードでAtCoderの問題を解いてみた - Qiita
「ゲームで学ぶ探索アルゴリズム実践入門」のサンプルコードでAtCoderの問題を解いてみた はじめに どうもこんにちは、thunderです。 私事ではありますが、2023/2/18に「ゲームで学ぶ探索アルゴリズム実践入門～木探索とメタヒューリスティクス」という技術書を出版しました！ amazon https://www.amazon.co.jp/dp/4297133601/ 技術評論社 https://gihyo.jp/book/2023/978-4-297-13360-3 本書の魅力はspeakerdeckにアップロードしたスライドにまとめているので、御覧いただけると幸いです。 さて、本書のサンプルコードはサポートページからダウンロードできるのですが、学んだ内容を活かして何かプログラムを書きたい！という方もいらっしゃるのではないかと思います。 本記事では、このサンプルコードを用いて実際に
Algorithm Design with Haskellでアルゴリズムを学ぶ - 朝日ネット 技術者ブログ
はじめに 開発部のcbmkageです。 仕事でプログラムを書いていると、どうしたら期待通りに、かつ高速に動作するアルゴリズムが実装できるか、考えることがあります。 本記事では、アルゴリズムについて新たな視点を与えてくれる本「Algorithm Design with Haskell」を紹介します。 本記事はHaskell中級者向けです。Haskellの文法や、代表的なリスト操作関数を知っていることを前提としています。 はじめに Algorithm Design with Haskellとは 準備: 関数の同値関係 貪欲アルゴリズムのPART紹介 貪欲アルゴリズムとは 候補の生成と選択 貪欲アルゴリズムへの改善 まとめ 採用情報 Algorithm Design with Haskellとは Algorithm Design with Haskell 作者:Bird, Richard,Gib
解説: Life Universe
公開からだいぶ時間が経ってしまいましたが、Life Universe の技術解説を書きます。 English version is here. Life Universe について その前に、いくつか知っておくとよい事柄があるので先に説明します。 OTCA Metapixel について ライフゲームの説明については割愛します。ライフゲームはチューリング完全なので様々なパターンが存在し、その中に OTCA Metapixel というものが存在します。OTCA Metapixel は（メタ）セルのオンとオフの状態が視覚的に分かる特殊なパターンで、ライフゲームのみならず outer totalistic なルール[1]で動く全ての[2]２次元セルオートマトンを再現できます。 つまり、ライフゲームの中で動くライフゲームを見ることができます。 こちらは有名な動画ですが、実際にこういう計算が可能になり
クリエイティブコーディングの教科書
ゲームエンジンや3Dソフトウェアを利用して高度な表現ができるこの時代でも、プリミティブな描画や動き、アルゴリズムから学べることは多い。それらをJavaScriptで書くクリエイティブコーディングという形で学べる手引書が本書となる。
この木なんの木？ モンテカルロ木と最良優先MiniMax木の"間"に存在する名もなき木々 - ヴァルの開発記
概要 この記事ではまだ名前が無いと思われるゲーム探索木をいくつか紹介します。この記事では具体的な実装は示さず、概念の紹介にとどめます。 この記事を読むために必要な知識は以下です。 ・モンテカルロ木探索＋UCB1 ・MiniMax探索 ・ボンバーマンの基本的なルール 名のある木々 名もなき木々を紹介する前に、まずは名のある木々を紹介します。 MCTS モンテカルロ木探索。簡単に言えば、評価関数を使わず、ランダム試行を繰り返して勝率の平均が高い手を調べる手法です。 有名な木なので、検索するとたくさん解説がヒットするのでこの記事では説明を割愛します。 一応参考として、私が初めてMCTSを実装したときに参考にした論文を載せておきます。 →A Survey of Monte Carlo Tree Search Methods 最良優先MiniMax 最良優先MiniMax探索についてはこちらの論文が
GitHub - scandum/fluxsort: A fast branchless stable quicksort / mergesort hybrid that is highly adaptive.
Fluxsort starts out with an analyzer that handles fully in-order arrays and reverse-order arrays using n comparisons. It also splits the array in 4 segments and obtains a measure of presortedness for each segment, switching to quadsort if the segment is more than 50% ordered. While not as adaptive as the bottom-up run detection used by quadsort, a top-down analyzer works well because quicksort sig
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - TheAlgorithms/Rust: All Algorithms implemented in Rust
Introduction to Design and Implementation of Metaheuristics
20230301_ビームサーチ講座.pptx
GitHub - ditsing/ruaft: Raft implemented in Rust
GitHub - eatonphil/goraft: A basic Raft implementation in Go.
Submission #36695211 - AtCoder Beginner Contest 278
GitHub - orlp/glidesort: A Rust implementation of Glidesort, my stable adaptive quicksort/mergesort hybrid sorting algorithm.
