リアルタイム共同編集のアルゴリズム (Operational Transformation; OT) を理解する試み – RORO
Google Docsのように文書を複数人でリアルタイムに共同編集できるアプリケーションがあります。あのような機能は、多かれ少なかれ、Operational Transformation (OT; 操作変換) という考え方を使って実現されているようです。興味があったので、このOTについて調べてみました。 (追記: これからは OT でなく CRDT だという話 → I was wrong. CRDTs are the future) なおGoogle Docsではいわゆる「リッチテキスト」を共同編集できますが、ここでは話を簡単にするために「プレーンテキスト」を共同編集することを想定します。 リアルタイム共同編集の流れ 共同編集システムの登場人物は次の通りです： サーバ x 1（各クライアントから届く編集操作をもとに、最新の文書を保持します） クライアント x N（文書を編集する側です） そ
攻撃して学ぶJWT【ハンズオンあり】 - Money Forward Developers Blog
こんにちは。 マネーフォワードの新卒Railsエンジニア、きなこ と申します。 マネーフォワードX という組織で、日々プロダクトの開発に勤しんでおります😊 突然ですが皆さんは JWT という技術をご存知でしょうか？ 私は趣味でCTFというセキュリティコンテストに出場するのですが、最近ホットだと感じるのがJWTに関連する攻撃です。 今年の1月に初めてJWTを題材にした問題に遭遇し、その後JWTの出題頻度が強まっていると感じ、社内に向けてJWTにまつわる攻撃を通して学ぶための記事を書いたところ、たくさんの反応をいただきました。 今回の記事はその内容を社外向けにアレンジし、ハンズオンを通して実際にJWTを改竄し、受け取るAPIを攻撃することでJWT自体を学べるようにしたものです。 本記事はJWTに興味があるWeb開発者を想定していますが、そうでない方も楽しんでいただけるようにハンズオンを用意し
クリエイティブコーディングの教科書
ゲームエンジンや3Dソフトウェアを利用して高度な表現ができるこの時代でも、プリミティブな描画や動き、アルゴリズムから学べることは多い。それらをJavaScriptで書くクリエイティブコーディングという形で学べる手引書が本書となる。
How to leverage optimal transport
大幅な加筆改訂を加えた最新版はこちらです： https://speakerdeck.com/eumesy/optimal-transport-for-natural-language-processing --- 最適輸送の使い方 〜最適輸送の直感的理解のための単語埋込入門 兼 最適輸送入門〜 【これは何？】 自然言語処理を中心に多くの利用例を挙げながら、最適輸送の直感的な理解を目指すスライドです。 「こんな風に使うことができるんだ… 面白い道具じゃん」「こういう使い方をしたかったらこういうキーワードで調べれば良いのね」と知識にアンカーを張ることが目的です。より深く知りたい人のための参考文献もできるだけ潤沢に加えました。 また、例として頻繁に活用する自然言語処理に馴染みがないかたのために、最初に単語埋め込みのチュートリアルをつけてあります。 【コンテンツ】 1. 単語埋込入門 … 「分布仮
Binary search with modern processors
第16回 StringBeginners での発表資料
サイトトップにAIを導入して売り上げに1億円貢献する - エムスリーテックブログ
エンジニアリンググループ AI・機械学習チームの金山 (@tkanayama_)です。今回は、私が立ち上げ段階から主担当として推進しているプロジェクトである、サイトトップページのコンテンツを自動更新するシステムの開発について書きます。後のA/Bテストにより、このシステムは年間換算で1億円規模の売り上げ貢献をしていることを示すことができました。この記事では、こうしたインパクトの大きいプロジェクトがどのように進行したかを説明します。よく弊社のブログや勉強会などで語られる「エムスリーはROIを重視する風土がある」ことの一例だと思って読んでいただければと思います。 （なお、タイトルに「AI」や「1億円」という強い言葉を並べてしまったことをここに懺悔します。） プロジェクトの概要 エムスリーでは、医療従事者向け総合医療情報である「m3.com」というウェブサイトを運営しています。このウェブサイト上に
Raft
2. 自己紹介 久保田展行 (@nobu_k) Preferred Infrastructure America, Inc. 取締役 本日の NG ワード「いつアメリカ行くの？」 MessagePack for C,C++ メンテナ 分散システム、 DB 、検索エンジン 最近 golang に夢中 2 3. 今日の話： Raft Raft とは 複製されたログを管理するためのコンセンサス ( 合意 ) アルゴリズ ム Raft はわかりやすさを重視して作られた 既存のアルゴリズムは難しすぎて正しく実装するのが困難 もしくは、難しい部分を簡単にしようとして安全ではなくなったり この先生きのこるには分散システムの理解が必須 コンセンサスは安全な分散システムを構築する上で必須のトピック ツールとして使うにしても、中身や特性は理解しておくべき
The Art of PNG Glitch
Overview PNG is an image format that has a history of development beginning in 1995, and it is still a popular, long living format. Generally, it is known for its features such as lossless compression and the ability to handle transparent pixels. However, we do not look at image formats from a general point of view, but rather think of ways to glitch them. When we look at PNG from the point of vie
[KMP77] を読んでみた - d.y.d.
17:53 14/12/22 ソートの逆流れ クイックソートってあるじゃないですか、クイックソート。 配列、たとえば [4,2,1,7,0,6,5,3] があったときに、 小さい方を左に、大きい方を右にまず適当に集める。 この「小さい方」と「大きい方」への二分割を、いわゆる再帰的に、 分かれたブロック両方で同じ事を繰り返していくと… なんと、小さい順に並んだ配列 [0,1,2,3,4,5,6,7] が出来上がるというアルゴリズムです。 逆向き！ このデータの流れを「逆向きに」見てみたい。つまり、ソートが終わった最終状態から話が始まります。 しかも、さっきから説明なしで意味ありげにくっついていた、 「入力配列で元々どの位置にあったか」を表す値に注目していきます。 0の上に[4]がくっついているのは、最初は値0は配列のインデックス[4]の位置にあった、 ということを意味しています。（上のソート
![[KMP77] を読んでみた - d.y.d.](https://cdn-ak-scissors.b.st-hatena.com/image/square/e6fe840dfdcca31b69f48171e0de96a69b93595b/height=288;version=1;width=512/http%3A%2F%2Fwww.kmonos.net%2Fwlog%2Fsub%2Fdual%2F8.png)
バブルソートよりも非効率なソートアルゴリズムを探して ―― ストゥージソートとスローソート - Line 1: Error: Invalid Blog('by Esehara' )
はじめに 恐らく、プログラマの中で配列内の要素を整列させたりするソートにお世話にならなかった人、というのは余り考えられないのではないでしょうか。しかし、とはいえ、大抵はソートを自前で実装せず、組み込み関数であったり、あるいは何らかのライブラリで済ませることが殆どだと思う。 車輪の再発明というよりも、バグとか、自分が考慮していなかった挙動などを避けるために、自前でソートを組むことは余りないのですが、とはいえ、自分なりにソートを実装して見ると、それがどういう特徴を持ったソートであるか、というのがわかりますし、また、ソートというのはいったいどういう操作で実現されるのかという洞察が深まってくるなあ、という実感があったりする。 なので、今回はあるソート二つについての話を書くのが趣旨です。 最高のアルゴリズムはある、だが最悪のアルゴリズムは何か 一口にソートといったところで、ソート自体にも銀の弾丸があ
x86x64 SSE4.2 POPCNT
2. ビットを数える例題ここにいるバイナリアンの数は何人か？机 1 0 0 1 = 0x0A (ビット2個)机 1 1 1 1 = 0x0F (ビット4個)机 1 1 1 0 = 0x0E (ビット3個)机 1 1 1 1 = 0x0F (ビット4個)机 1 1 1 1 = 0x0F (ビット4個)合計 17人 4. (1) popCount 8bit If1 byte あたり 8回条件分岐して bit を数える for (int i = 0; i < n; i++) { if (*x & 0x01) c++; if (*x & 0x02) c++; if (*x & 0x04) c++; if (*x & 0x08) c++; if (*x & 0x10) c++; if (*x & 0x20) c++; if (*x & 0x40) c++; if (*x & 0x80) c++; x
Haskellで円周率1億桁を計算する、あるいは円周率計算にHaskellの多倍長整数の改良を見る - 純粋関数空間
きっかけ http://d.hatena.ne.jp/itchyny/20120304 この記事を見て、私も昔円周率を計算したことがあるのを思い出しました。 http://d.hatena.ne.jp/tanakh/20070506#p1 公式は同じくチュドノフスキーを使用、GHCのIntegerをそのまま用いて円周率を計算、 当時（5年前）のマシン（おそらくCore2あたり）で1億桁が15分ほどだったようです。 SPOJというサイトのコンテスト向けに、 $\sqrt{2}$ 200万桁計算の高速化 をCで書くとこから始めて、 ナイーブ乗算、カラツバ法、そしてFFT乗算の実装にいたり、円周率へ。 最初AGMを実装し、 古くて新しい方法、Arctan系の公式の実装を経て Binary Splitting Methodを知り、 チュドノフスキーの公式へ至りました。 さらにHaskellでの実装
C/C++向け多倍長整数資料を探している人のためのガイド - 世界線航跡蔵
多倍長整数の解説執筆がいつまで経っても進展しないので、お詫びの印にガイドを書いてみる 実装が欲しいよ派（実用主義派） お金は掛けたくないよ派 GMPとか、Mintはどうでしょうね。前者は開発者もユーザーも多いのでその点で信頼性が期待できますし、かなり速いです。後者は、x86限定ですが、ドキュメントも日本語ですし分かりやすく、設計上も使いやすい感じです。作者の苫米地聰さんは数体篩い法の実装などで知られる、計算実験に関してはかなり凄い人です。 あるいは、いっそPythonインタプリタやGaucheを埋め込んでしまうのはどうでしょうね。どちらもCプログラムに埋め込み易く書かれていますし、元来は汎用のスクリプティング言語ですから、アプリケーションにマクロ言語機能も付けられるというおまけがあってお得な感じです。アプリケーションのマクロ言語としてはRubyは最高と思うのですが、如何せん、現Ruby実装
クヌース氏も認めたアルゴリズム「ZDD」でスマートグリッドを実現、北大・湊教授らが開発
科学技術振興機構（JST）、北海道大学、早稲田大学は2012年2月23日、北海道大学大学院情報科学研究科の湊真一教授らのグループが、電力の配電網における送電ロスを最小化する技術を開発したと発表した。湊教授が考案した「ゼロサプレス型二分決定グラフ（ZDD）」というアルゴリズムを、配電網の最適化計算に適用した。モデル上の検証では、配電網における電力ロスを3％削減できたとしている。 湊教授が1993年に考案したZDDは、米スタンフォード大学のドナルド・クヌース名誉教授の著書「The Art of Computer Programming」において、日本人が考案したアルゴリズムとしては初めて、独立項目として解説されたことで知られている。これまでZDDは、LSI設計において、回路の構成を最適化する計算などに使われていた。そのZDDを配電網の経路最適化に用いたのが、今回の発表のポイントである。 電力の
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Raft:Understandable Distributed Consensus
Verified Functional Algorithms
Grokking Algorithms Is Out - adit.io
Chromeのなかのコンピュータ・サイエンス
最適化超入門
あなたの知らないハッシュテーブルの世界