とても長い配列の上位M件だけをクイックソートより高速に取り出す - Qiita
というわけで、10倍の差がでた。 当然、配列の長さやソートする長さ、また実装の方法によって性能差は変わってくるが 今回の方法は有効であるということは確認できた。 既存の記事(2015/11/09 20:22 追記) コメント欄でUnordered partial sorting にそれらしきことが書いてあると教えていただいた。 そちらでは、「上位k個を取り出す（ソートは不要）」という問題を考えている。 同様に分割統治法を用いてソートしていきながら、上位k個以内の小区間になったらその区間はソートせずに全て選択して良いとしている。 早い話が、QuickSelectによりk+1番目の要素を探してそれより上位の要素をごそっと抜き出している。 分割統治法で大雑把にソートしていきながら、不要なソートを行わないようにする という同様のアプローチである。 C++のSTLの場合(2015/11/09 22:
HL分解 (Heavy-Light Decomposition) - ペケンペイのブログ
HL 分解 (heavy-light decomposition) についてではなく、パスクエリを複数の列クエリに分解するという考え方について説明する。HL 分解は木が与えられて次の二種類のクエリを処理する問題等で用いられる。 uv パス上のすべての頂点にxを加算する uv パス上の値の総和を求める 総和クエリの例。この場合は 2+3+4+9+6+4+7+1=36 が答えになる 木ではなく列であれば segment tree によって効率的に処理できる。HL 分解は木をパスに分解することで、木の問題を列の問題に還元する。木をパスに分解するとはどういうことだろうか。例えば次の図のようなものが木をパスに分解した例になっている。 冒頭で例に出したクエリは次の形に分解できる。 このクエリはsum[16..16] + sum[13..14] + sum[0..1] + sum[6..8]で計算できる
RDB - 実例で学ぶ、JOIN (NLJ) が遅くなる理屈と対処法 - Qiita
"Nested Loop Joinしか取り上げて無いのにタイトルが大きすぎないか" と指摘を頂いたので、タイトルを修正しました。Merge JoinとHash Joinのことはまた今度書こうと思います。 「JOINは遅い」とよく言われます。特にRDBを使い始めて間がない内にそういう言説に触れた結果「JOIN=悪」という認識で固定化されてしまっている人も多いように感じています。 たしかに、JOINを含むようなSELECT文は、含まないものに比べて重たくなる傾向があることは事実です。また、本質的に問い合わせたい内容が複雑で、対処することが難しいものも存在します。しかし、RDBの中で一体どういうことが起きているのかを知り、それに基いて対処すれば高速化できることも少なくないと考えています。 本稿では、JOINの内部動作を解説した上で、Webサービスを作っているとよく出てくるJOIN SQLを例題に
ネガマックスの説明がどこもおかしい件 - やねうらおブログ(移転しました)
αβ探索は簡単なコードではあるが直感的には理解しづらい。熟練したプログラマでも慣れていなければ理解しにくい。 「αβ探索ってなんぞや？」って言う人はこの時点でブラウザを閉じてお戻りください。ここから先に腹がよじれるような面白いことは何一つ書いてませんので。 さて、αβ探索が理解できないならMinMax法から勉強しなおすべきで、MinMax法の基本的なコードが次のコードである。 「ミニマックス法」(Wikipedia) http://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%8B%E3%83%9E%E3%83%83%E3%82%AF%E3%82%B9%E6%B3%95 上のMinMax法のコードは自分は局面評価が最大になるものを選び、相手は局面評価が最小になるものを選ぶ。簡単明瞭なコードである。つまり、ここで言う局面評価関数(上記コードの STATIC_VA
手続き型のダンジョン生成アルゴリズム | プログラミング | POSTD
この投稿では、以前に TinyKeepDev が こちら で述べたランダムなダンジョンを生成する技法について説明しようと思います。元の投稿に比べて、もう少し具体的に話を進めるつもりです。まずは、以下に示したアルゴリズムの一般的な動作をご覧ください。 部屋の生成 はじめに、幅と高さを持つ部屋を円の中にランダムに配置しましょう。TKdevのアルゴリズムは、各部屋のサイズを生成するのに正規分布を用いています。これは一般的にとてもいいアイデアです。なぜかと言うと、これによってより多くのパラメータを扱うことができるようになるからです。幅/高さの平均と標準偏差間の異なる比率を選ぶと、通常は見た目の違うダンジョンとなります。 ここで実行すべき関数は getRandomPointInCircle です。 function getRandomPointInCircle(radius) local t = 2
【リスペクト】マリオメーカーに「65535+65535=131070」を計算させてみた
out of surviceさんの3+3=6動画(sm27235148)を見てすっかり影響され、とうとう動画作成に踏み切るなお動画作成に一番時間がかかったもよう個人的にはかなり小型化出来たと思っていますでももっと頭の回る人が更なる方式、更なる小型化を実現しそう論理回路の解説はリスペクト先の動画やウィキペディアを見てください論理回路はマイクラで少しかじった程度なのでもし間違ったところがあっても生暖かい目で見守ってやってください普段はマリオメーカーで難易度低めのステージ作ってますID:9D1A-0000-0051-3F77ID:C77C-0000-004E-2DE9
Segment Trees
Motivational Problems: http://www.spoj.pl/problems/BRCKTS/ http://www.spoj.com/problems/GSS3/ http://www.spoj.com/problems/HORRIBLE http://www.spoj.pl/problems/IOPC1207/ https://www.spoj.com/problems/GSS2/ http://www.spoj.com/problems/SEGSQRSS/ http://www.spoj.com/problems/ORDERSET/ http://www.spoj.com/problems/HELPR2D2/ http://www.spoj.com/problems/TEMPLEQ Segment trees (shortened as segtrees), a
Heavy Light Decomposition
Long post with lot of explanation, targeting novice. If you are aware of how HLD is useful, skip to “Basic Idea”. Why a Balanced Binary Tree is good? Balanced Binary Tree A balanced binary tree with N nodes has a height of log N. This gives us the following properties: You need to visit at most log N nodes to reach root node from any other node You need to visit at most 2 * log N nodes to reach fr
焼きなまし法でThomson問題の解を探索する - lan496の日記
Thomson問題 Thomson問題とは、三次元単位球の表面にN個の電荷の等しい粒子を配置するとき、クーロンポテンシャル\( U = \sum_{i < j} \frac{1}{|\rm{r}_{i} - \rm{r}_{j}|}\)が最小となる配置となるを求める問題です。詳しくはwikiをThomson problem - Wikipedia, the free encyclopedia。N=5のときにて三方両錐形が解になったり、N=8で立方体が解にならないなどいろいろと面白い問題です。 去年の12月頃、そもそもこの問題設定に名前が付いていることをある方から教えていただき、N=5の場合で実際に初期条件を与えて時間発展させることで本当に三方両錐形になるのか実験してみました。 球面上の点電荷が最も安定する配置(thomson problem)のRK4を利用したシミュレーションの進捗 pic
催促 - 対戦講座 : ぷよぷよ講座 | 壱大整域
とこぷよ等、邪魔するものが無い場合自分の連鎖のみ考えればいいのですが、実際の対戦では対戦相手がいます。なので対戦相手のことも考えなければいけません。ぷよぷよ(初代)では、相殺がないので、相手を埋められる量の連鎖(5連鎖)をすればいいですが、通以降は相殺があるので、当然勝つためには連鎖数が多ければ多いほどいいはずです。しかし、ある程度連鎖数が大きくなると、次の法則が成り立ちます。 後撃ち有利の法則 (以下、図は左を1P、右を2Pとします) 左図のように、今1Pが10連鎖、2Pが8連鎖を作っているとします。 当然10連鎖＞8連鎖だから、「今1Pが連鎖すれば1Pの勝ちだ」と思うかもしれません。 しかし、連鎖は発火してから終わるまで結構時間が掛かります。この間に2Pは連鎖を伸ばす事が出来ます。 だから、先に大連鎖を打ってしまうと相手に連鎖を伸ばされ、負けてしまうのです。 つまり、対戦では連鎖を後に
本当に実用的なたったひとつのソートアルゴリズム - CARTA TECH BLOG
コンテンツメディア事業本部の新卒エンジニア坂本がお送りいたします。 突然ですが、皆さんの好きなソートアルゴリズムはなんですか？ 私は基数ソートのスマートでストイックな雰囲気に惹かれます。 とはいえ、普段の開発では「どのソートアルゴリズムを使うか」を意識することは少ないのではないでしょうか。 むしろ現実世界で「トランプが全部揃ってるか」を手作業で確認するときとかのほうが、実はソートアルゴリズムが必要なのかもしれません。 ということで（？）、そのような現実的な場面で、本当に実用的なソートアルゴリズムを決める戦いが始まりました。 選手紹介 今回試したソートアルゴリズムは、独断と偏見で選んだ以下の5種類。 1 挿入ソート シンプル・イズ・ベスト！正直言ってベンチマークの噛ませ犬！ 2 クイックソート 「クイック」の名前はダテじゃない！王者の貫禄を見せてやれ！ 3 マージソート 安定感のある隠れた実
キャッシュフレンドリーな二分探索 ー データ構造を再考する | POSTD
現代のコンピュータのアーキテクチャに搭載されている高速のキャッシュメモリは、 参照の局所性 に優れた(＝一連のものとしてアクセスした要素が、互いに近いメモリのアドレスに配置されている)データ構造を好みます。これは、 Boost.Containerの平坦な（ツリー状ではない）連想コンテナ のようなクラスを陰で支えている理論的根拠です。要素を連続的に（かつ順序だてて）保存すると同時に、標準的なC++ノードベースの連想コンテナの機能性をエミュレートします。以下にあるのは、要素が0から30の範囲の時、 boost::container::flat_set の中で 二分探索 がどのように行われるのかを示した例です。 探索で目的の値を絞り込むにつれて、アクセスされる要素は次第に近くなっていきます。そのため、最初のうちは大きな距離を飛び越えていくような感じであっても、参照の局所性は このプロセスの最後の
ICPC国内予選F解説
強化学習のアルゴリズムの中で，複雑な環境の探索のために内発的報酬を用いているアルゴリズムを紹介した資料です．未知の状態への探索を促していることから「好奇心」を用いた探索とも呼ばれます．元々は別の場所で公開していた資料でしたが，いくつかの修正を加えて，こちらに改めてアップしました．
橋本環奈が司会でプログラミングの世界を紹介。NHK「アルゴリズミ子研究所」が話題
リンク 世界を変える魔法！ - NHK 世界を変える魔法！ アルゴリズミ子研究所 - NHK 世界は今アルゴリズムで動いている！世界経済からスマホ、家電まであらゆる物を動かすコンピュータプログラムの世界を紹介。 【案内役】橋本環奈、有野晋哉（よゐこ） 42 users 1524 sefuumi @sefuumi がっつり数学的な話でしょうか、それともアルゴリズムってスゲーって話でしょうか。どちらにしても気になるところ。ただ、子供に見せるには遅い時間。 世界を変える魔法！アルゴリズミ子研究所 ［Ｅテレ］9月30日(火)… plus.google.com/10758128188852… 2014-09-30 14:51:26
もし先輩女子エンジニアが『アルゴリズム』を図解で教えてくれるとしたら -
2014年7月30日より8月27日まで開催した、paizaオンラインハッカソン（略してPOH![ポー！]）Lite「天才火消しエンジニア霧島 もしPMおじさんが『丸投げ』を覚えたら」ですが、どのような解法が有ったのでしょうか。 今回もPOH恒例の「解説図解」を、天才火消しエンジニア霧島が解説するとしたら、という体で書いてみたいと思います。(特に文体とか変えませんがｗ 最後に霧島壁紙DLが有るので是非最後までお読みください。) ■どのような高速化ステップがあるのか？ 今回の問題ですが、実行時間に大きく影響する計算量別にみたアプローチでは、すべての組み合わせを出して、人数を満たして一番安い組み合わせを見つける全探索[計算量はO(2^N)]と、動的計画法[計算量はq = max(q_i) としてO(Nq) ]（やり方によってはO(NM)）による2種類があります。 また全探索を改良し、効率的な枝刈
組合せ最適化を使おう - Qiita
野菜の選び方はナップサック問題、乗り換え駅探索は、最短路問題といいます。典型問題は、よく研究もされているので、多くの場合、効率的な解法があります。あるいは、定式化がされているので、すぐ解くことができます。あとで、やってみましょう。ここで、あげている全ての典型問題の実行例は、典型問題と実行方法をご覧ください。 汎用問題 最近、私がやっているコンテナの仕事のお話しをします。 世界中の人たちが、いろいろなものを安く買えるのはコンテナ輸送のおかげです。中国などで生産したものを日本やアメリカやヨーロッパに、大量に安く運べるからです。でも、空のコンテナが、どんどんたまります。また中国に戻さないといけません。いつ、どこからどこに戻すかを決めるのが、最小費用流問題になります。ところが、最小費用流問題で表せない制約条件もあります。1 つが、カボタージュとよばれるものです。カボタージュというのは、国内のみの輸
【アルゴリズム】Project Euler Problem 15 解答:動的計画法を用いて40C20の値を求めてみた - データマイニングと数学の備忘録
2015-06-13 【アルゴリズム】Project Euler Problem 15 解答:動的計画法を用いて40C20の値を求めてみた C C言語 ProjectEuler 数学の問題をプログラムを使って解くサイト「Project Euler」。今回はその問題15とその解説をしたい。数学やProject Eulerやアルゴリズムに興味のある方は是非読んで欲しい。Problem 15Lattice paths Problem 15Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down,there are exactly 6 routes to the bottom right corner. How many such routes are ther
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
The Unhealthy Obsession with Tree Questions
Chromeのなかのコンピュータ・サイエンス
サルでも分かるwaifu2xのアルゴリズム.pdf - Google ドライブ
