有向非巡回グラフ - Wikipedia
有向非巡回グラフの例。この例は連結グラフであるが、非連結な有向非巡回グラフも存在する。 有向非巡回グラフ、有向非循環グラフ、有向無閉路グラフ（ゆうこうひじゅんかいグラフ、英: Directed acyclic graph, DAG）とは、グラフ理論における閉路のない有向グラフのことである。有向グラフは頂点と有向辺（方向を示す矢印付きの辺）からなり、辺は頂点同士をつなぐが、ある頂点から出発し、辺をたどり、頂点に戻ってこないのが有向非巡回グラフである[1][2][3]。 有向非巡回グラフは様々な情報をモデル化するのに使われる。有向非巡回グラフにおける到達可能性は半順序を構成し、全ての有限半順序は到達可能性を利用し有向非巡回グラフで表現可能である。順序づけする必要があるタスクの集合は、あるタスクが他のタスクよりも前に行う必要があるという制約により、頂点をタスク、辺を制約条件で表現すると有向非巡回
Lowest common ancestor - Wikipedia
In this tree, the lowest common ancestor of the nodes x and y is marked in dark green. Other common ancestors are shown in light green. In graph theory and computer science, the lowest common ancestor (LCA) (also called least common ancestor) of two nodes v and w in a tree or directed acyclic graph (DAG) T is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each
平衡二分探索木 - Wikipedia
平衡二分探索木（へいこうにぶんたんさくぎ、英: self-balancing binary search tree）とは、計算機科学において二分探索木のうち木の高さ（根からの階層の数）を自動的にできるだけ小さく維持しようとするもの（平衡木）である。平衡二分探索木は連想配列や集合その他の抽象データ型を実装する最も効率のよいデータ構造の1つである。 概要[編集] 二分探索木上の大半の操作にかかるコストは木の高さに比例するので木の高さは低く保つのが望ましい。通常の二分探索木の主要な欠点は、キーが辞書順に挿入されるような普通の状況で木の高さが大きくなってしまうということである。結果として連結リスト同様のデータ構造になってしまい、全ての操作が高くつく結果となる。もしあらかじめ全てのデータが分かっているならば、値をランダムに追加することで木の高さを平均的に小さく保つことができるが、そのような贅沢はいつ
Ruby製のシンプルなワークフローエンジンRukawaの紹介 - Qiita
Bigqueryを使ったバッチジョブを色々と実行しているのですが、Rakeで複雑な依存関係を管理したり、並列実行させたりするのが辛くなってきたのでRukawaというワークフローエンジンを自作しました。 自作したのは、RailsプロダクトにAirflowとかLuigiとかAzkabanとか入れるにはちょっと重厚過ぎる感じだったのと、Rubyで書ける方が楽で良いやという理由からです。 RukawaとはRUby KAntan Workflow Assistantの略です(後付け) (本当はミッチーとか水戸の方が好きなんだけど良い名前が浮かばなかった) 実際は、並列実行を可能にして書き方を変えてみたRakeとそんなに大差無い。 Rukawaの機能 ジョブの定義 まず実行したい処理をジョブクラスに記述します。 module ExecuteLog def self.store @store ||= {
隣接リスト - Wikipedia
計算機科学において、隣接リストはグラフを表すデータ構造と密接な関係がある。隣接リスト表現では、各頂点について、1つの辺でその頂点とつながっている全ての他の頂点のリストを作る（これがその頂点の「隣接リスト」である）。例えば、ヴァンロッサムが示唆した表現では、各頂点とその隣接する頂点群の配列をハッシュテーブルで関連付ける[1]。これは隣接リスト表現のインスタンスの1つと考えられる。また、Cormen らの表現では、頂点の番号をインデックスとする配列に各頂点の隣接する頂点群の片方向リストへの参照を格納する[2]。 隣接リスト構造の問題点は、グラフの辺についてのデータ（例えば、長さ、コストなど）を格納する明確な場所がない点である。その解決策として、例えば Goodrich と Tamassia の著書では、よりオブジェクト指向的に隣接リスト構造を変形し、各頂点に接合する辺を表したオブジェクトのリス
Breadth-first search - Wikipedia
Animated example of a breadth-first search. Black: explored, grey: queued to be explored later on BFS on Maze-solving algorithm Top part of Tic-tac-toe game tree Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next
Depth-first search - Wikipedia
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. Extra memory, usually a stack, is needed to keep track of the nodes discovered so far along a specified branch which he
NetworkX - Wikipedia
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article may rely excessively on sources too closely associated with the subject, potentially preventing the article from being verifiable and neutral. Please help improve it by replacing them with more appropriate citations to reliable, inde
Recurrent Nets and their Computational Graph — Chainer 1.3.2 documentation
Recurrent Nets and their Computational Graph¶ In this section, you will learn how to write recurrent nets with full backprop, recurrent nets with truncated backprop, evaluation of networks with few memory. After reading this section, you will be able to: Handle input sequences of variable length Truncate upper stream of the network during forward computation Use volatile variables to prevent netwo
第六回闇PHP勉強会の発表資料まとめ - hnwの日記
昨日11/22(日)に第六回闇PHP勉強会が開催されました。PHPの勉強会なのにPHPのコードが全部で10行も登場しないという毎度おなじみの展開でしたが、たくさんの方にご参加頂きました。本当にありがとうございました。 では、発表を順に紹介します。 @hnw 「OPcacheの新機能ファイルベースキャッシュの内部実装を読んでみた」 まずは僕の発表からでした。PHP7からの新機能であるOPcacheのファイルベースキャッシュについてソースコードを交えて仕組みを紹介しました。本機能について、個人的には若干ネガティブに見ていますが、今後「こういう状況では確かに便利だ」という事例が出てくれば判断も変わると思います。 @noldorinfoさん「SQLite2と3のエスケープ関数の違いとその対策」 SQLite3のエスケープ関数がSQLite2のものと実装が変わっており、バイナリアンセーフになっていて
二分木 - Wikipedia
簡単な二分木。大きさ9、深さ3、根は値2を持つ 二分木（にぶんぎ）は、データ構造の1つである。二進木（にしんぎ）やバイナリツリー（英: binary tree）とも呼ばれ、根付き木構造の中で、全てのノード（節点 node）が持つ子の数が高々2であるものをいう。典型的には2つの子はそれぞれ「左」「右」と呼ばれる。 たとえば、二分探索や二分ヒープを実装するために使われる。 以後、括弧の中は英語表記。 親から子へ有向線分（辺、エッジ edge）が引かれる。子を持たないノードを葉（リーフ leaf）ないし外部ノード (external node) と呼ぶ。葉でないノードを内部ノード (internal node) と呼ぶ。あるノードの「深さ」(depth) はルート（root 「根」にあたるノード）からそのノードまでにたどる経路（パス path）の長さ（経路の種類ではなく、ノード-ノードを1と数え
Binary tree - Wikipedia
A labeled binary tree of size 9 (the number of nodes in the tree) and height 3 (the height of a tree defined as the number of edges or links from the top-most or root node to the farthest leaf node), with a root node whose value is 1. The above tree is unbalanced and not sorted. In computer science, a binary tree is a tree data structure in which each node has at most two children, referred to as
抽象構文木 - Wikipedia
抽象構文木（ちゅうしょうこうぶんぎ、英: abstract syntax tree、AST）は、通常の構文木（具象構文木あるいは解析木とも言う）から、言語の意味に関係ない情報を取り除き、意味に関係ある情報のみを取り出した（抽象した）木構造の木である。 理論的には、有限なラベル付き有向木である。また、演算子と変数や定数といったオペランドから成る数式などのようなものに対する抽象構文木を例にすると、分枝点は演算子、葉はオペランド（つまり、変数や定数）である。 抽象構文木は、構文解析によって直接得られる具象構文木と、最終的な意味表現などのデータ構造との、中間にあるものと位置付けることができる。コンパイラやインタプリタといったプログラミング言語処理系の場合は、中間表現のひとつであり、一部の最適化は抽象構文木の上の操作などによっておこなわれる。具象に対する構文がたとえばBNFによって規定されるように、
Building a Binary Tree with Enumerable | Mike Perham
2014-11-26 I believe that the Enumerable module is the most important thing to understand if you want to go from a beginner to intermediate Rubyist. It requires you to understand two fundamental parts of Ruby: modules and blocks. Ruby’s standard library includes hashes, arrays, sets and thread-safe queues. One structure missing is a generic binary tree. Binary trees are great general purpose data
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
jfp1100010a
recursion-drill/drill/11.md at main · kazu-yamamoto/recursion-drill
Weighted Tree -- from Wolfram MathWorld
Weighted Tree - vizuly.io
Weight-balanced tree - Wikipedia
GitHub - dirkholzapfel/abuelo: Abuelo is a graph theory library
