DocBaseの同時編集機能を実現しているアルゴリズム – KRAY Inc.
はじめに 皆さんはGoogleドキュメントやHackMDを使ったことはあるでしょうか。これらのツールは「ネット越しに同時に複数の人で1つのドキュメントを編集できる」という特徴を持っています。お互いの編集がリアルタイムに反映されるので、相手が何を書くのかを意識することなく、簡単にドキュメントを複数人で編集することができます。これを実現するためには、同時編集に参加しているユーザ全員の編集内容がネットワークの延滞に影響されることなく、それぞれの編集内容をうまい具合にマージして反映してくれるような賢いアルゴリズムが必要になります。今回はこのアルゴリズムに関して書きます。 編集内容のマージとは 編集内容をうまい具合にマージしなければいけないケースを考えてみます。 AさんとBさんが次のドキュメントを同時編集するとします。最初は、お互いブラウザ上では次のように見えています。当然、この状態ではお互いに見え
「プログラミングの常識」を時々見直す必要性について｜Rui Ueyama
自分の中のプログラミングの常識というものは、ときどき現実のハードウェアに合わせて調節しないといけない。ハードウェアが進歩し続けているので、コンピュータで簡単にできることと相対的に難しいことのバランスが変化し続けているからだ。ここでは特にストレージにフォーカスして書こうと思う。 昔はメモリが相対的にとても貴重な資源だったので多くのプログラマがメモリを節約することに血道を上げていた。例えばWindowsの初期の頃に設計されたデータ構造には、メモリをバイト単位ででもいいから節約したいという意図の痕跡がいまでも多く見受けられる。DRAMの次に速い記憶装置はHDDだったので、メモリが足りなくなればHDDにデータを保存せざるを得ないのだが、DRAMとHDDのランダムアクセスの速度差は、机の上の本の開いているページを見るのと、その本をAmazonで注文して到着するのを待つのと同じくらいのスケールで違うの
bliki: Circuit Breaker
It's common for software systems to make remote calls to software running in different processes, probably on different machines across a network. One of the big differences between in-memory calls and remote calls is that remote calls can fail, or hang without a response until some timeout limit is reached. What's worse if you have many callers on a unresponsive supplier, then you can run out of
はじめてのAdversarial Example
今回はadversarial exampleについて解説していきます。Adversarial exampleというのは、下図のように摂動を与えることによりモデルに間違った答えを出力させてしまうもののことです。 この例では、もともとモデルがパンダと正しく分類することができていた画像に摂動を与えることで、テナガザルと誤分類させています。しかし、人間には元の画像との違いはほとんど分からず、パンダのままに見えます。 Adversarial exampleは機械学習モデルを実用化していく上で大きな問題となります。例えば、交通標識をadversarial exampleにしてしまえば、自動運転車をだませてしまう可能性があります。 注目を集めてきている研究分野ですが、まだちゃんと調べたことがないという人も多いかと思います。今回もなるべく丁寧に解説していきたいと思います。 目次 基礎 攻撃 防御 論文紹介
差分検出アルゴリズム三種盛り - Object.create(null)
こんばんは. 気がつけばもうずいぶんと涼しくなってきました. 勢い余って凍ってしまったりせぬよう, くれぐれも普段の言動にはお気をつけください. はじめに さて, 我々人類にはどうしても二つの文字列 (あるいは行ごとに区切られたテキスト) 間の差分を求めなければいけない瞬間が発生します. 先人たちはそういった時のために diff のようなツールを開発し, それを利用することで文明はめざましい発展を遂げてきました. しかしながら, 使用するアルゴリズムを比較検討したい場合, 「差分」の定義を変えるなどして既存のアルゴリズムに変更を加えたい場合, diff のない異世界に飛ばされて自分で実装しなければいけない時などにおいては, 差分検出アルゴリズムについての理解が必要不可欠です. というわけで, この記事では文字列間の差分検出とは何かということと, 差分を求める三種類のアルゴリズムの紹介・解説
C言語でインクルードするだけで使えるNon-movingで正確なコピーGCを作った - Qiita
C言語でインクルードするだけで使えるNon-movingで正確なコピーGCを作った インクルードするだけで使えるNon-movingで正確なGCをC言語用に作りました。 行数がコメントを除いて100行に満たない非常に小さなライブラリです。 GCのアルゴリズムとしてはCheneyのコピーGCを採用しています。 通常のCheneyのコピーGCではメモリ空間のうち半分が無駄になってしまいメモリ効率が悪かったり、 GC発生時にオブジェクトが移動してしまいC言語のようなポインタを直接触れる言語との相性が悪いという欠点がありました。 今回はヒープ全体を二重連結リストとして管理することでそのような問題を解決しています。 ちなみにこれはTreadmill GCのアイデアと同じです。(が、アルゴリズム自体はTreadmill GCではありません。) APIはLinuxのlist.hに非常に近い見た目になって
いろいろな言語での Map, Dictionary 的なものの名前 - Qiita
いろいろな言語で、キーと値とを対応づけるデータ構造、いわゆる連想配列、辞書、……たちがどのように呼ばれているか、気になったので調べてみた。 おおよそ、対応表（map）、辞書（dictionary）、実装の名前をそのまま（hash-table）、 Perl風（hash）に分けられると思う。 Common Lisp: hash-table Scheme: hash-table (SRFI-69, SRFI-125 → R7RS-large), hashtable (R6RS Scheme, SRFI-126), map (SRFI-44), mapping (SRFI-146) Haskell: Map OCaml: Hashtbl, Map SML: hash_table (sml-nj-lib) C++: map, multimap, unordered_map, unordered_mu
AutoLayout Algorithm
iOSDC 2017 (Sep 16, 2017) https://iosdc.jp/2017/node/1317 Library: https://github.com/inamiy/Cassowary
iOSDC Japan 2017で「Auto Layoutのアルゴリズム」について発表しました - Qiita
こんにちは、オートレイアウト作ったマン の @inamiy です。 オートレイアウト○○マンが全員集結したMARVEL映画に出るのが将来の夢です。 さて先日、2017年9月15-17日の2.5日間にかけて、iOSDC Japan 2017というiOSの一大イベントが、早稲田大学理工学部・西早稲田キャンパスにて開催されました。 昨年に引き続き、第2回目の開催で、総勢800名が参加されたとのことです。 スピーカーの人数も倍増して、大成功した昨年の2016年をさらに上回る規模となりました。 そんな中、私は今年のテーマとして、「Auto Layoutのアルゴリズム」という若干マニアックな話を選びました。 今年は4トラック同時進行ということもあり、実際にセッションに集まるのは100〜200人くらいだろうと想像していましたが、タイムスケジュールが公開されると、まさかのキーノート登壇！（トップバッター＋
JITコンパイルでの冒険 パート1：インタプリタ | POSTD
本記事は、JITコンパイラに関するシリーズの第1回目です。計画としては、シンプルな入力言語を使ってそのインタプリタとJITをいくつか開発し、段々と複雑なものにしていくつもりです。このシリーズが終わるまでに、JITコンパイラの開発に何が必要か、そのためにどんな支援ツールが使えるかを、読者の皆さんによく理解していただけるようになれば幸いです。 入力言語は Brainfuck です。本シリーズでは以後、BFと呼んでいきます。BFはプログラマビリティの本質を突き詰めるので、今回の目的に適した言語だと思います。BFは、プログラミングは非常に冗長ですが、なじみのC構造体に直接マップするメモリポインタやループのような概念を持つ点で、プログラミング言語としてはかなりの”メインストリーム”です。 実装言語にはC++を使います。”手始め”の言語としては一般的ではないかもしれません。とはいえ、私の知っている大部
pixivコミック作品のタグが自動生成されるまでの軌跡 - pixiv inside
「pixivコミック・ノベル」チームのエンジニアの pawa です。 pixivコミックはWebやアプリで漫画を試し読みできるサービスです。私が一番好きな pixivコミック作品は「温泉卓球☆コンパニオンズ！」です。 2017年7月4日、pixivコミック（Web版）の作品ページにタグ機能が追加されました。 これらのタグは、作品説明文から自動的に抽出されたもので、コンピュータに計算させた「作品のキーワードとして妥当な順番」に並んでいます。 今回は、このタグ機能が生まれるまでの物語をご紹介します。 問題提起 pixivコミックに携わる者として、以前から、次の2点を問題だと感じていました。 特定のジャンル（たとえばスポーツ）の漫画を探すのが難しい 「あわせて読みたい」作品がなぜ「あわせて読みたい」のか分かりにくい 私は、社会人になってから、大好きなスポーツが共通する人とスポーツをすることの果て
輻輳制御の新アルゴリズム 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
CPU の AES 高速化
Intel と AMD の CPU には AES-NI という CPU 命令拡張が搭載されています。詳細は Wikipedia を読んでください。ちなみに ARM にも AES 拡張が搭載されているものがあります。 ちなみに 私自身はハードがわからないので AES-NI の知識はまったくありません。AES がハードウェアによって高速化される程度の知識です。 ただ、AES といっても暗号の種類は CBC 以外にも、最近良く使われている AES-GCM (TLS 1.2 で利用) や、 WebRTC の SRTP で利用されている AES-CTR があり、実は CPU ごとに AES-GCM や AES-CTR はかなりの差があるというのを最近調べていて気づきました。 ということでインターネッツのちからを使って募集してみることにしました。この記事を読んだ人も是非お時間あれば、気軽にコメントして
タイムストレッチ、ピッチシフトのアルゴリズム
タイムストレッチは音程を保ったまま再生速度を変える処理、 ピッチシフトは再生速度を保ったまま音程を変える処理です。 下図のように単純に波形を拡大、縮小すると再生速度と音程が 両方変わってしまいます。再生速度と音程を別々に変更するには 特殊な処理をする必要があります。 タイムストレッチ、ピッチシフトのアルゴリズムには、 FFTを用いる手法やクロスフェードを利用する手法などがあります。 以下ではWaveToneで採用しているクロスフェードによるタイムストレッチ、 ピッチシフトのアルゴリズムについて解説します。 タイムストレッチの基本的なアルゴリズム 再生速度を2倍にするには、下図のように波形を小さなブロックに分割し、 ブロックを1つおきに配置します。 再生速度を0.5倍にするには、コピー元の位置を0.5ブロックずつずらしながら ブロックを配置します。 ブロックのサイズをある程度大きくしないと、
HTC端末、突如としてデフォルトキーボードに広告表示が開始される - すまほん!!
台湾メーカーHTC製の、多くの端末のデフォルトの文字入力には、「TouchPal Sense Edition」こと「TouchPal Keyboard for HTC」が搭載して出荷されています。最新のHTC 10やHTC U11もこの例に漏れません。 しかしこの「TouchPal Keyboard for HTC」が、最近のアップデートによって、突如として広告が表示されるようになったと海外で報告されています。どうやらキーボード上部に広告が出るようです。 @htc why the fuck are there ads attached to my keyboard when I’m texting or even tweeting this damn question pic.twitter.com/SU5zo3M2Lk — Mer-Meg (@meeeganmeow) 2017年7月16
量子コンピュータで１＋１を計算する - Qiita
はじめに IBM Q の公開で無料で量子コンピュータをいじって遊べる素敵な時代がやってきました。私は 1+1 の計算をやってみたのですが、なかなか面白かったので投稿してみることにしました。実用性はありませんが、量子コンピュータの学習には適当かと思います。 ログイン IBM Q を開き、ユーザ登録をします。 ログインしたら Composer をクリック、Custom Topology を選択します。 Topology は Quantum 及び Classical の Registers を 4 に減らし、Set Topology を押して次に進みます。 0+0=0 の回路の作成 下図の回路をマウスで作成します。Gates からゲートを選択し、線の上でクリックすると置けます。 Gates の Advanced チェックボックスをチェックしてください。ccXが使えるようになります。 それぞれの意
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
LinkedHashMapはなぜ defaultにすべきではないか - 外神田バナナ加工
マイナンバーのチェックデジットがかなり恥ずかしい件について - CSS2017キャンドルスターセッション
分散システムについて語らせてくれ
GitHub - facebook/zstd: Zstandard - Fast real-time compression algorithm
