「Goの父」ロブ・パイクの「プログラミング5カ条」、ネット上で話題に
「UNIXはただ死んだだけでなく、本当にひどい臭いを放ち始めている」「キャッシュはアーキテクチャではない。単なる最適化だ」などの語録を生んだ「Goの父」とも呼ばれるロブ・パイク氏の「プログラミング5カ条」について、ネット上で話題となっています users.ece.utexas.edu/~adnan/pike.html http://users.ece.utexas.edu/~adnan/pike.html Rob Pike's Rules of Programming (1989) | Hacker News https://news.ycombinator.com/item?id=24135189 パイク氏の「プログラミング5カ条」は以下。 ルール1：プログラムのどこで処理時間がかかるかはわからない。ボトルネックは意外な場所で発生するので、ボトルネックがどこにあるかを証明するまでは、臆測
幅広く利用される動画圧縮コーデック「H.264/MPEG-4 AVC」はどうやって巨大なサイズのムービーを劇的に圧縮するのか？
動画圧縮標準規格MPEG-4の1つでもあるH.264/MPEG-4 AVC/MPEG-4 AVCは「低ビットレートでも高画質」を目指した動画用の圧縮コーデックです。2003年に登場して以来、H.264/MPEG-4 AVCはインターネット上で公開されるムービーやビデオ電話、防犯カメラ、ドローンなど、ありとあらゆる場面で利用されています。そんなH.264/MPEG-4 AVCがどのようにして動画を圧縮しているのか、その技術の正体についてエンジニアのSid Balaさんがブログで説明しています。 H.264 is magic: a technical walkthrough of a remarkable technology. https://sidbala.com/h-264-is-magic/ 圧縮されていない生の動画は、パラパラ漫画のように1秒間に何十枚もの静止画を連続でつなぎ合わせた
オーダー記法（ランダウの記号）の定義と大雑把な意味 | 高校数学の美しい物語
無限大や 000 付近でのふるまいを，以下の2つの考え方に従って大雑把に評価します。 影響力が一番強い項以外無視する 定数倍の差は無視する（係数は書かない） 例えば，n3+nn^3+nn3+n はルール1により n→∞n\to\inftyn→∞ では n3n^3n3 と同じくらい，2nlogn2n\log n2nlogn はルール2により n→∞n\to\inftyn→∞ では nlognn\log nnlogn と同じくらい，と考えます。 以下では，無限大でのふるまいについて詳しく解説します（000 付近でのふるまいは最後に少しだけ）。 主にアルゴリズムの計算量評価に用いられる記号です。 三種類の記号について，表記・大雑把な意味（重要）・きちんとした定義・具体例を解説します。 ビッグオー（重要） 表記： f(n)=O(g(n))f(n)=O(g(n))f(n)=O(g(n)) 意味：
ティムソートとは [単語記事] - ニコニコ大百科
ティムソート単語 ティムソート 1.7千文字の記事 2 0pt ほめる 掲示板へ 記事編集 実利的ものさし原理性能評価関連項目掲示板ティムソートはソートアルゴリズムの一種。ティムさん（Tim Peters）が作ったからティムソート。 「ソートは研究室で動いてるんじゃない、現場で動いてるんだ」がモットーの実利派設計。オーダー的にも平均O(n log n)というデキるソートの条件を満たしながら、最悪O(n log n)と最良O(n)がくっついてしかも安定ソートというオットコマエな子。 実装がお目見えしたのは2002年のPython上という、これぞモダンアルゴリズムと言った感のあるソートである。まあ中身は大体マージソートだが。 実利的ものさし 原理の前に、そもそもソートの性能はどうやって測るのかという話をしよう。 普通ソートアルゴリズムの計算回数はデータの内容によって変動が発生する。例えば高速で
![ティムソートとは [単語記事] - ニコニコ大百科](https://cdn-ak-scissors.b.st-hatena.com/image/square/5bd1fac8d544d19340796767c18bdf23d7d3493d/height=288;version=1;width=512/https%3A%2F%2Fdic.nicovideo.jp%2Fimg%2Fog_b.jpg)
IDEA - nonverbal algorithm assembly instructions
IDEA is a series of nonverbal algorithm assembly instructions, developed by Sándor P. Fekete and blinry. The instructions explain how various popular algorithms work, entirely without text. This also allows the instructions to be understood interculturally. All instructions are available under Creative Commons licenses, so everyone is free to share and adapt them in noncommercial settings. We hope
【Unity】ソートアルゴリズム12種を可視化してみた - Qiita
はじめに ソートアルゴリズムの学習として、12種のソートアルゴリズムを実装して可視化してみました。 Unityにはあまり関係がなさそうな話題ですが、Unity上で作ったのでUnityタグをつけます。 バブルソート バブルソートのアルゴリズムは以下のような感じです。 配列の要素を最初から最後まで見ていき、順序が逆の要素があれば入れ替える 全ての要素の順序が正しくなるまで 1.を繰り返す. void BubbleSort(int[] a) { bool isEnd = false; int finAdjust = 1; // 最終添え字の調整値 while (!isEnd) { bool loopSwap = false; for (int i = 0; i < a.Length - finAdjust; i++) { if (a[i] < a[i + 1]) { Swap(ref a[i],
どうぶつしょうぎ名人 - まめめも
どうぶつしょうぎ AI を作りました。絶対に勝てません。無力感を味わってください。 ref: http://mame.github.io/dobutsu-shogi-master どうぶつしょうぎとは 3 マス x 4 マスの単純化された将棋です。ライオン（王相当）、ぞう（1 マスしか進めない角行）、キリン（1 マスしか進めない飛車）、ひよこ（歩相当、にわとりに成ったら金相当）の 4 種類の駒を動かして、相手のライオンを取るか、トライ（ライオンを一番奥の行まで運ぶ、ただし直後に取られる場合はだめ）に成功すれば勝ちです。詳しくは Wikipedia の記事を見てください。 どうぶつしょうぎは後手必勝であることが知られています（研究報告）。つまり、後手が正しくプレイする限り、先手は絶対に勝てません。どうぶつしょうぎ名人は常に正しくプレイするので、先手のあなたは絶対に勝てません。 なんで作ったの
ZDD Graphillionを使う - ryamadaのコンピュータ・数学メモ
超高速グラフ列挙アルゴリズム?〈フカシギの数え方〉が拓く，組合せ問題への新アプローチ? 作者: ERATO 湊離散構造処理系プロジェクト,湊真一出版社/メーカー: 森北出版発売日: 2015/04/08メディア: 単行本（ソフトカバー）この商品を含むブログ (4件) を見る が出版され、そこにpythonのgithub(こちらが紹介されているので使ってみる。以前も使ってみようと思ったものの、うまく回せなかったけれど、pythonも少しわかってきたしやり直し 以下は数え上げとGraphillionの動画 教えられるがまま(こちら)に沿ってインストール "Mac OS X で Graphillion を使うには、Apple が配布している Xcode の Clang をお使い下さい。"という件についてはYosemiteでは特に何もせずにデフォルトでやったけれど、ひとまず回っている まず、コンソ
Home
Graphillion - 無数のグラフを効率的に扱うための高速・軽量ライブラリ 最新のドキュメントは英語版を参照ください． ニュース 特徴 概要 インストール チュートリアル グラフセットの作成 グラフセットの操作 並列計算 NetworkXとの連携 ライブラリ・リファレンス サンプルコード 今後の予定 参考資料 ニュース Graphillion 1.0 がとうとうリリースされました． Python 3 をサポートしました (Python 2 でも使えます)． OpenMP を用いた 並列計算 が可能になりました． より効率的な辺の順序づけが実装されました． 高度な集合演算 (join, meet, quotient など) が追加されました． 2015年4月に，Graphillion の本が出版されます． 2015年1-2月に，奈良先端科学技術大学院大学の川原純先生による講義で Gra
BDD, ZDD, フロンティア法, Graphillion - iwiwi 備忘録
詳しい資料へのポインタを示しつつ，自分が読んで理解した範囲の簡潔なまとめを書きます． BDD 入門 湊先生の授業が詳しく分かりやすい． http://www-alg.ist.hokudai.ac.jp/~minato/alg2013.html 概念自体 図を一個見れば一発で理解できる DAG で，各中間ノードは変数で，その変数の値に応じて次に進む子を選ぶ．終着点が答え． 構築法 順序付き既約 BDD (ROBDD) を普通作るらしい．重要な性質を持つらしい． 順序付き ＝ 変数が出現してくる順番が全順序 以下の 2 つのルールを適用し続けていれば既約になる（適用順関係なし） 冗長な接点を全て削除 等価な接点を全て共有 実際には，BDD の間の二項論理演算を繰り返して構築する BDD 同士の演算 (Family Algebra) and, or, xor, not, ... みたいな色々な
おねえさんを組み合わせ爆発から救う：ZDDがおねえさんを救う - きしだのHatena
おねえさんを組み合わせ爆発から救うために、経路をBDDとして表しました。 http://d.hatena.ne.jp/nowokay/20121017#1350435805 ところで、「F」に至る経路で、ある辺を通るとした場合に即「F」となっているものが半分あります。 その節点を使うとしたときに、結果が偽になるのであれば、それは節点ごと不要だと言えます。そこで、そのような節点は省略してしまいます。 このような図を、ゼロ抑制BDD(Zero suppressed BDD)、略してZDDと呼びます。 「F」をすべて省略することもできます。ただし、BDDとは違って、どちらでも同じ結果になる場合も、それぞれの接続を表示する必要があります。 そうすると、2x2マスの経路でも、次のように表すことができます。かなり節点の数が減っていることがわかります。 「T」に至るパスの数が、経路の数です。 さまざまな
確率的プログラミング | POSTD
この数年で、プログラミング言語（PL）や機械学習のコミュニティは 確率的プログラミング（PP） を用いて、それぞれに共通する研究の関心事を明らかにしてきました。その概念は、抽象化のような強力なPLのコンセプトを”エクスポート”し、現状では複雑で困難な作業である統計的モデリングに再利用することができるかもしれない、というところにあります。 （講義ノートの 最新版 を閲覧したい方は、リンクをクリックしてください。ソースは GitHub に投稿してあります。誤りを発見した場合は、Pull Requestを送信してください。） 1. 何、そしてなぜ 1.1. 確率的プログラミングは○○○ではない 直観に反して、確率的プログラミングとは確率的に振る舞うソフトウェアを書くことでは ありません。 例えば、暗号のキー・ジェネレータやOSカーネルでの ASLR の実装、または回路設計のための 焼きなまし法
GitHub - dropbox/zxcvbn: Low-Budget Password Strength Estimation
zxcvbn is a password strength estimator inspired by password crackers. Through pattern matching and conservative estimation, it recognizes and weighs 30k common passwords, common names and surnames according to US census data, popular English words from Wikipedia and US television and movies, and other common patterns like dates, repeats (aaa), sequences (abcd), keyboard patterns (qwertyuiop), and
文字列アルゴリズムの学びかた - Hatena Developer Blog
こんにちは！はてなアプリケーションエンジニアの id:takuya-a です。 みなさんは、このような疑問をもったことはありませんか？ grep はどのように文字列を検索しているのか？ MeCab はどうやって辞書を高速にルックアップしているのか？ パーサやコンパイラを作りたいけど、何から始めればいいのか？ 本稿では、「文字列アルゴリズムとはどんなものなのか？」「なぜ重要なのか？」「何を知っておくべきか？」「どうやって勉強すればいいのか？」といった疑問にお答えしていこうと思います。 文字列アルゴリズムの意外な応用や、モチベーションを保ちやすい勉強のしかた、文字列アルゴリズムを勉強するために行った社内での取り組み、実装するときのコツといったトピックについても触れています。 このエントリは、はてなエンジニアアドベントカレンダー2016の22日目の記事です。昨日は id:syou6162 さんに
Googleの旅行アプリで使われている280年前のアルゴリズムとは？
By Celeste RC Googleが2016年9月20日にリリースした「Google Trips」は旅行に関する情報をまとめて管理できるアプリで、目的地までの移動方法や行き方、移動時間、観光地の場所や付近にあるレストランなど、さまざまな情報を元にして旅行の計画表を自動で作ることができます。Googleによれば、このGoogle Tripsに使用しているアルゴリズムは280年前のものを元にしているとのことで、その詳細をGoogleが公式ブログで明かしています。 Research Blog: The 280-Year-Old Algorithm Inside Google Trips https://research.googleblog.com/2016/09/the-280-year-old-algorithm-inside.html Google Trips - Google Pl
ナップサック問題でマラソンマッチ入門 - notブログ
マラソンマッチって？ 競技プログラミングのうち、「より良い解を求める」ことを競うコンテストをマラソン形式と呼びます。 例えば厳密解を求めることができない問題について、近似解のスコアを競ったりします。 マラソンでよく使われるアルゴリズム マラソンで頻出なのは「ビームサーチ」と「焼きなまし法」です。 この記事ではナップサック問題を例にしてこの２つのアルゴリズムを解説します。 もちろん、この２つのアルゴリズムはどちらも近似アルゴリズムなので最適解は求められません。 ビームサーチ まずは順番にナップサックに入るだけ入れるコードを書いてみます。 #include <iostream> using namespace std; int main() { // 個数 const int N = 100000; // ナップサックの大きさ const int W = 100000; // 重さ・価値 in
【オンライン機械学習】 Go で PA, CW, AROW, SCW を書いてみた |
Perceptron (Rosenblatt, 1958) を1年半前に書いてから, だいぶ時間が経ってしまいましたが, 今回はその続きで Go で PA, PA-I, PA-II, CW, AROW, SCW-I, SCW-II を書いてみたのでメモリます。 PA, CW, AROW, SCWの総まとめ的な論文 Exact Soft Confidence-Weighted Learning にアルゴリズムがまとまっています。 PA (Passive-Aggressive) PA (Crammer et al., 2006) [1] は, 損失関数にSVMでも使われているヒンジ損失を用いる。 最適化問題は, ヒンジ損失が 0 となる制約の元でこれまでに得られている重みに近い重みを選択する。ただし, ヒンジ損失が 0 となる制約は強く, 急に重みが変動してしまうので, PA-Iでは罰則項を線
今話題のブロックチェーンとは何なんだ？ 部外者の技術者として考察してみる。
一行でまとめ: 暗号通貨は面白いけど、ブロックチェーンはそれ以外には使い道がないだろうと僕は思ってるよ。暗号通貨はダメでブロックチェーンは有用という奴らは何も分かってない。 最近、IT業界を取り巻くメディア（日経BPとTechCrunch等）ではブロックチェーンなる技術が話題です。 ブロックチェーンとは、bitcoinを構成する技術であり、それ自体が金融システムを変革するものなどと言われています。しかしメディアではブロックチェーンの本質について説明しない記事が目立ちます。 現状の大きな問題として、ブロックチェーンやbitcoinについて解説する記事の多くは、bitcoin関連の仕事をしている起業家や研究者などの利害関係者による記事が多いというバイアスがあります。また技術者ではないジャーナリストが書いた記事も、技術的な本質に突っ込めていないものが目立ちます。 本記事では、bitcoinに関し
RubyとPythonにおけるガベージコレクションの視覚化 | POSTD
本稿は、ブダペストで開かれたイベント「 RuPy 」で、Pat Shaughnessyが披露したプレゼンの内容をまとめたものです。 プレゼンの映像はここ から視聴できます。 本稿は当初、 同氏の個人ブログ に投稿されましたが、同氏の了承を得て、Codeshipに再掲載します。 このイベントは「RubyとPython」に関するカンファレンスなので、RubyとPythonでは、ガベージコレクション（以下「GC」）の動作がどう違うのかを比較すると面白いだろうと私は思いました。 ただしその本題に入る前に、そもそもなぜ、GCを取り上げるのかについてお話しします。正直言って、すごく魅力的な、わくわくするテーマではないですよね？ 皆さんの中でGCと聞いて、心がときめいた方はいらっしゃいますか？ ［実はこのカンファレンス出席者の中で、ここで手を挙げた人は数名いました！］ Rubyコミュニティで最近、Rub
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Graphillionを用いたネットワーク障害推定
