)
除算 (デジタル) - Wikipedia
数値的（ディジタル）な除算アルゴリズムはいくつか存在する。それらのアルゴリズムは、低速な除算と高速な除算の2つに分類できる。低速な除算は反復する毎に最終的な商を1桁ずつ生成していくアルゴリズムである。回復型、不実行回復型、非回復型、SRT除算などがある。高速な除算は最初に商の近似値から出発して徐々に正確な値に近づけていくもので、低速な除算よりも反復回数が少なくて済む。ニュートン-ラプソン法とゴールドシュミット法がこれに分類される。 以下の解説では、除算を で表し、 Q = 商 (quotient) N = 被除数（分子 = numerator） D = 除数（分母 = denominator） とする。 procedure divide_unsigned(N, D: unsigned_integer; var Q, R: unsigned_integer); const n = 32; (
Golangの新しいGCアルゴリズム Transaction Oriented Collector（TOC）
http://golang.org/s/gctoc Goの新しいGCのProposalが出た．まだProposal段階であり具体的な実装はないが簡単にどのようなものであるかをまとめておく． GoのGCはGo1.5において単純なStop The World（STW）からConcurrent Mark & Sweepへと変更され大きな改善があった（詳しくは“GolangのGCを追う”に書いた）．先の記事に書いたようにGo1.5におけるGCの改善は主にレイテンシ（最大停止時間）に重きが置かれいた．数値目標として10msが掲げられGo1.6においては大きなヒープサイズ（500GB）においてそれを達成していた． GCの評価項目はレイテンシのみではない．スループットやヒープの使用効率（断片化の対処）なども重要である．Go1.6までのGCではそれらについて大きく言及されていなかった（と思う）．例えばスル
トップページ | Programming Place Plus アルゴリズムとデータ構造編
トップページ ここは、Programming Place Plus の、アルゴリズムとデータ構造編のトップページです。 各種アルゴリズムとデータ構造に関して、詳細な解説や、Ｃ言語を使った具体的な実装例があります（Ｃ言語についての情報は、Ｃ言語編を参照してください）。 データ構造 整列アルゴリズム 探索アルゴリズム その他のアルゴリズム APPENDIX リンク集 参考書籍
ローグライクゲームのダンジョン自動生成アルゴリズムまとめ - NinaLabo
ローグライクゲームのダンジョンマップを自動生成するにあたり、参考にさせていただいたページをまとめておきます。 《マップを2分割していく方法》 大きいマップをどんどん2分割していくことで、不思議のダンジョンのようなマップを自動生成できます。開発中のローグライクゲームも、ここにある方法を採用しました。 ◼Racanhackコード解説 ローグライクゲームRacanhackのソースコードを解説した記事。特にダンジョンマップの自動生成に関するアルゴリズムの解説記事が詳しくてわかりやすいのですが、何故かページのテキストエンコーディングがEUC。 ◼アルゴリズム - 不思議なダンジョンの作り方 (Unity2Dサンプルコードつき) - Qiita Unity (C#) のサンプルコード付き！自前で実装した後にこの記事を見つけたのが悔やまれます... ◼ゲームプログラマーを目指すひと ランダムダンジョン生
最近よく聞くQuorumは過半数(多数決)よりも一般的でパワフルな概念だった - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 最近では珍しくもなくなった"Quorum"という言葉。Zookeeper, etcd, Serfといったクラスタ中でデータのレプリケーションを行ってくれるようなツールや、Cassandra, Riakといった分散データベース(NoSQL系)のようなツールにおいても、データの複製に一貫性を持たせる仕組みとしてよく聞かれます。 しかしながら、多くのスライドやWebの記事を読んでも、"Quorum"という語が意味するところは要するに「過半数ノードによる多数決」というような説明が多いように感じていました。 にも関わらず、"Quorum"と呼ばれ
計算グラフの微積分：バックプロパゲーションを理解する | POSTD
はじめに バックプロパゲーションとは、ディープモデルの学習を計算可能にしてくれる重要なアルゴリズムです。最近のニューラルネットワークではバックプロパゲーション (誤差逆伝播法) を使うことで、最急降下法による学習が愚直な実装と比べて1000万倍速くなります。 例えば，バックプロパゲーションでの学習に1週間しかかからないのに対して、愚直な実装では20万年かかる計算になります。 ディープラーニングでの使用以外にも、バックプロパゲーションはさまざまな分野で使えるとても便利な計算ツールです。それぞれで呼ばれる名称は違うのですが、天気予報から、数値的安定性を分析する時にまで多岐にわたり使用できます。実際に、このアルゴリズムは、いろいろな分野で少なくとも20回は再開発されています（参照： Griewank（2010） ）。一般的な用途自体の名前は”リバースモード微分”といいます。 基本的に、この技術は
1024cores - Non-intrusive MPSC node-based queue
Advantages: + Waitfree and fast producers. One XCHG is maximum what one can get with multi-producer non-distributed queue. + Extremely fast consumer. On fast-path it's atomic-free, XCHG executed per node batch, in order to grab 'last item'. + No need for node order reversion. So pop operation is always O(1). + ABA-free. + No need for PDR. That is, one can use this algorithm out-of-the-box. No need
Google Chromeが採用した、擬似乱数生成アルゴリズム「xorshift」の数理
2015年12月17日、Google Chrome の JavaScript エンジン（処理系）である V8 の公式ブログにて、 JavaScript の標準的な乱数生成APIである Math.random() の背後で使われているアルゴリズムの変更がアナウンスされました。 Math.random() 関数は JavaScript を利用する際には比較的よく使われる関数ですので、親しみのある方も多いのではないかと思います。 新たなバグの発見や、従来より優秀なアルゴリズムの発見によってアルゴリズムが変更されること自体はそれほど珍しくはないものの、 技術的には枯れていると思われる Math.random() のような基本的な処理の背後のアルゴリズムが変更されたことに驚きを感じる方も少なくないかと思いますが、 それ以上に注目すべきはその変更後のアルゴリズムです。 実際に採用されたアルゴリズムの原
確率的カウントアルゴリズム Morris Counting の話 - Debug me
ちゃお。舞い降り......† ハイパフォーマンスPython 作者: Micha Gorelick,Ian Ozsvald,相川愛三出版社/メーカー: オライリージャパン発売日: 2015/11/20メディア: 大型本この商品を含むブログ (3件) を見る 11/20にオライリーのHigh Performance Pythonの日本語版が出るようです。 著者のMicha Gorelickさんの紹介文がエキセントリックなことで一部で話題沸騰中な本です。(未来から来たマッドサイエンティストらしい...†) 私は先に出た英語版を読んでMorris Countingという推定カウントアルゴリズムが面白いと思ったんですけど、検索してみたら日本語だとあまりヒットしなかったので、今回はそのお話をしたいと思います。トニーモリス (有名人) の話じゃないよ〜。 さてMorris Counting [Mor
ゴロム符号 - Wikipedia
ゴロム符号（ゴロムふごう、Golomb coding)とは、南カリフォルニア大学のソロモン・ゴロムによって開発された、幾何分布に従って出現する整数を最適に符号化することのできる整数の符号化手法である。 ゴロム符号と類似の手法にライス符号があるが、ゴロム符号の特別な場合がライス符号になるため、ライス符号のことをゴロム・ライス符号(Golomb-Rice coding)と呼称することが多い。特にライス符号は符号化・復号の計算量が少ないことが特徴。圧縮率は幾何分布の時はハフマン符号と同一で、それ以外ではそれよりも悪い。 符号化のパラメータとして、1 以上の整数値 m を用いる。 m > 1 のとき、符号化対象とする整数値 x(≧0) に対して、x を m で割った商を q 余りを r とする。 商 q をunary符号を用いて符号化する。 余り r は に従って、次のように符号化する。 が整数値
手続き型のダンジョン生成アルゴリズム | プログラミング | POSTD
この投稿では、以前に TinyKeepDev が こちら で述べたランダムなダンジョンを生成する技法について説明しようと思います。元の投稿に比べて、もう少し具体的に話を進めるつもりです。まずは、以下に示したアルゴリズムの一般的な動作をご覧ください。 部屋の生成 はじめに、幅と高さを持つ部屋を円の中にランダムに配置しましょう。TKdevのアルゴリズムは、各部屋のサイズを生成するのに正規分布を用いています。これは一般的にとてもいいアイデアです。なぜかと言うと、これによってより多くのパラメータを扱うことができるようになるからです。幅/高さの平均と標準偏差間の異なる比率を選ぶと、通常は見た目の違うダンジョンとなります。 ここで実行すべき関数は getRandomPointInCircle です。 function getRandomPointInCircle(radius) local t = 2
Riak 2.0のPlumtreeを読む — そこはかとなく書くよん。 ドキュメント
Riak 2.0のPlumtreeを読む¶ 昨年のRiakアドベントカレンダーでしのはらさんが、 Riak 2.0 : クラスタ全体のデータ共有を効率 という記事を書かれています。 これによると、Riak 2.0ではgossip protocolに加えて Plumtreeという論文 をもとに実装されるツリー状の経路を通って通信するプロトコルが追加される とのことです。 紹介されている スライド を読んでいて興味が湧いてきたのでriak_coreを読んで みることにします。 ちなみにlogを見ると、2013年8月1日にこれらの変更が最初に入ったようです。 tl; dr;¶ Riak 2.0からgossipプロトコルが効率良くなるよ 10台以上から有効化されるよ 01/23追記: 間違いでした！常にplumtreeが使われていて、gossipを使うのは最初のtreeを作るところだけでした。 用
O(1)というのはご機嫌に速いということ？ | 配電盤
「実際に起こりうる状況ではご機嫌に速い」という意味で「O(1)」と書くことがあるわけですが、誤解が生じるのでやめたほうがいいと思います。 たとえばn桁の足し算は、2つの整数および結果が適当なレジスタに収まるうちは、1クロック（程度）でできるのでご機嫌に速いわけですが、O(1)というわけではもちろんなく、O(n)だと考えるのがふつうでしょう。 もう少し厳密に言うと、精度に限りがあるのであれば、指数関数もO(1)でよい、ということです（ベキ乗はO(1)でOK?） もう少し厳密に言えば、O記法は極限の概念の上に成り立っているものなので、精度に限りがあるときには使いません。精度に限りがあるのなら、結果の入ったテーブルを使うことで、どんな関数でもご機嫌に速く計算できます。もっとも、テーブルを作るのに時間がかかるわけですが、 こうして一度出した結果を覚えておいて、あればそれを使うという方法はメモ化(m
僕が（一部を）考えた公平なガチャシステム - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 新しい手法を開発しました。 僕が（ほとんどを考えた）公平なガチャシステム はじめに ソーシャルゲームのガチャは、あらかじめ運営からSSRなどのレアリティに基づいた出現確率が公表されているが、それはあくまで運営が公表した値でしかなく、本当にその通りなのか疑う余地があった。そこでこの記事では前回の記事で紹介したハッシュの衝突に基いて、ユーザーにとっても運営にとってもガチャによるカードの出現確率が明らかな方法を提案する。何か質問や意見などがあれば、気軽にコメントして欲しい。 プロトコル この計算量を利用した方法はどこかのCTFで出題されたと友
Algorithmist
Algorithmist is dedicated to anything algorithms - from the practical realm, to the theoretical realm. There are also links and explanation to problemsets. Algorithmic Topics Sorting Exhaustive Search Graph Theory Dynamic Programming Greedy Computational Geometry Number Theory Data Structures View the Table of Contents. Want a problem/algorithm/section written up? Leave a note on the Algorithmist
本当に実用的なたったひとつのソートアルゴリズム - CARTA TECH BLOG
コンテンツメディア事業本部の新卒エンジニア坂本がお送りいたします。 突然ですが、皆さんの好きなソートアルゴリズムはなんですか？ 私は基数ソートのスマートでストイックな雰囲気に惹かれます。 とはいえ、普段の開発では「どのソートアルゴリズムを使うか」を意識することは少ないのではないでしょうか。 むしろ現実世界で「トランプが全部揃ってるか」を手作業で確認するときとかのほうが、実はソートアルゴリズムが必要なのかもしれません。 ということで（？）、そのような現実的な場面で、本当に実用的なソートアルゴリズムを決める戦いが始まりました。 選手紹介 今回試したソートアルゴリズムは、独断と偏見で選んだ以下の5種類。 1 挿入ソート シンプル・イズ・ベスト！正直言ってベンチマークの噛ませ犬！ 2 クイックソート 「クイック」の名前はダテじゃない！王者の貫禄を見せてやれ！ 3 マージソート 安定感のある隠れた実
Cache optimizing a priority queue
I must begin with saying that if you found this because you have a performance problem, you should almost certainly look elsewhere. It is highly unlikely that your performance problem is caused by your priority queue. If, however, you are curious, or you have done careful profiling and found out that the cache characteristics of your priority queue are causing your performance problem, and you can
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
scads/design/heaps.md at master · chrisokasaki/scads
計算量と僕とWeb開発 / computational complexity and I and Web
A multi-order radix tree [LWN.net]