ブルームフィルタ - Wikipedia
この項目では、確率的データ構造について説明しています。画像にぼかし効果を付加する画像フィルタについては「川瀬のブルームフィルター」をご覧ください。 ブルームフィルタ（英語: Bloom filter）は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、あるデータが集合の要素である（集合に含まれている）かどうかの判定に使われる。ただし判定は正確ではなくて、含まれていないのに含まれていると誤って判定すること偽陽性（false positive）の可能性がある。しかし含まれているものを含まれていないと誤判定すること偽陰性（false negative）はない。なお集合に要素を追加することはできるが、集合から要素を削除することはできない（ただし、拡張をした counting filter であれば削除もできる）。集合に要素を追加していくにつれて偽陽性の
)
トライ (データ構造) - Wikipedia
"A", "to", "tea", "ted", "ten", "i", "in", "inn" というキー群によるトライ木 トライ木（英: trie）やプレフィックス木（英: prefix tree）とは、順序付き木の一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス（接頭部）があり、ルート（根）には空の文字列が対応している。値は一般に全ノードに対応して存在するわけではなく、末端ノードや一部の中間ノードだけがキーに対応した値を格納している。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置とキーが対応している。 キーが文字列である連想配列の実装構造としても使われる。右図の例では、ノードを表す丸の中にキーが書かれ、連想される値がその下に書かれている。値が書かれていないノードはキー文字列の途中までにしか対応していない。各英単語
三分探索木 - Wikipedia
三分探索木（さんぶんたんさくぎ、英: ternary search tree）は、トライ木の各ノードを二分探索木として表現したデータ構造である。各ノードは文字列中の文字と以下の三つの子ノードを持つ。 その文字の代わりに、より小さな文字を指す左ノード その文字の代わりに、より大きな文字を指す右ノード その文字の次の文字を指す中央ノード 他のトライ木構造と同じく、三分探索木の各ノードは格納された文字列の接頭辞に対応している。中央ノードに格納された木は、そこに至るまでのノードを共通接頭辞として持つ。 c / | \ a u h | | | \ t t e u / / | / | s p e i s 上記の三分探索木は "as", "at", "cup", "cute", "he", "i", "us" が値として格納されている。三分探索木から値を取得するには次のような操作を行う。 頂点ノードから
Evaluation strategy - Wikipedia
In a programming language, an evaluation strategy is a set of rules for evaluating expressions.[1] The term is often used to refer to the more specific notion of a parameter-passing strategy[2] that defines the kind of value that is passed to the function for each parameter (the binding strategy)[3] and whether to evaluate the parameters of a function call, and if so in what order (the evaluation
BBPアルゴリズム
はじめに 円周率の小数点以下d桁目を求めるためには、1,2,3,...,d-1桁目を計算しなければならないと考えられてきました。ところが1995年にSimon Plouffe(プラウフ)により発見された公式を用いると、円周率の16進数表示のd桁目をピンポイントに求められることが分かりました。この公式は、今日BBP(Bailey-Borwein-Plouffe)公式と呼ばれています。公式を次に示します。 まず、とおきます。xの小数部分を{x}としますと、円周率の小数点以下d+1桁目が知りたいときは、{16dπ}を求めればよいことが分かります。BBP公式を用いると、{16dπ}は、 と表されます。最後に4を足しているのは、例えば、たまたま{S1}=0.00111、{S4}=0.98891、{S5}=0.89991、{S6}=0.90361、となったとき、本来4S1-2S4-S5-S6は正の数に
Reddit - Dive into anything
The subreddit covers various game development aspects, including programming, design, writing, art, game jams, postmortems, and marketing. It serves as a hub for game creators to discuss and share their insights, experiences, and expertise in the industry. So today I'm going to be a little different and talk about one technical aspect of my game TinyKeep, that is random procedural dungeon generati
Fowler–Noll–Vo hash function - Wikipedia
Fowler–Noll–Vo (or FNV) is a non-cryptographic hash function created by Glenn Fowler, Landon Curt Noll, and Kiem-Phong Vo. The basis of the FNV hash algorithm was taken from an idea sent as reviewer comments to the IEEE POSIX P1003.2 committee by Glenn Fowler and Phong Vo in 1991. In a subsequent ballot round, Landon Curt Noll improved on their algorithm. In an email message to Landon, they named
Token bucket - Wikipedia
The token bucket is an algorithm used in packet-switched and telecommunications networks. It can be used to check that data transmissions, in the form of packets, conform to defined limits on bandwidth and burstiness (a measure of the unevenness or variations in the traffic flow). It can also be used as a scheduling algorithm to determine the timing of transmissions that will comply with the limit
Amazonの推薦システムの20年
IEEE Internet Computingの2017年5・6月号に "Two Decades of Recommender Systems at Amazon.com" という記事が掲載された。 2003年に同誌に掲載されたレポート "Amazon.com Recommendations: Item-to-Item Collaborative Filtering" が Test of Time、つまり『時代が証明したで賞』を受賞したことをうけての特別記事らしい 1。 「この商品を買った人はこんな商品も買っています」という推薦で有名なAmazonが1998年にその土台となるアルゴリズムの特許を出願してから20年、彼らが 推薦アルゴリズムをどのような視点で改良してきたのか 今、どのような未来を想像するのか その一端を知ることができる記事だった。 アイテムベース協調フィルタリング 20年前も
What's new in purely functional data structures since Okasaki?
Since Chris Okasaki's 1998 book "Purely functional data structures", I haven't seen too many new exciting purely functional data structures appear; I can name just a few: IntMap (also invented by Okasaki in 1998, but not present in that book) Finger trees (and their generalization over monoids) There are also some interesting ways of implementing already known datastructures, such as using "nested
H.264の秘密 | POSTD
(編注：2020/08/18、いただいたフィードバックをもとに記事を修正いたしました。) (2016/12/11、いただきましたフィードバックをもとに翻訳を修正いたしました。) H.264は、動画圧縮コーデックの標準規格です。ネット上の動画、Blu-ray、スマホ、セキュリティカメラ、ドローンなどなど、今やあらゆるところでH.264が使われています。 H.264は注目すべき技術のひとつです。たったひとつの目標、つまりフルモーションビデオの送信に要するネットワーク帯域を削減することを目指した30年以上の努力の結晶なのです。 技術的な面でも、H.264はとても興味深い規格です。この記事では、その一部について概要レベルでの知識を得られることでしょう。あまり複雑だと感じさせないようにするつもりです。今回おはなしする概念の多くは動画圧縮全般にあてはまるものであり、H.264に限ったものではありません
Generating fantasy maps
mewo2.com is the website of Martin O'Leary artist, designer, teacher, researcher These are some notes on how I generate the maps for my Twitter bot @unchartedatlas, which is based on a generator I originally produced during NaNoGenMo 2015. There's JavaScript code for the generator on Github here, and the original messy Python generator code can be seen here. You may also be interested in this comp
Connected-component labeling - Wikipedia
Connected-component labeling (CCL), connected-component analysis (CCA), blob extraction, region labeling, blob discovery, or region extraction is an algorithmic application of graph theory, where subsets of connected components are uniquely labeled based on a given heuristic. Connected-component labeling is not to be confused with segmentation. Connected-component labeling is used in computer visi
kd木 - Wikipedia
3次元のkd木。根セル（白）をまず2つの部分セルに分割（赤）し、それぞれをさらに2つに分割（緑）している。最後に4つのセルそれぞれを2つに分割（青）している。それ以上の分割はされていないので、最終的にできた8つのセルを葉セルと呼ぶ。黄色の球は木の頂点を表している。 kd木（英: kd-tree, k-dimensional tree）は、k次元のユークリッド空間にある点を分類する空間分割データ構造である。kd木は、多次元探索鍵を使った探索（例えば、範囲探索や最近傍探索）などの用途に使われるデータ構造である。kd木はBSP木の特殊ケースである。 kd木は、座標軸の1つに垂直な平面だけを使って分割を行う。BSP木では分割平面の角度は任意である。さらに一般的には、kd木の根ノードから葉ノードまでの各ノードには1つの点が格納される[1]。この点もBSP木とは異なり、BSP木では葉ノードのみが点（ま
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Data Structures in JavaScript: Arrays, HashMaps, and Lists
遺伝的FM音源