2-satisfiability - Wikipedia
In computer science, 2-satisfiability, 2-SAT or just 2SAT is a computational problem of assigning values to variables, each of which has two possible values, in order to satisfy a system of constraints on pairs of variables. It is a special case of the general Boolean satisfiability problem, which can involve constraints on more than two variables, and of constraint satisfaction problems, which ca
蟻コロニー最適化 - Wikipedia
蟻コロニー最適化の概念図 蟻コロニー最適化（ありコロニーさいてきか、Ant Colony Optimization、ACO）とは、Marco Dorigo が 1992年の博士論文で提案したアルゴリズムであり、グラフを使ってよい経路を探すことで単純化できるような計算問題の確率的解法である。これはアリがコロニー（＝群れ）から食物までの経路を見つける際の挙動からヒントを得たものである。 実世界では、アリは始めランダムにうろつき、食物を見つけるとフェロモンの跡を付けながらコロニーへ戻る。他のアリがその経路を見つけると、アリはランダムな彷徨を止めてその跡を辿り始め、食物を見つけると経路を補強しながら戻る。 しかし、時間とともにフェロモンの痕跡は蒸発しはじめ、その吸引力がなくなっていく。その経路が長いほどフェロモンは蒸発しやすい。それに対して、経路が短ければ行進にも時間がかからず、フェロモンが蒸発す
Google、TCPのスループットとレイテンシを改善する輻輳制御アルゴリズム「TCP BBR」をGoogle Cloudで利用開始
Google、TCPのスループットとレイテンシを改善する輻輳制御アルゴリズム「TCP BBR」をGoogle Cloudで利用開始 Googleは、同社が開発したTCPの輻輳制御アルゴリズム「TCP BBR」をGoogle Cloud Platformで利用可能にしたと発表しました。 インターネットにおける通信にはTCPを用いる場合とUDPを用いる場合に分かれますが、BBRはTCPにおける輻輳制御アルゴリズムを改善したもの。すでにGoogleはTCP BBRをYouTubeのネットワークで利用しており、従来のパケットロスをベースにした輻輳制御アルゴリズムであるCUBICを用いた場合と比較して、スループットが平均で4％、最大で14％以上改善したことを明らかにしています。 TCP BBRは現在の高速なネットワークに適した輻輳制御アルゴリズム TCP BBRのBBRは「Bottleneck Ba
確率的データ構造の比較：カッコウフィルタ対ブルームフィルタ | POSTD
確率的データ構造は少ないメモリでデータをコンパクトに保存し、保存されたデータに関するクエリに対し、おおよその答えを提供してくれます。クエリに対し空間効率の良い方法で答えるように設計されており、それはつまり、正確さを犠牲にするということにもなります。しかし、これらは一般的に、問われているデータ構造の仕様にもよりますが、誤差率の保証と境界を提供してくれます。メモリ使用量が少ないため、確率的データ構造はストリーミングや低出力の設定に特に有用なのです。ですから、動画の視聴回数を数えたり、過去に投稿された一意となるツイートのリストを維持したりするなど、ビッグデータの環境下では非常に有用です。例えば、 HyperLogLog++ 構造 は、2.56KBのメモリで最大790億の一意のアイテムを数えることができるのですが、誤差率はわずか1.65パーセントです。 Fast Forward Labsのチームは
マルコフモデル ～概要から原理まで～ （前編） | POSTD
本記事は、元記事を翻訳した記事の前編となります。 B/C/D節については後編をご参照ください。 “マルコフモデルとは何か” という議論は昔からありますが、もし皆さんがその答えを知りたいのであれば、正直なところ、ウィキペディアを見る（または以下のTLDRだけを読む????）ことをお勧めします。一方、マルコフモデルの概要やこのモデルが重要である理由、およびその実装方法に興味があり、サンプルを通じて理解を深めたいという方は、この記事を引き続きご覧ください(^ ^)。以下で、 具体例を挙げて説明します。 TLDR： 確率論 において、マルコフモデルは不規則に変化するシステムを モデル化 するための 確率モデル である。なお、未来の状態は現在の状態のみに左右され、過去に起きた事象には影響されないと仮定する（つまり、 マルコフ性 を仮定する）。 引用元： https://en.wikipedia.or
興味深いデータ構造：BK木 | POSTD
BK木とは、 距離空間 内のデータをインデックス化する目的に特化した、木構造を指します。距離空間は基本的に、要素の組 $ (a,b) $ 全てについて距離関数 $ d(a,b) $ を持つオブジェクトの集合です。この距離関数は正しく動作することを保証するために、一連の公理を満たしていなければなりません。これが必要になる理由は、後述の「検索」のセクションできちんと説明します。 BK木のデータ構造は、一連のキーを検索し、与えられた検索キーの値に最も近いキーを見つける問題の解決策として、 1973年にBurkhardとKellerが提案したもの です。この問題を解決する素朴な方法は、要素の組に含まれる各要素と検索キーの値を単純に比較することです。一定の時間内に比較が完了した場合、この検索の解は $ O(n) $ となります。一方、BK木を採用すると、この時実行する比較の回数を減らせる可能性が高く
私が書いた最速のハッシュテーブル – PART 2 | POSTD
素数か2のべき乗か ハッシュテーブルのアイテムをルックアップする際に高負荷なステップが3つあります。 キーをハッシングする キーをスロットにマッピングする 該当スロットのメモリをフェッチする ステップ1は、キーが整数であれば、低負荷になります。単にintをsize_tにキャストするだけです。しかし、文字列のようなタイプのキーの場合は高負荷となります。 ステップ2はよくある整数モジュロ演算です。 ステップ3はポインタの間接参照です。std::unordered_mapの場合は複数のポインタ間接参照となります。 処理の遅いハッシュ関数でなければ、直観的にステップ3が最も高負荷になると考えると思います。しかし、全てのルックアップでキャッシュミスが生じなければ、整数モジュロが最も高負荷な処理となります。現代のハードウェアにおいても整数モジュロは非常に遅いのです。 Intelマニュアル では、整数モ
MySQLのfilesortは何ソートで行われているのか - $shibayu36->blog;
最近、CourseraのArgorithms, Part1という講義を受けている。そこでソートの講義を受けて、そういえばMySQLのORDER BYでfilesortになったときってどのソートが使われているのだろうと気になってきたので調べてみた。 調べてみると非常に難解で、結局いまいち分からなかったが、今の段階の調べた内容をひとまず書いておく。MySQLのコードを読んだのも初めてで、しかもちゃんと読み解くことができなかったので、情報が間違っている可能性も非常に高い。間違ってたら指摘してもらえるとうれしいです。 調査結果 最初に調査結果を書いておく。たぶんこれは非常に単純化したもので、詳しく見るともっといろいろチューニングされてそう。 sort_buffer_size以内のメモリ量でソートが可能な場合、メモリ内でのみソートされる ソートにsort_buffer_size以上のメモリが必要な場
私が書いた最速のハッシュテーブル – PART 1 | POSTD
結局、やり出したら止まりません。私は以前、” I Wrote a Fast Hashtable（私が書いた高速なハッシュテーブル） “という記事と、それに次いで” I Wrote a Faster Hashtable（私が書いたより高速なハッシュテーブル） “という記事をブログにアップしましたが、今回ついに、最速のハッシュテーブルを書き上げました。これが意味するところは、ルックアップがどのハッシュテーブルよりも速いということです。それに加えて、挿入や削除も（最速とまではいかないまでも）非常に速く行えます。 秘訣は、探索回数の上限を設定したロビンフッドハッシュ法を使用することです。ある要素が、その理想的な位置からX数以上、離れた位置にある場合、テーブルを拡張することで、全ての要素が、その大きなテーブル内において、理想的な位置に近づくようにします。結果的に、このやり方は非常にうまくいきました。
効率的にゲームを更新する | POSTD
先日、 Things that can go wrong when downloading（ダウンロード時に上手くいかないものごと） についての記事を書きました。その記事に、ネットワークの問題から妥当でないコンテンツ、不完全なハードウェアに至るまで、ゲームを最初にインストールする際に発生することがある一連の原因をリストアップしました。 今回の記事では、ゲームの前バージョンが正常にインストールされているときに、そのゲームを新しいバージョンにアップグレードするのにどんな方法が使えるかについて考えます。 圧縮 あるユーザが利用できる帯域の量は、通常、一定です。ユーザのインターネットアクセスの論理的な最大速度は20mbps、100mbps、1gbps、または、国によってはそれよりずっと低いものです。 私の自宅にはまだ光ファイバが引かれていないので、アクセスは20mbpsという遅さですが、インターネ
Guetzli／Butteraugliに関するあれこれ - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 2017年3月にGoogleから発表された新しいJPEGエンコーダ「Guetzli」と、同エンコーダが用いる画品質評価アルゴリズム「Butteraugli」について思うところとか。 Announcing Guetzli: A New Open Source JPEG Encoder GitHub google/guetzli GitHub google/butteraugli 多くのニュースサイトで『Google、JPEGを35％小さくできるエンコーダー「Guetzli」をオープンソースで公開』のようにセンセーショナルに紹介され、またG
できる動的計画法：ロッド切り出し問題 | POSTD
私が常に頭を悩まされていたのが最適化問題です。これは、コードを理解するだけでも非常に困難な問題です。そこで、これまでに私が学んだことを基に、典型的な動的計画法の問題を取り扱ういくつかの記事を投稿することにしました。今回取り上げるロッド切り出し問題は古典的な最適化問題であり、動的計画法の一例と言えます。 ロッド切り出し問題とは？ ロッド切り出し問題は、現実世界で私たちが直面するたいていの問題に非常によく似ています。ある長さの棒があり、この棒を最大利益が得られる長さにして切り売りをしたいという状況があると仮定します。ここで問題となるのは、切り出した長さによって棒の値段が異なる点です。例えば細かく切り出した方が大まかに切り出した場合よりも、より多くの利益が得られる可能性があるため、ちょっと違った考え方をする必要があります。 先に進む前に、まずはこの問題をより正確に定義しておきましょう。 長さ n
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
What's the approach to solving this kind of logic problem?
The puzzle of Liars
CSCI 2824: Lecture
How can i generate 4 bit binary combination using recursion in C for 0,1?
GitHub - jiayihu/pretty-algorithms: 🌊 Pretty, common and useful algorithms with modern JS and beautiful tests
GitHub - kbrsh/wade: :ocean: Blazing fast 1kb search library
https://jp.techcrunch.com/2017/06/24/20170623new-algorithm-lets-you-make-anything-in-origami/
GitHub Enterprise、SHA-1衝突を実行不能にするパッチを適用へ SHA-1ハッシュが同一のファイルの格納を検出してブロック
