輻輳制御の新アルゴリズム TCP BBR を GCP に導入 | Google Cloud 公式ブログ
私たちはこのほど、インターネット トラフィックの帯域幅を広げ、レイテンシを低減する最先端の輻輳制御アルゴリズム、TCP BBR を Google Cloud Platform（GCP）に導入しました。TCP BBR は、google.com からの TCP トラフィックで使われ、YouTube ネットワークのスループットを全世界平均で 4 %、一部の国では 14 % 以上引き上げたのと同じ BBR です。 私たち WP Engine のデジタル エクスペリエンス プラットフォーム上で稼働する 50 万の WordPress サイトは、BBR のおかげで驚異的な速さでロードできるようになりました。Google のテストによれば、BBR のスループットはこれまでベストだった loss-based 輻輳制御の 2,700 倍に達し、キューイング遅延は 25 倍も下がっています。私たちが GCP
UTF-8のコードポイントはどうやって高速に数えるか - Qiita
UTF-8文字列からコードポイント数を計算するアルゴリズムについて紹介します。コードポイント数カウントは、シンプルに書くのはそれほど難しくないものの、高効率な実装は意外にややこしいです。 内容は二本立てです。 実践的な実装について、Ruby(CRuby)の内部実装(string.c)で使われているものを紹介します。 標準Cの範囲を超えて、SIMD命令(AVX/AVX2)を使った実装についても述べます 軽く検索する限りだと既知のアルゴリズムが見当たらなかったので、アドホックな実装をひねり出しましたが、そんなに効率は悪くなさそうです おまけで簡単な性能評価をやってみました。 なお、UTF-8文字列はバリデーション済み（不正なシーケンスでないことが分かっている）であるとします。 Rubyの内部実装だとどうやっているか まずは、それがコードポイントの先頭バイト(leading byte)かを判定す
Adiantum : 低廉な端末でも効率的に使える暗号化技術
.app 1 .dev 1 #11WeeksOfAndroid 13 #11WeeksOfAndroid Android TV 1 #Android11 3 #DevFest16 1 #DevFest17 1 #DevFest18 1 #DevFest19 1 #DevFest20 1 #DevFest21 1 #DevFest22 1 #DevFest23 1 #hack4jp 3 11 weeks of Android 2 A MESSAGE FROM OUR CEO 1 A/B Testing 1 A4A 4 Accelerator 6 Accessibility 1 accuracy 1 Actions on Google 16 Activation Atlas 1 address validation API 1 Addy Osmani 1 ADK 2 AdMob 32 Ads
高速な比較安定ソートアルゴリズム「颯式」の紹介（ベンチマークあり） - Qiita
颯式（はやてしき）は、「クイックソート種より高速」を目指した、マージソートの改良アルゴリズムです。 以下の特徴があります。 比較ソート 安定ソート 外部領域：N 最良：O(N) 平均：O(N log N) 最悪：O(N log N) 再帰：無し リポジトリ 颯式（はやてしき） MIT License 基本となるアルゴリズム 外部領域を、2Nの連続帯として見立てます。 値を外部領域に置く際、以下のルールを適用します。 （最大値 ≦ 値）であれば、昇順列の上側に置き、最大値を更新します。 （値 ＜ 最小値）であれば、降順列の下側に置き、最小値を更新します。 （最小値 ≦ 値 ＜ 最大値）であれば、新しい値（最大値であり最小値）を昇順列に置き、それまでに並べた値群をPartとします。 Part群をマージします。 具体的な流れ 外部領域を、2Nの連続帯として見立てます 4 5 1 2 7 6 3
bcryptの72文字制限をSHA-512ハッシュで回避する方式の注意点
宅ふぁいる便から平文パスワードが漏洩した件を受けて、あらためてパスワードの安全な保存方法が関心を集めています。現在のパスワード保存のベストプラクティスは、パスワード保存に特化したハッシュ関数（ソルトやストレッチングも用いる）であるbcryptやArgon2などを用いることです。PHPの場合は、PHP5.5以降で使用できるpassword_hash関数が非常に便利ですし、他の言語やアプリケーションフレームワークでも、それぞれ用意されているパスワード保護の機能を使うことはパスワード保護の第一選択肢となります。 なかでもbcryptは、PHPのpassword_hash関数のデフォルトアルゴリズムである他、他の言語でも安全なハッシュ保存機能として広く利用されていますが、パスワードが最大72文字で切り詰められるという実装上の特性があり、その点が気になる人もいるようです（この制限はDoS脆弱性回避が
「高速文字列解析の世界」を読む前に知っておくと良いこと - EchizenBlog-Zwei
「高速文字列解析の世界」という大変すばらしい本が発売された。わりと敷居が高い本ではあるので読む前に知っておくとよさそうなことを書いておく。 「高速文字列解析」とは 本書でいう高速文字列解析というのは主に2つのことを指している。ひとつはデータを圧縮して小さくしてディスクよりメモリ、メモリよりキャッシュというようにより高速な記憶装置で扱いましょう、という話。もうひとつはデータ構造を工夫することで複雑な操作もそこそこ高速に扱えますよ、という話。つまり「圧縮」の話と「効率的なデータ構造」の話があると考えておくと良い。 キーワードは3つ オビにも書いてあるけれど、本書が主に扱うのは「BWT」「簡潔データ構造」「ウェーブレット木」の3つ。具体的には「BWT」が「圧縮」に関わっていて「ウェーブレット木」が「効率的なデータ構造」に関わっている。「簡潔データ構造」は基本的な道具として本書の色々なところで出て
中学生にもわかるウェーブレット行列 - アスペ日記
id:echizen_tm さんの記事「ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix"」から始まったウェーブレット行列ブームから半年以上が過ぎ、すでに枯れた技術として確立されつつある感があります。 …嘘です。 日本以外ではあんまり来ていません。 理由としては、やはりアルファベット圏では単語境界が明確であるため、こちらの記事で書かれているような「キーワード分割の難易度」といったことがあまり問題にならないということがあるかもしれません。 まあ、そういうわけで局所的に来ているウェーブレット行列ですが、日本語をはじめとする単語境界のない言語圏にとっては重要なネタであると思うため、解説記事を書き直して*1みようと思います。 ウェーブレット行列でできること 主となる操作は、文字列に対する 定数時間の rank() と select()*2 です。 rank() は、「文
画像処理100本ノックを作ったった - Qiita
画像処理が初めての人のための問題集をつくったりました。（完成！！） 研究室の後輩用に作ったものです。 自然言語処理100本ノックがあるのに、画像処理のがなかったので作ってみました。 あくまで趣味ベースで作ったものなので、プルリクエストは受け付けてますが依頼などは一切受け付けません そこをご理解頂けた方のみご利用下さい 画像処理の基本のアルゴリズム理解につながると思います。 pythonのnumpyの練習にもなると思います。(2019.3.8 C++もつくってますーー） ぜひぜひ下のgitをやってみてください。 [HP]https://yoyoyo-yo.github.io/Gasyori100knock/ [Git]https://github.com/yoyoyo-yo/Gasyori100knock ★追記 2020.5.8 環境構築の手間をなくすために、Google Colabに修正
ソート可能なUUID互換のulidが便利そう - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? UUIDは重複しないIDを生成する手段として便利ですが、特にversion4(乱数によるUUID)を利用する場合は一意性を得るのと同時に乱雑さも得ることになりますので、UUIDに順序性を求めることができません。 UUID - Wikipedia https://ja.wikipedia.org/wiki/UUID UUID（Universally Unique Identifier）とは、ソフトウェア上でオブジェクトを一意に識別するための識別子である。UUIDは128ビットの数値だが、十六進法による550e8400-e29b-41d4-
とても強い計算量クラスのコンピュータとその実現方法 - Qiita
この記事は武蔵野アドベントカレンダー19日目の記事です。 物理のステートメントはだいぶ雑ですが、計算のステートメントには一応正確さに気を使って書いているつもりです。何か誤りがあった場合は、@iKodackまでご連絡いただけると幸いです。 (2018/12/22に「宇宙破壊コンピュータはセールスマン巡回問題の最適化問題を解けるか？ 」「時間遡行コンピュータで無限ループすると何が起きるか？」を記事末尾に追加しました。) (2018/12/28に「宇宙破壊コンピュータは答えが無い場合に全ての宇宙を破壊する？」について記事末尾に追加しました。) 前書き より速い計算機が欲しい、という欲求は全ソフトウェアエンジニア共通であることが知られています。 最近、業務において500GBのSSDや16GBのメモリを最低水準にするべきではないか、という議論がネットで活発になされていますが、生産性を限界まで高める限
簡潔ビットベクトルでRubyをlog N倍速くした - クックパッド開発者ブログ
技術部のフルタイムRubyコミッタの遠藤（@mametter）です。昨日の Hackarade #04 の開催報告に続き、2日連続で記事を投稿します。 今回は、ある条件下でのRubyの実行速度を高速化した話を紹介します。この改善はすでにMRIの先端にコミットされていて*1、年末リリース予定のRuby 2.6に含まれる予定です。 ひとことで言うと、「簡潔ビットベクトルを索引に使うことで、プログラムカウンタから行番号を計算するアルゴリズムをO(log N)からO(1)に改善した。これにより、TracePoint有効時やコードカバレッジ測定下で、長さ N のメソッドの実行が O(N log N) から O(N) に高速化される」ということです。順に説明します。 背景：Rubyのバイトコードの構造 この最適化を理解するにはまず、Rubyのバイトコードのある特徴を知る必要があります。 たとえば x
ニュースパスを支える関連記事推薦と近似近傍探索 - Gunosyデータ分析ブログ
こんにちは。メディアロジック分析部の米田 (@mathetake) です。 今日はGunosy社とKDDI社が共同で運営するニュースパスというニュースアプリケーションで使われている関連記事推薦のアルゴリズムについて書きたいと思います。 特に、約半年前に私が導入しKPIの改善に成功した新しいアルゴリズムと、そこでコアとなる近似近傍探索(Approximate Nearest Neighbor search)の技術について述べます。 関連記事推薦とは この記事で紹介する関連記事推薦とは、「特定のニュースに関連したニュースを推薦すること」です。 より具体的には、特定の記事をクリックした後に記事閲覧画面を下にスクロールすると登場する「おすすめ記事」の枠に対して、関連したニュースを検索して表示することを指します: このような枠が設置されている事は一般的なアプリケーションにおいてごく自然ですが、推薦シ
Post by @shyouhei
とりあえずHashが何であるかとか、どういう作りになっているかとか、そういうことは既知とする。リストの配列ってことね。←これで何言ってるか分からないおまえらにはこの文章はちょっとはやい。先にデータ構造の教科書を読むことをおすすめ。以下ではHashに登録されるキーとデータのペアのことをentryと呼び、リストの配列と言ったときのリストのほうをbin、配列のほうをbucketと呼ぶ。つまり、
マイナンバーのチェックディジット計算
[2018-08-07 おことわり] JavaScriptで書かれたマイナンバーのチェックディジット計算プログラムを公開していましたが，個人情報保護委員会様から，入力されたものがネットに流れないことはソースで確認したが，マイナンバー収集を誤認するようなページは好ましくないのではないかというご意見をいただきました。確かにもっともなことですので，ソースコードを示すだけにとどめることにしました。このソースを打ち込めば確認できますので，ご自分でお試しください。 <p><label>マイナンバーの先頭11桁：<input id="input" size="13" onchange="check()"></label></p> <p>マイナンバーの最後の桁（チェックディジット）：<input id="output" size="5" readonly></p> <script> function ch
Halide事始め - プログラミングの実験場
MIT Halide(http://halide-lang.org/)というC++の高速画像処理ライブラリが去年リリースされた。C++内のDSLを使っていて、画像処理を、 計算のアルゴリズム アルゴリズム自体は副作用がなく、純粋関数的に定義される。 実装の詳細（「スケジュール」） スケジュールは、計算の並列化と、複数の計算ステップの融合を最適化する方法を指定する。 を分離した形で簡潔に書ける。 凄いのは、抽象的に書いたアルゴリズムからライブラリによって低レベルコードを出力させたほうが、手書きでチューニングしたコードよりも速いことすらあること（という作者の主張）。たとえば最近開発されたlocal Laplacian filterというの複雑なアルゴリズム（http://people.csail.mit.edu/sparis/publi/2011/siggraph/、pixelwise ope
分散システム、本当に「正しく」開発できますか？ #JTF2018 / July Tech Festa 2018
July Tech Festa 2018 で使用したスライドです。二相コミットを例として、分散アルゴリズムの検証にモデル検査を使用する手法について解説しています。また、代表的なモデル検査ツールである SPIN、TLA+、P について、同じシステムを各ツールで記述してみることでその特定の違いについて学びま…
Linuxのloadavgが約7時間ごとに上昇する現象の原因 - Mackerel ブログ #mackerelio
Mackerelチームのエンジニアのid:itchynyです。 「mackerel-agentを入れるとloadavgが7時間ごとに上昇する」 先日、このような問い合わせを複数のお客さまから受けました。私も実験してみたところ、確かに再現しました。EC2 t2.microにmackerel-agentを入れて簡単なログ監視とプロセス監視を設定し、数日放置しました。 確かに、約7時間ごとにloadavgが上昇しています。この周期のcronの設定はしておらず、またmackerel-agent内部でも7時間ごとに行う処理はありません。しかし、プラグインを多く入れるほどloadavgのピーク値も上がります。 本エントリーでは、この現象の原因について説明します。 loadavgが上昇する原因を調べるには、まずloadavg自体がどう計算されているかを知る必要があります。 まずは、Linuxがloada
なぜWii版マリオ64で長時間放置すると足場が浮かび上がるのか（非技術者向け解説）
ゲームのバグって面白いですよね。進行不可能バグはもちろん論外ですが、ちょっとした不思議なバグはなかなかに楽しめます。 さて、今回話題になったのはWii版（バーチャルコンソール）のマリオ64で、「長時間たつと足場がどんどん浮き上がる」というものです。オリジナル版では起こらず、バーチャルコンソール版だけで起こるというのがミソです。 この摩訶不思議なバグがいったいどうやって起きているのか、確かめていきましょう。 話題のバグ：時間が経つと足場が浮かぶ Automatonなどで記事になった「『スーパーマリオ64』を研究するプレイヤーたちは、Aボタンを押さずステージクリアするために3日間待ち続ける」がゲーマーの間で話題になっています。 このバグは、炎の海から顔を出したり沈んだりするだけの足場が、時間が経つにつれほんの少しずつ炎の海から浮遊するというものです。ゲームを起動したまま3日間放置すると、足場が
Java におけるデータ圧縮とそのライブラリ事情について #jjug_ccc 2018 Spring でお話しました
※ 発表で使用したスライドより、本質的ではないスライドは省いています。 振り返りPermalink CfP を投げるときに何を血迷ったか 20 分枠で応募してしまったがために、時間的な制約によって深い・細かい話は一切できずに代表的な圧縮アルゴリズムのざっくり説明とその Java 向けライブラリの紹介、そしてちょっとした比較に終始してしまいました。これでは、発表タイトルにある「極める」とは程遠い内容だな… と反省するばかりです。 なお、Java そのものからはちょっとずれた「データ圧縮」というテーマ設定での発表ではありましたが、ご回答いただいたアンケートで もう少しロジックに踏み込んだ話が聞きたかった。 という声があったり、Twitter 上でも こういうの好き。20分しかなかったので圧縮の「比較」に注力したのだと思うんだけど、45分あれば少し踏み込んでアルゴリズムの違いとかも話してくれそう
ニューラルネットワーク、多様体、トポロジー - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? Christopher Olah氏のブログ記事 http://colah.github.io/posts/2014-03-NN-Manifolds-Topology/ の翻訳です。 翻訳の誤りなどあればご指摘お待ちしております。 #ニューラルネットワーク、多様体、トポロジー 近年、深層ニューラルネットワークには多くの興奮と関心が寄せられています。コンピュータビジョンなどの分野でブレークスルーとなる成果を達成したためです。1 しかし、それにはいくつかの懸念が残ります。そのひとつは、ニューラルネットワークが実際に 何を やっているかを理解す
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
