blog :: Brent -> [String] - Competitive Programming in Haskell: stacks, queues, and monoidal sliding windows
Competitive Programming in Haskell: stacks, queues, and monoidal sliding windows Suppose we have a list of items of length \(n\), and we want to consider windows (i.e. contiguous subsequences) of width \(w\) within the list. ⊕A list of numbers, with contiguous size-3 windows highlighted We can compute the sum of each window by brute force in \(O(nw)\) time, by simply generating the list of all the
セグメント木を徹底解説！0から遅延評価やモノイドまで | アルゴリズムロジック
セグメント木とは セグメント木とは、完全二分木（全ての葉の深さが等しい木）によって実装された、区間を扱うのに適したデータ構造のことです。 区間に対する操作を対数時間 O(log n) で行えることが特徴で、競技プログラミングなどで頻出となっています。 セグメント木でできること セグメント木は、区間に対する操作やクエリを行うことができます。 特に、 区間上の値を更新する任意の区間上の最小値や合計値などを取得する などが対数時間でそれぞれ行えるのが強みです。 区間上の合計値などは、累積和などを使えば前処理 O(N) ・クエリ O(1) で取得することもできます。しかし、区間上の値の更新と、合計値の取得が入り乱れるような時は、セグメント木の方が有効になることが多いです。 以下では説明のために、区間上の最小値 Range Minimam Query(RMQ) を扱うセグメント木を例として説明します
Monoidify! Monoids as a Design Principle for Efficient MapReduce Algorithms
It is well known that since the sort/shuffle stage in MapReduce is costly, local aggregation is one important principle to designing efficient algorithms. This short paper represents an attempt to more clearly articulate this design principle in terms of monoids, which generalizes the use of combiners and the in-mapper combining pattern.
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Monoid-augmented FIFOs, deamortised - Paul Khuong: some Lisp
https://izbicki.me/public/papers/icml2013-algebraic-classifiers.pdf
