トポロジカルソートと強連結成分分解でWikipediaの特定カテゴリー配下のページをすべて取得する - 終末 A.I.
Wikipediaの特定カテゴリー配下のページをすべて取得するためには、整理されていないグラフデータ特有のいくつかの問題に向き合う必要があります。 一つは、Category:カツラ科と糸井の大カツラのように、サブカテゴリーにはページへのリンクが含まれているが、カテゴリー本体にはページへのリンクが含まれていないケースがあるという問題。 もう一つは、Category:インフォグラム・エンターテインメントームソフトとCategory:アタリのゲームソフトのように、お互いがお互いのサブカテゴリーに含まれてしまっているケースがあるという問題です。 これらの問題は、以下の手順を踏むことで解決できます。 カテゴリーにリンクされているページだけでなく、サブカテゴリー内のリンクを順にたどって含まれるすべてのページを収集する ただし、一度たどったカテゴリーに再度到達した場合、それ以上はそのルートを探索しない
こんなプログラムはいやだ: 負の剰余 - bkブログ
こんなプログラムはいやだ: 負の剰余 知人から次の式の計算結果はどうなるかという問題を出されました。 -3 % 5 3 % -5 -3 % -5 降参して答えを尋ねたところ、問題を出した方も答えを知らないことがわかりました。そこで、いくつかの言語処理系で結果を調べてみました。手元の環境 (Intel Xeon 上の Debian GNU/Linux sarge) で調べると2つのグループに分かれました。 C (GCC 3.3.5) Java (Sun JDK 1.5.0_05) PHP 4.3.10-16 Emacs 22.0.50.2 Ruby 1.8.2 Python 2.3.5 Perl 5.8.4
アルゴリズムとデータ構造から理解するRedis / Learn Redis from Internal Algorithms and Data Structures
2019年新卒研修で使った資料です。 内部実装の雰囲気を感じとりながら、Redisについて理解を深める研修を行いました。 以下の内容について学びました。 1. Redisの概要 2. 社内での利用方法 3. 正しい用法用量 Redis についての前提知識は必要としていません。…
TRIE-Optimized Regexp : 404 Blog Not Found
2005年09月11日07:06 カテゴリLightweight Languages TRIE-Optimized Regexp これをPerlで直接使えたらうれしいよね＞おおる きまぐれ日記: はてなキーワードを高速に付与 そこで、はてなキーワードを TRIE を使って付与するプログラムを作ってみました。 というわけで、やってみました。 最初はDartsのXSを作ろうとしたのだけど、どうもtemplateばりばりのC++コードとXSは相性が悪い。でもTrieを作るだけなら、Perlでもそこそこ出来るし、実際Regexp::OptimizerやRegexp::Assembleのようなモジュールもある。ただこれらはTrie以外のOptimizeもしてしまうので、ちょっと重たいというわけで、mk_trie_regexp.plというScriptをサクっと書いてみました。 使い方は簡単。/usr/
きまぐれ日記: Autolink: 前方最長一致ではなく最長キーワード優先一致を実現する
Hatena のキーワード置換アルゴリズムがTRIE ベースの手法に変更になったようです。以前に AC法でやる方法の記事を書いたのですが、それと似たことをやってるのでしょうか。 AC法のやり方は単純で、前方から最長一致でキーワードを見つけていきます。これまでは長いキーワードから順番に見つけていく方法(最長キーワード優先一致)だったそうですが、前方から見つけていく方法だと短いキーワードが優先される場合があります。 http://d.hatena.ne.jp/ita/20060119/p1 http://d.hatena.ne.jp/hatenadiary/20060119/1137667217 本文：あいうえおかきくけこさしすせそ KW1 いう KW2 うえおかき KW3 かきく KW4 きくけこさし という文でKW1-KW4のキーワードがマッチする場合、新しくなった方法では「いう」と「かき
ブラックホール撮影にも使える「スパースモデリング」とは？【機械学習】 - ざるご博士になりたいブログ
この記事は移転しました。約2秒後に新記事へ移動します。移動しない場合はココをクリックしてください。 どうもざるご（@zalgo3）です． 世界初のブラックホール撮影の成功例が出たようです． ブラックホールの撮影に成功 世界初 一般相対性理論を証明 - 毎日新聞 今回のブラックホール撮影は，スパースモデリングという機械学習技術を取り入れたことによる貢献が大きいようです． 天文学に計算機科学の知識が取り入れられて，大きな成果が出たというのは，驚くべきことだと思います． 今回はそんな大成功を巻き起こした「スパースモデリング」について解説していきます． スパースモデリングとは スパースモデリングとは，誤解を恐れずにざっくりいうと解けない連立一次方程式を無理やり解くための仕組みです． 次のような連立一次方程式を考えます． この方程式は，が逆行列を持つときに解くことができて， となります．では，が逆行
Dijkstra法に関するn考察 〜前半〜 - Mister雑記
(思ったより長くなりそうだったので前半と後半に分けることにしました。 後半の投稿予定は未定です。) 競技プログラミングのグラフ問題でしばしば題材となるアルゴリズム「Dijkstra法」。 その名前のインパクトと汎用性から比較的知名度が高いアルゴリズムだが、実装がそこそこ重いため初心者の壁となることもある。 そんなDijkstra法について、私の持つ知識、イメージを適当に書き連ねていこうと思う。 目次 目次 Dijkstra法の概要 何をするアルゴリズムか 具体例 イメージ？ 実装方法 パターンA パターンB (PFS) 計算量の比較 問題例 後半について Dijkstra法の概要 何をするアルゴリズムか Dijkstra法を一言で説明するなら「重み付きグラフにおいて、ある頂点から他の全ての頂点までの最短距離を求める」アルゴリズムである。 一工夫すれば最短距離を実現する経路も同時に求められる
ダイクストラとポテンシャルのはなし - niuez’s diary
はじめまして, niuezといいます. 競プロを少ししています. 最近勉強したことのメモ書きをしておきます. ダイクストラ法 ダイクストラ法(Dijkstra)は負の長さの無いグラフで始点からの最短距離を求めるアルゴリズムです. 具体的には 距離が未確定の頂点の中で一番小さいものを選び, 距離を確定させる. 選んだ頂点から距離が未確定の頂点に伸びる辺で, 未確定な距離をより短いものに更新する. を繰り返します. これを実装すると $O(N)$ですが, よく知られるダイクストラの計算量は $O((E+ V) \log E)$ です(heapとかを使う). #include <set> #include <queue> #include <vector> struct edge { int u,v; int dist; }; std::vector<int> dijkstra(const st
CodeChef GPD Gotham PD - kazuma8128’s blog
問題文 https://www.codechef.com/problems/GPD 問題概要 頂点数 N の根付き木が与えられる. 各頂点には正整数のキーが付いている. 以下の二種類の Q 個のクエリをオンラインで処理せよ. クエリ１：頂点 v の子に, キー k の付いた新しい頂点 u を増やす クエリ２：頂点 v から根までのパスに含まれる頂点に付いたキーの中で, k でXORしたときの最大の値と最小の値を求める 制約：1 ≤ N ≤ 10^5, 1 ≤ Q ≤ 2*10^5, 1 ≤ (各キー) ≤ 2^31-1 解法 まず, トライ木を使うと, 要素の挿入 (insert) , 要素の削除 (erase) , ある値でXORしたときの最大値/最小値の取得が O(ビット数) でできます. 詳しくは以下のページなどを参照 www.geeksforgeeks.org これを使って根からD
非負整数値を扱う Trie について - kazuma8128’s blog
はじめに 非負整数を二分木のトライ木で管理するアレに関する日本語記事があんまり無いっぽいので雑にメモ. （というかそもそも専用の呼び名ないのかな？） とりあえずここでは Binary Trie って呼んどきます. Binary Trie とは 整数をビット列とみなしてトライ木っぽく持つ set 的なことができるデータ構造です. 正確には要素の重複を許す multiset っぽく実装することが多そう. 整数集合を管理できますが, 平衡二分木よりも実装が楽なので最高です. こんな感じ ノードに書いてある数字は部分木に含まれる要素の個数です. できること ビット長を B とすると, 以下の操作が全て O(B) でできます. insert(x) : 値 x を集合に（一つ）追加 erase(x) : 値 x を集合から（一つ）削除 max_element/min_elemet() : 集合内の最大
スライド区間に対するクエリのまとめ
スライド区間に対するクエリ処理の種類とそれに対するアルゴリズムをいくつか紹介します。まず、「スライド区間」の定義ですが、窓関数のようなものを想像してください。例えば、[2,5,10,-1,0,4,...]というデータに対してサイズ3の窓関数をスライドさせると、[2,5,10], [5,10,-1],[10,-1,0],.....と複数の連続する区間ができます。これらの区間に対して以下のようなクエリを考えます。 データサイズが小さい場合は愚直な方法で計算しても問題ありませんが、データサイズが大きい場合やオンライン処理で次々にデータが来る場合は高速な処理が求められます。天気予報システムや金融システムなどではこのような需要があると思います。例えば、ある時間幅内での最高気温・最低気温・平均気温を計算したり、リアルタイムに株価の高値・低値を計算するなどです。
アルゴリズムの勉強は必要か？不要である3つの理由
アルゴリズムとは？ アルゴリズムとは、ある問題を解く具体的な手順のことです。 プログラミングの世界では、効率的な解法のことを指すことがあります。 有名なアルゴリズムだと、クイックソートと呼ばれるものがあります。 これは、その名の通り、数列を効率的にならべるアルゴリズムです。 また、私が初心者のころ 優秀なプログラマーになるためにはアルゴリズムが必要 と思ってアルゴリズムを勉強した覚えがあります。 しかし、今思えば 学習コストのわりにあまり役立たない知識 だったなという印象です。 今回はその理由を説明します。 現在、プログラミングをはじめたてでアルゴリズムを勉強しようとしてる方は必見。 たいていのアルゴリズムは実装されている ほとんどのアルゴリズムは発見された時点で実装済です。 ましてや、本に載ってるようなアルゴリズムは、 どんな言語でも標準モジュールに実装されていることがほとんどです。 そ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
じゃがりきん on Twitter: "～迷路を簡単に解くアルゴリズム～ https://t.co/PLJq5SwWif"
next_permutationがイマイチよくわからなかったのでまとめてみた - Qiita
VP trees: A data structure for finding stuff fast
untitled
Animation of Aho-Corasick string matching algorithm
乱択アルゴリズム紹介(行列乗算の検査&多項式等価性の検査) - Preferred Networks Research & Development
数列の任意の範囲で大きいほうから任意の個数のsumをO(1)で求める（注：O(logワードサイズ)です） - 誤読
GitHub - liyin2015/python-coding-interview: A middle-to-high level open source algorithm book designed with coding interview at heart!
