できるだけ嘘を書かずに計算量やオーダーの説明をしようとした記事 - えびちゃんの日記
計算量についてのお話です。対象は、プログラミング経験はあるが計算量のことを知らない初心者から、計算量のことを知っているつもりになっている中級者くらいです。 数式を見たくない人にとっては読むのが大変かもですが、深呼吸しつつ落ちついて読んでくれるとうれしいです。 それから、この記事が自分には合わないな〜と思ったときは、（別の記事を Qiita とかで検索するよりも）この記事の一番下の 参考文献 にある本を読むことをおすすめします。Amazon の試し読みで無料で読めます*1。 TL; DR 関数の増加度合いのことをオーダーと呼ぶよ 計算量は、入力サイズ（など）を受け取ってアルゴリズムの計算回数（など）を返す関数だよ その関数のオーダーについての議論がよく行われるよ オーダーを上から抑えるときは \(O\)、下から抑えるときは \(\Omega\) を使うよ オーダーを上下両方から抑えたいときは
二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜 - Qiita
0. はじめに 二分探索法は単純ながらも効果が大きく印象に残りやすいもので、アルゴリズム学習のスタート地点に彩られた花という感じです。二分探索というと「ソート済み配列の中から目的のものを高速に探索する」アルゴリズムを思い浮かべる方が多いと思います。巨大なサイズのデータを扱う場面の多い現代ではそれだけでも十分実用的ですが、二分探索法はもっとずっと広い適用範囲を持っています。 本記事では、二分探索法のエッセンスを抽象化して、適用範囲の広い「二分探索法の一般形」を紹介します。同時に無数にある二分探索の実装方法の中でも「めぐる式二分探索」がバグりにくいと感じているので、紹介したいと思います。 注意 1: 二分探索の計算時間について 二分探索の計算時間について簡単に触れておきたいと思います。例えば「$n$ 個の要素からなるソート済み配列から目的の値を探索する」というよく知られた設定であれば、 単純な
大量のテキストからランダムに少数の行を抽出したい - Reservoir Sampling - 唯物是真 @Scaled_Wurm
前に以下のような記事を書きましたが、大量のテキストではうまくいかなかったので新たに書きました ファイルからランダムにN行取り出す(shufコマンド) - 唯物是真 @Scaled_Wurm 上の記事ではテキストをランダムに\(k\)行取り出したい時"shuf -n k"コマンドでランダムにシャッフルした\(k\)行を取り出していました ところが非常に大きなテキストファイルに対して上のコマンドを実行すると、一度にデータを全部メモリに読み込み始めているのか、すごい勢いでメモリを消費していきました(sort -Rでも) そこでメモリをあまり使わずにランダムに\(k\)行取り出す方法について調べました まず基本的な非復元抽出のアルゴリズムは以下の記事の発展手法とか追記のあたりの話がわかりやすいと思います 非復元抽出の高速かつ実装が簡単な方法を考える - 睡眠不足？！ この記事の話も一度全部の要素を
［SQEXOC 2012］FFXIVで使われているAI技術〜敵NPCはどうやって経路を探索しているのか？
［SQEXOC 2012］FFXIVで使われているAI技術〜敵NPCはどうやって経路を探索しているのか？ ライター：米田 聡 スクウェア・エニックスが2012年11月23日と24日の両日開催した「スクウェア・エニックス オープンカンファレンス」の最後には「AIセッション」が用意されていた。AIセッションは前半と後半に分かれ，前半は「ファイナルファンタジーXIV: 新生エオルゼア」（以下，新生FFXIV）における経路探索の実装に関する実践的な解説，後半はゲームAIの第一人者とも評される三宅陽一郎氏による，Luminous Studio用AIエンジンのやや概念的な話という構成だった。本稿では，まず前半の，より実践的なセッションから紹介してみたい。 テーマは，「MMORPGでマップ上を移動する敵NPCの経路をどう決めるのか」である。複雑で広いマップを有するMMORPGでは，移動する経路を賢く選択
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Cache-Oblivious データ構造入門 @DSIRNLP#5
