[B! algorithm][C++] emonkakのブックマーク

emonkak id:emonkak

algorithmとC++に関するemonkakのブックマーク (8)

Home
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert
emonkak 2019/02/12
algorithm

c++
リンク
C++11 最近接偶数への丸め - Faith and Brave - C++で遊ぼう
C++11では<cmath>にいろいろ関数が追加されていますが、丸め演算も増えています。 C++11で最近接偶数への丸めを使いたい場合は、std::nearbyint() (near by int)という関数がありますので、それを使いましょう。 #include <iostream> #include <cmath> int main() { std::cout << std::nearbyint(2.5) << std::endl; // 2が出力される } 四捨五入も最近接偶数への丸めも、どちらも大きなくくりでは「round to nearest integer (最も近い整数への丸め)」に該当します。この2つの丸め方式は、中間値(0.5)の場合に動作が異なります：四捨五入は中間値の場合に、ゼロから遠い方向に丸められる (2.5だったら3になる) 最近接偶数への丸めは中間値の場合に、
emonkak 2016/12/20
c++

algorithm
リンク
Google Code Archive - Long-term storage for Google Code Project Hosting.
Code Archive Skip to content Google About Google Privacy Terms
emonkak 2013/02/09
c++

algorithm
リンク
Google Code Archive - Long-term storage for Google Code Project Hosting.
Code Archive Skip to content Google About Google Privacy Terms
emonkak 2013/02/02
c++

algorithm

library
リンク
try-and-back-off アルゴリズム - melpon日記 - HaskellもC++もまともに扱えないへたれのページ
C++11 には、複数の Lockable なオブジェクトをロックしてくれる std::lock 関数があります。 template<class L1, class L2, class... L3> void lock(L1& m1, L2& m2, L3&... m3); この関数の最大の特徴は、決してデッドロックしないことです。そして、このデッドロックしないという要件を満たすために使われるアルゴリズムが、try-and-back-off アルゴリズムと呼ばれるものです。今回はこの try-and-back-off アルゴリズムについて説明します。（この記事には独自解釈が含まれているので、間違ってる部分とかあれば指摘して頂けると嬉しいです）デッドロックの条件デッドロックは、正確ではないですが、大まかに言って以下の条件を満たすと発生します。ロックを取得するために待機を行なうあ
emonkak 2012/10/27
c++

algorithm
リンク
max_queue 最大値をいち早く返すデータ構造 - くまメモ
ちょっとマニアックなデータ構造を紹介その名もmax queue、使い勝手はほとんどFIFOなqueueと一緒で、enqueue()もdequeue()もO(1)だけどそれに加えて「入ってるデータのうち最大の値」もO(1)の計算量で算出するという代物。兄弟分で最小の物を返すmin queueや、両方の機能を備えたmin-max queueもあるけどmax queueが判れば自明なので割愛。最大の値を覚えておけば良いだけに思えるけど、最大の値がdequeueされてしまった場合にO(n)の時間を掛けて再び探索してたら条件を満たせない。 max-queueでは最大の値を覚えておくため専用のqueue（以後最大値queueと呼ぶ）を内部でもう一本持つ。この青い線がqueueに入ってるデータ列で高さがデータの大きさを表す、下に書かれている薄い線の入ったデータ列が最大値queue。こちらの最大
emonkak 2012/10/09
algorithm

c++
リンク
C++でPurely Functional Random-Access Listなるものを実装してみた - IT系で覚醒めたい
先日の夏のプログラミングシンポジウムという会に参加したときにkinabaせんせーに布教されてずっとpurely functionalなデータ構造について調べてた。 stack,linkedlistはもちろんqueue/dequeにも永続的データ構造があってまぁそれはそれで面白いんだけどやっぱり一番気になるのがvectorの実装。そのvectorの実装にもいくつも種類があるらしく、clojureの32分木のpersistentvectorもその一つだとか。調べていくとsrfi-101のrandom access listもそのうちのひとつだと気づいたので面白半分に実装してみた。 srfi-101 http://srfi.schemers.org/srfi-101/srfi-101.html gist 実装は原論文(http://citeseerx.ist.psu.edu/viewdoc/
emonkak 2012/08/28
algorithm

c++
リンク
wat-array : wavelet木を利用した高速配列処理ライブラリ - Preferred Networks Research & Development
こんにちは岡野原です。もう年末になりましたが、私の今年はこれからです。 wat-arrayというC++ライブラリを公開しました。 google code:wat-array wat-arrayはフリーソフトウェアであり、修正BSDライセンスに基づいて利用できます． wat-arrayはwavelet木と呼ばれるデータ構造を利用することにより、配列上の様々な処理を効率的に行うことができるC++ライブラリです。例えば、 – 任意の連続した範囲内にある最大値 /最小値 / k番目に大きい値, またそれらの出現位置、頻度 – 任意の連続した範囲内にある指定した文字cの出現回数、c未満/より大きい文字の出現回数 – 任意の文字のi番目の出現位置といったものを求めることが全て範囲長、入力長に対して定数時間で行うことができます。例えば長さ10億、値の範囲が0から1000万であるような配列A中のA[
emonkak 2010/12/18
C++

library

algorithm
リンク
1