Google Developers: データ圧縮アルゴリズムの基礎 - ワザノバ | wazanova
「webサイトの平均サイズが2メガに近づき、Androidゲームが125メガになってきて、コンテンツと送信コストのトレードオフが深刻な問題になってきている。開発者にとって次の10年は、圧縮アルゴリズムを理解して、うまく使いこなすことが重要になる。」という紹介文に惹かれて、3回 (20分/10分/20分) のビデオシリーズを見ました。概要は下記の通りですが、図示が中心でわかりやすく説明してくれてますので、是非チェックしてみてください。（3回目の後半はちょっと素人には難解でした。。） Episode 1: Variable Length Codes モールス信号からバイナリコードに進化してきたが、共通しているのは、出現率の高い文字から順番に短い記号列 ("."もしくは"-") /数列 ("0"もしくは"1") をあてはめることで、記号列/数列全体の平均の長さを短くしようとする考え方。 この場合
DataGridを自前実装する話
名古屋ＭＳ系秋祭り http://atnd.org/events/43243 のLT資料です、当日会場で1時間そこそこで書き上げたものなので、非常に雑です。Read less
動的に価格を変えるアルゴリズム - ワザノバ | wazanova
https://www.youtube.com/watch?v=-KFe5pGMFbo 1 comment | 0 points | by WazanovaNews ■ comment by Jshiike | 約1時間前 Uberは、配下のタクシーの乗車率を最大化して、かつ顧客の不満「タクシーがつかまらない!」「呼んだタクシーがくるのが遅い!」を下げるために、タクシーがつかまりづらい時間帯は動的に価格が上がる仕組みにして、需給バランスの最適化を計ってます。 最初はしばらく手動で値上がり率を入力して、データを蓄積。それからアルゴリズム化した。 都市ごとに係数は変えている。大きな都市では、空きタクシーの検索範囲は市全体でなく時間帯で適切なエリアだけをカバーするかたちに変えた。 最初はその時間に適用される値上がり率を、へりくだったお詫び的なテキストの中で表示していたが、請求されてから気づく酔
アリの行動に学ぶ、より多くの脱出を可能にする非常出口の設計手法とは
多くの人が集まったり一定の広さを持つ部屋には、万が一の事態にも安全に脱出できる非常出口の設置が法律で定められています。効率的な避難路を確保するために非常口の周辺には障害となる物を置かないことが必要とされていますが、アリを使って特定の条件下で行われた一連の実験の結果では、非常出口の前に障害物を置いたほうが、脱出のスピードが速くなるという意外とも言える結果が明らかになりました。 Want to Get Out Alive? Follow the Ants - Issue 13: Symmetry - Nautilus http://nautil.us/issue/13/symmetry/want-to-get-out-alive-follow-the-ants これらの実験の対象となったのは、アリ科の中でも大型に分類されるキューバアリで、その生態を観察することで検証が進められました。実験を行っ
Iconfinder: 画像データの重複チェックのアルゴリズム - ワザノバ | wazanova
http://blog.iconfinder.com/detecting-duplicate-images-using-python/ 1 comment | 0 points | by WazanovaNews ■ comment by Jshiike | 約5時間前 Iconfinderは以前、500 Startup Fundのデモdayでプレゼンするのを見た記憶があります。それから資金調達もできたようで、無事生き残ってますね。 アイコン等の画像ファイルの検索 & 販売をするサイトですが、悪いユーザがIconfinderから画像をダウンロードした後に、そのまま、もしくは多少改変して、Iconfinderにアップして販売しようとする不正行為があるようです。その対策のための検知アルゴリズムについてブログで紹介しています。 一般的な画像データをハッシュ化するアルゴリズムでは、画像のごく一部
Tiny Raytracer - Gabriel Gambetta
I love raytracers. Their combination of a simple algorithm and stunning results are hard to beat. I’ve written several raytracers over the years, including the one in Computer Graphics from Scratch, but this time I decided to write the smallest possible one I could write. My current version is 912 bytes of Javascript, and I’m sure it’s still possible to shave off a few more bytes. Note that the si
ビットコインの応用で、電子書籍を譲渡可能にするアルゴリズム
サトウヒロシ🐰まずは医療費全世代３割負担。現役世代を苦しめる社会保険料を低減しよう @satobtc (1)今日は、ビットコインの経済的側面ではなく、技術的側面から可能になる未来像について、連続ツイートします。 ビットコインのP2Pネットワークは、あるデジタルデータ（コインでは残高＝お金としている）の所有権を中央の認証機関なしに移転することができるというものです。 2014-02-24 15:42:36 サトウヒロシ🐰まずは医療費全世代３割負担。現役世代を苦しめる社会保険料を低減しよう @satobtc (2)これは、計算機科学的にいうとビザンチン将軍問題というもので、だれか管理者がいなくても分散型のコンピュータはお互いに故障や正しいデータを識別できるか、といったような問題です。これに対する実用的なはじめての回答がビットコイン的な仕組みです。 2014-02-24 15:43:49
GNU grep 2.18リリース: 10倍速くなったと思ったら今度は200倍遅くなっていた | はむかず！
先日の記事 いまさらgrepが10倍高速化したのはなぜか が思わぬ閲覧数を稼いでしまい、トルコ語の知識を日本に広めるのに大きな貢献をしたような気がしますが、みなさんいかがお過ごしでしょうか。 実は先日の記事を書いた時にはすでに2.18がリリースされてたのだが、今回は2.17のときと違って日本の大手メディアが取り上げてなかったので、ついつい見落としていた。しかし実は2.18でも大きな変更が！！ リリースノート抜粋： grep -i in a multibyte, non-UTF8 locale could be up to 200 times slower than in 2.16. [bug introduced in grep-2.17] なんということでしょう。-iオプションでUTF8のときは2.17で10倍速くなっていたのだが、それ以外のマルチバイトロケールのときは200倍遅くなって
いまさらgrepが10倍高速化したのはなぜか – はむかず！
最近GNU grepコマンドの最新バージョンがリリースされ、速度が10倍になったとのアナウンスがあった。それを聞いて、なんであんな枯れた技術に10倍もの高速化の余地があったのだろうと不思議に思った人も多いだろう。 ニュース記事：grepコマンド最新版、”-i”で10倍の高速化 本家のリリースノート：grep – News: grep-2.17 released [stable] 今回のリリースでは正確には、マルチバイトロケールで、-iオプション（–ignore-case、つまり大文字小文字を区別しないオプション）をオンにした時の速度が10倍くらいになったそうだ。 なぜそんなに速くなったのか？逆を言えば今までなぜそんなに遅かったのか？ そもそも、多くの日本人にとって「大文字小文字の区別」というと英語のアルファベットか、せいぜいフランス語とかドイツ語とかのアクサン記号・ウムラウトがついたものく
計量学習を用いた画像検索エンジンとアニメ顔類似検索v3について - デー
まだgithubにはpushしていないのですが、さいきょうの組み込み型画像検索エンジンotamaに計量学習を用いて与えられたデータにあった画像間の距離関数を学習してそれを使って検索するというドライバを入れたので、先行的なデモとしてアニメ顔類似検索v3を作ってみました。 計量学習は、ベクトル間の距離の計り方を機械学習で決めるみたいな分野です。 アニメ顔類似検索v3 AnimeFace Search v3 - Otama LMCA_VLAD_HSV Driver randomボタンを押すと顔画像がランダムに出るのでどれかクリックするとそれをクエリに検索します。color weightは色の重みを調節するパラメーターで、1にすると色だけで検索します。0にすると形状やテクスチャだけで検索します。結果画像の上の数字は類似度的なもので、その横のgglは元画像をGoogle Search by Imag
mrubyやKopiLuaにはなぜ文字連結用オペコードがあるの? ① (あるいはJavaの文字連結最適化について) - ほげほげにゃ
前置き 最近色々ありましてmrubyやKopiLua(C#によるLua実装)のソースコードを読んだりしております。 ちょうどVM部分を読んでいたら、面白い部分を見つけました。 mrubyのバイトコードにOP_STRCAT(文字連結)っていうのがあるのに驚いてたけど, LuaVM読んでたらOP_CONCATとかあったし文字連結系のオペコード用意するのって普通なんです…?— どみとり (@domitry) 2013, 12月 5 これまでx86のアセンブラしか読んだことがなかったので特殊かどうかよくわからない… そこでふとLL言語でない, 例えばJavaのVMはどうなってるんだろうなーと思い調べてみました。 昨日のお話、Javaのバイトコードを見てみたらstrcatやらconcatはなかった… キャストとかオブジェクト指向な要素(newとかclass method呼び出しとか)とかは含まれてた
Skip Lists
Skip Lists は 1990年に William Pugh によって開発されたリスト構造体の一種である。 オリジナルの論文は William Pugh, "Skip Lists: A Probablistic Alternative to Balanced Trees", Communications of the ACM, June 1990 となっている。 この論文は ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf からコピーを入手可能である。 また、Unix Magazine 1999年 1月号 を入手できれば、 そこには日本語で書かれた解説があるが、 これはほとんど論文丸写しに近いので、きっと重宝するだろう。 数多くの、要素が増減しなおかつ入れ替わるようなデータ構造で、 さらにランダムアクセスが
ARC12 D - Don’t worry. Be Together - math314の日記
http://arc012.contest.atcoder.jp/tasks/arc012_4 二次元平面上の格子点(x,y) にいる人間が、原点(0,0)に移動したい。 この時、Tターン後に原点にいる移動方法の組み合わせを求めることが出来ればよい。 移動が可能な条件 Tターン後に原点へ移動が可能な条件は、x+y <= T かつ、x+yとTの偶奇が一致している事。 x+y <= Tは明らかとして、x+yとTの偶奇についての証明 無駄に丁寧なのでわかってる人は飛ばしてください まず1次元で考える。 Txターン後に原点へと移動したい x軸方向と逆方向の2通りの動き方があり、座標xからそれぞれ(a,b)だけ移動したとすると、移動後の座標は x+a-b となる。 ここで x+a-b = 0,a+b = Tx より a = (Tx-x)/2 , b = (Tx+x)/2 a,bが整数なので、Tx-x
ねじ曲げ画像を使った新方式のCAPTCHA MintEyeを23行のPythonコードで破った話
先月ご紹介してなかなか好評だった、画像をグニャリと円状に曲げて加工し、それを正しい状態に戻すことで人間かスパムプログラムかを判定するという新方式のCAPTCHA MintEyeですが、一ヶ月しか経っていないのに機械的に解 […] 先月ご紹介してなかなか好評だった、画像をグニャリと円状に曲げて加工し、それを正しい状態に戻すことで人間かスパムプログラムかを判定するという新方式のCAPTCHA MintEyeですが、一ヶ月しか経っていないのに機械的に解いてしまう話が出てきてしまいました。それもPythonでたった23行のコードで。 このスクリプトがやっているのは、グレースケールに変換した上で、Sobel()で画像上のエッジを取得し、エッジの合計をグラフにプロットしている、というだけですね。画像ファイルを開くところやグラフを描くところを除けば、数行の短さです。 スライダーにあわせて表示されるすべて
画像処理 - HexeRein
description 画像処理について。 ソースは24bitのビットマップ（及びその互換）、EclipseによるJava環境（org.eclipse.swt.graphicsとjava.utils.Arrays。具体的にはこんな感じ）を前提に記述していますが、ピクセル毎に入出力できる環境であれば任意に読み替えて問題ありません。 具体的には、画像から幅、高さ、指定場所の画素といったものが利用出来、なおかつそれから画像を生成できることが条件となります。 低機能でも良ければC++用の簡易クラス（.cppファイル、.hファイル）とかあります。 ただし、簡易クラスの方では色データはRGB纏まった形で取得するのではなくて、GetR等のように一つ一つの色を取り出す必要がありますので、以下のソースコードそのままでは使用できない場合（や、面倒な前処理が不要となる場合）があります。 なお、ソースそれ自体は適
プログラミングコンテストでの乱択アルゴリズム
前編 (平衡二分探索木編) はこちら http://www.slideshare.net/iwiwi/2-12188757
CGI Error
The error was detected while processing this request. Be sure of followings: The CGI script does exist. The permission of CGI script is 755. The Perl path in CGI script is #!/usr/local/bin/perl. CGIスクリプトの呼び出し中にエラーが発生しました。 下記の点をご確認ください。 ・CGIスクリプトが存在すること。 ・CGIスクリプトのパーミッションが755であること。 ・CGIスクリプトのperlのパスが #!/usr/local/bin/perl であること。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
冬のLock-Free祭り)
Excel 2010 Performance: Improving Calculation Performance
Glibc malloc internal
