私が書いた最速のハッシュテーブル – 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
2017年3月にGoogleから発表された新しいJPEGエンコーダ「Guetzli」と、同エンコーダが用いる画品質評価アルゴリズム「Butteraugli」について思うところとか。 Announcing Guetzli: A New Open Source JPEG Encoder GitHub google/guetzli GitHub google/butteraugli 多くのニュースサイトで『Google、JPEGを35％小さくできるエンコーダー「Guetzli」をオープンソースで公開』のようにセンセーショナルに紹介され、またGoogle社の手によるネームバリューもあったのか、世間の強い興味を引いたように思います。OSS方式にてソースコード公開されており、実際にエンコーダを動してみた方による良い／悪い評価結果が出てきています。 この記事では、同エンコーダ作者 Jyrki Alaku
できる動的計画法：ロッド切り出し問題 | POSTD
私が常に頭を悩まされていたのが最適化問題です。これは、コードを理解するだけでも非常に困難な問題です。そこで、これまでに私が学んだことを基に、典型的な動的計画法の問題を取り扱ういくつかの記事を投稿することにしました。今回取り上げるロッド切り出し問題は古典的な最適化問題であり、動的計画法の一例と言えます。 ロッド切り出し問題とは？ ロッド切り出し問題は、現実世界で私たちが直面するたいていの問題に非常によく似ています。ある長さの棒があり、この棒を最大利益が得られる長さにして切り売りをしたいという状況があると仮定します。ここで問題となるのは、切り出した長さによって棒の値段が異なる点です。例えば細かく切り出した方が大まかに切り出した場合よりも、より多くの利益が得られる可能性があるため、ちょっと違った考え方をする必要があります。 先に進む前に、まずはこの問題をより正確に定義しておきましょう。 長さ n
高速なRandomized Queueのアルゴリズムを実装する - $shibayu36->blog;
CourseraのAlgorithms, Part Iというコースで、高速なRandomized Queueを実装するという話題があったので、試しに作ってみた。 高速なRandomized Queueとは Randomized Queueとは、Queueからdequeueするときに、中に入っている要素の中からランダムに一要素取り出すようなQueueである。 また「高速な」とは、enqueue、dequeue、isEmpty、sizeなどの操作の実行時間が、"constant amortized time"であること、つまり何回も操作を繰り返していくと、平均的には定数時間でそれぞれの操作が終わるということである。 この二つを満たすものを高速なRandomized Queueと呼ぶ。 実装 高速なRandomized Queueを実装すると次のようになった。 import java.util.
円周率の16進数表現100億桁目を求めてみた！ ― 円周率の世界記録をどのように検証するか ― - プログラムモグモグ
あなたは円周率を何桁言えますか。3.14159…という、あの数字です。 円周率の小数部分は無限に続き、循環することもありません。 古来より、数学者は円周率の値を様々な幾何学的な近似や公式を用いて計算してきました。 その桁数は計算機の発明により飛躍的に伸び、収束の速い公式の発見や効率の良いアルゴリズムの発明などによって加速してきました *1。 5年前、私がまだ学生だった頃、円周率1億桁の計算に挑んだことがありました。 私にとって高精度計算の初めての挑戦で、様々な試行錯誤で苦労したのをよく覚えています。 itchyny.hatenablog.com 2017年現在、円周率計算の世界記録は22兆桁です。 円周率計算の歴史をご覧いただくとよく分かると思いますが、近年の円周率計算の世界記録からは次のような特徴が読み取れます。 2002年に1兆を超え、最新の記録 (2016年) は22兆桁 (10進数
一から学ぶベジェ曲線 | POSTD
(編注：SVGアニメーションを元記事にならい追加しました。リクエストありがとうございました。) 皆さんは線分のことをどう表現しますか？ 線分は、端点によって考えられるかもしれません。その端点を P0 、 P1 と呼ぶことにしましょう。 線分を厳密に定義するならば、「 P0 と P1 を結ぶ直線において、 P0 と P1 の間にある全ての点の集合」と言えるかもしれません。これは以下のように表せるでしょう。 便利なことに、上記の定義から、その線分上のどこにある点の座標でも簡単に求めることができます。例えば、中点は L(0.5) にあります。 実は、2点間のどんな値でも、任意の精度で 線形補間する ことが可能です。そのため、時間関数 L(t) の t で線をたどるといった、より複雑なことができるのです。 ここまで来ると、「それが曲線と何の関係があるのか？」と不思議に思うかもしれません。2つの点だ
中置記法の数式文字列から計算結果を求める操車場アルゴリズム - $shibayu36->blog;
最近 Algorithms, Part I | Coursera の社内勉強会を開いている。そこで「Stacks and Queues」という章をみんなで学習し、議論したところ、中置記法の数式文字列から計算結果を求める操車場アルゴリズム(Shunting-yard algorithm)というものがあるということを知った。 操車場アルゴリズムというのは、中置記法の数式文字列から計算結果を求めるというようなことができるアルゴリズム。オペレータスタックと値スタックの二つがあるだけでトークンを一つずつ読みつつその都度計算するだけで計算結果を求めることができる。パースして構文木を作るというフローを取ることなく計算ができるというのが面白い。このアルゴリズムの説明は Wikipediaの操車場アルゴリズム - Wikipedia の説明が非常に分かりやすい。 このアルゴリズムを使うことで、例えば以下のよ
Big Sky :: レーベンシュタイン距離を使ったあいまい grep コマンド「lsdgrep」作ってみた
元ネタはずいぶんと昔の記事なのだけど。 編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー ■ 編集距離 (Levenshtein Distance) 昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベン... http://d.hatena.ne.jp/naoya/20090329/1238307757 思い付きはまったく関係ない所から。 mp3 が数千ファイル入ってるフォルダで何かの手違いで同じ曲が入ってしまう事が結構あって重複取り去る作業してた。ID3が違ってるとMD5も違うのでレーベンシュタインの文字列距離を使ってファイル名が似てるの調べたら422ファイル消せる事が分かった。 — Vim芸人 (@mattn_jp) February 25, 2017 これを
遺伝的アルゴリズムで二足歩行の学習 /物理エンジン【むにむに】
物理エンジンで人型のロボットを作った。 遺伝的アルゴリズムで二足歩行の学習をさせた。 遺伝子：各関節の角度。5つの動作分(0(初動),1,2,3,4)。 動作：0⇒1⇒2⇒3⇒4⇒1⇒･･･。0は最初だけ。1から4を繰り返す。2動作ずらして左右対称。 評価：倒れるまでに前進した距離。 選択：評価の高いものから5体。 交叉：評価の高い5体からランダムに2体選んで遺伝子を混ぜる。 突然変異：遺伝子1個～2個に対してランダムな値(角度)を足す。 突然変異は、ほとんどの場合、改悪である(奇形児)。 が、まれに親の能力を上回る。 ニコニコ動画版 https://www.nicovideo.jp/watch/sm16597051 #むにむに #munimuni #物理エンジン #遺伝的アルゴリズム
すばらしいビット | POSTD
unsigned int v; //only works if v is 32 bit v--; v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; v++;
エンコード方式 base-122 | POSTD
base-64よりもスペース効率の良い方法。 GitHub レポジトリ 1 概要 バイナリをテキストに変換するエンコード方式としての base-64 は、そのデータ量を33％増大させます。この記事では、UTF-8のテキスト変換方式であり、元のデータから14％増大するbase-122を紹介します。base22はWebを念頭において作られました。 実装 には、Javascriptのデコーダを使い、base-122でエンコードしたリソースをWebページに読み込ませる過程が含まれます。 免責事項 3で示すように、base-122は 大半のWebページが該当します gzip圧縮ページでの使用は推奨しません。ですが、base-122は一般的な文字エンコード方式として役に立つ可能性があります。 1.1 はじめに 画像、フォント、オーディオなどの外部のバイナリリソースは、base-64でエンコードする デ
どうぶつしょうぎ名人 - まめめも
どうぶつしょうぎ AI を作りました。絶対に勝てません。無力感を味わってください。 ref: http://mame.github.io/dobutsu-shogi-master どうぶつしょうぎとは 3 マス x 4 マスの単純化された将棋です。ライオン（王相当）、ぞう（1 マスしか進めない角行）、キリン（1 マスしか進めない飛車）、ひよこ（歩相当、にわとりに成ったら金相当）の 4 種類の駒を動かして、相手のライオンを取るか、トライ（ライオンを一番奥の行まで運ぶ、ただし直後に取られる場合はだめ）に成功すれば勝ちです。詳しくは Wikipedia の記事を見てください。 どうぶつしょうぎは後手必勝であることが知られています（研究報告）。つまり、後手が正しくプレイする限り、先手は絶対に勝てません。どうぶつしょうぎ名人は常に正しくプレイするので、先手のあなたは絶対に勝てません。 なんで作ったの
Union Findアルゴリズムの様々な実装とパフォーマンス計測 - $shibayu36->blog;
CourseraにAlgorithms Part1という授業があり、これが非常に評判が良いので、会社で勉強会をしている。Week1にUnion Findというアルゴリズムが出てきて、その実装パターンがいくつかあった。それぞれ計算量が違うらしいのだけど、速度がどのように変化するか試したかったので、実装してパフォーマンス計測をしてみた。それぞれの実装の詳しい説明が知りたかったら、https://www.coursera.org/learn/algorithms-part1 を見ると良い。 Union Findとは何か 二つのノードを繋いでいき(Union)、あるノードとあるノードがつながっているか(Find or Connected)を判定するアルゴリズム。 例えば、union(1,6)、union(5,6)、union(2,7)、union(3,8)、union(4,9)、union(8,9
バージョンの充足可能性問題 | POSTD
(注：2017/02/06、いただいたフィードバックを元に翻訳を修正いたしました。修正内容については、 こちら を参照ください。) Dependency HellはNP完全ですが、この状況から脱却できるかもしれません。 パッケージにおけるバージョン選択の問題とは、完全である（全ての依存関係を満たしている）かつ互換性のある（互換性のない2つのパッケージが選択されていない）トップレベルパッケージPをビルドするために使われる依存関係の集合を見つけることです。ただし、菱形依存問題があるので、このようなセットは存在しない可能性があります。菱形依存問題とは、AはBとCが必要、BはDのバージョン2ではなくバージョン1が必要、CはDのバージョン1ではなくバージョン2が必要といったような問題のことです。この場合、Dの両方のバージョンを選択することはできないため、Aをビルドすることができないわけです。 パッケ
Suffix Arrayを使った文字列マッチング - $shibayu36->blog;
あるPatternがあるText中のどこに含まれるかという文字列マッチングの実装を最近してみている。前回、Suffix Trieでの文字列マッチングを行った。 blog.shibayu36.org Suffix Trieを利用すると、Suffix Trieを最初に構築したあと、実際にパターンを検索するのはO(|Patternの長さ|)の時間計算量で文字列マッチング出来た。しかし、Suffix Trieを保持するために非常に多くのメモリを使用するため、あまり長いTextに適用できないという問題があった。 同じように文字列マッチングをする方法としてSuffix Arrayという構造を使う方法がある。Suffix Arrayの構造のメモリ使用量は|Text|の長さ * (IntかLongのバイト数)程度となり、メモリ使用量の問題を軽減することができる。そこで今回はSuffix Array構造を利
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になる) 最近接偶数への丸めは中間値の場合に、
「銀行家の丸め」とは何か | 会計SEのメモ
「銀行家の丸め」というコトバがあります。このコトバ、知らなかったでしょ？知ってる人って少ないと思うんですよ。このブログは会計初学者のSEさん向けに書いてるわけですけど、この「銀行家の丸め」はかなり細かい話なんで、初学者の人はまず知らないはず。でも知ってしまえばものすごく簡単なハナシなので、これを機会に覚えちゃって下さい。 なお、この「銀行家の丸め」は、「最近接偶数への丸め」「偶数丸め」「JIS丸め」「ISO丸め」「五捨五入」「偶捨奇入」「bankers’ rounding（バンカーズラウンディング）」とも呼ばれます。何しろマイナーな処理なので言い方も定まってないんだよね、たぶん。 四捨五入の一種 この「銀行家の丸め」ってのは、四捨五入の一種です。「ちょっと変わった四捨五入」って言えばいいかな。 定義 定義は、「端数が0.5より小さいなら切り捨て、端数が0.5より大きいならば切り上げる。端数
"リトライ"の実装: Truncated Binary Exponential Backoff - Qiita
exponential backoff はシステムが許容可能な速度を見つけるために各処理の実行速度を遅延させるためのアルゴリズムです。簡単に言えば最適なリトライ ─ 例えば通信が切断された時に自動で再接続するまでの遅延時間を計算する方法のこと。exponential backoff は連続失敗回数を $n$ とした時に $0$ から $x^{n-1}$ までの間の乱数を使用する。 よく使われているアルゴリズムは $2$ のべき乗で計算する binary exponential backoff というもの。 $t = a \times 2^{n-1}$ $t$, $a$ を秒とした場合、1回目のリトライは $0～a$[sec]、2回目のリトライは $0～2a$[sec]、3回目のリトライは $0～4a$[sec]、... の間のランダムに選んだ時間をおく。 ただこの式だけでは $t$ がすぐ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub Enterprise、SHA-1衝突を実行不能にするパッチを適用へ SHA-1ハッシュが同一のファイルの格納を検出してブロック
