Operational transformation - Wikipedia
"Operation Transformation" redirects here. For the cross-media event, see Operation Transformation (TV series). Operational transformation (OT) is a technology for supporting a range of collaboration functionalities in advanced collaborative software systems. OT was originally invented for consistency maintenance and concurrency control in collaborative editing of plain text documents. Its capabil
RustでCRDTを使ったリアルタイム共同編集機能を作ってみる話
メモ代わりにZennに記事を書いているせいで、下書きが積まれまくっているmasamikiです。 はじめに FigmaとかかMiroとかゲームならマインクラフトとか共同編集を機能としてもっているものは世にいろいろありますが、共同で編集することの需要が今後も増えていきそうないかなさそうな、P2Pの世界も広がっていきそうないかなさそうな気がするので、「共同編集」もっと詳しく知っておかないとなと、そのあたりを書いてみました。 （わかりやすく説明するのがとても難しい………） 変なとこがあればコメントください。追記や修正していきます。 リアルタイム共同編集の仕組み マルチプレイヤーな仕組みを検討する時に考えなければいけない、データのコンフリクトです。 同じものを同じタイミングで編集した場合どうなるの…？ 後勝ち（Last-writer-wins）にしちゃえば？ 編集したものを、他の人が編集してしまった
How Figma’s multiplayer technology works | Figma Blog
in Figma four years ago, we decided to develop our own solution. No other design tool offered this feature, and we didn’t want to use operational transforms (a.k.a. OTs), the standard multiplayer algorithm popularized by apps like Google Docs. As a startup we value the ability to ship features quickly, and OTs were unnecessarily complex for our problem space. So we built a custom multiplayer syste
A comprehensive study of Convergent and Commutative Replicated Data Types
HAL Id: inria-00555588 https://inria.hal.science/inria-00555588v1 Submitted on 13 Jan 2011 HAL is a multi-disciplinary open access archive for the deposit and dissemination of sci- entific research documents, whether they are pub- lished or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridis
CRDT (Conflict-free Replicated Data Type)を15分で説明してみる - Qiita
下記はスライドの講演の書き下しのようになっているので、スライドだけ見るんじゃなくて、スライドを見ながら文章を読み進めたい方向けです。 CRDTとは 今回は、CRDTというデータ構造について紹介します。CRDTはそもそも2011年にSSS(Stabilization, Safety, and Security of Distributed Systems)という国際会議で、INRIA(フランス国立情報学自動制御研究所)のMarc Shapiro博士によって発表された、比較的新しいモノです。 CRDTは"Conflict-free Replicated Data Type"の略で、日本語で言うと、__コンフリクトしない複製可能なデータ__といった感じです。 CRDTには実現方法によって２種類の呼び方が存在します(それぞれの略もまたCRDTなのでややこしいですが)。 Commutative Re
Move Over Dijkstra: The New Algorithm That Just Rewrote 70 Years of Computer Science
For nearly seven decades, Dijkstra’s algorithm has reigned supreme as the gold standard for finding shortest paths in graphs. Born from a 20-minute mental exercise at an Amsterdam café in 1956, Edsger Dijkstra’s creation has been the backbone of everything from GPS navigation to network routing protocols. But that reign just ended. A research team led by Ran Duan at Tsinghua University has achieve
【#も読】n月刊ラムダノート、実用Raft（@yusuktan）
「あの人も読んでる」略して「も読」。さまざまな寄稿者が最近気になった情報や話題をシェアする企画です。他のテックな人たちがどんな情報を追っているのか、ちょっと覗いてみませんか？ みなさんこんにちは。 この度「あの人も読んでる」に寄稿させていただくことになったmaguro (X @yusuktan)です。 僕が読んで面白かった本、記事、動画などのコンテンツを定期的にご紹介していければと思います。よろしくお願いします。 今回紹介するコンテンツ記念すべき第1回目にぜひ紹介したいのが、2025年3月1日に発売されたばかりのラムダノート社「n月刊ラムダノート Vol.5, No.1(2025)」です。ラムダノート社が不定期で発行している技術解説情報誌で、今号は以下の3本の記事が掲載されています。 自然数を作って学ぶLean言語（井上亜星 著） Chromiumはテキストをどのように描画しているのか（佐
malloc.c を読む (malloc / free)
このシリーズではこれらの関数が内部でどのように処理されるのかを調べていきます。 malloc.c を読む (malloc / free) malloc.c を読む (bins) malloc.c を読む (arena) 今回は malloc() free() の全体像を紹介します。 注意としてここでの目的は全体を俯瞰して、詳細を詰めずとも各 bins の役割を理解し、攻撃手法を理解できるようにすることです。それに合わないマルチスレッドや最適化などにおける緻密なトリックやコーナーケースなどは暗黙的に実装されていると仮定します。その詳細についてはソースコードや他の資料を参考にしていただきたいです。 ここで扱う glibc のバージョンは v2.38 です。また glibc のソースコードはブラウザ上で読むことができます。 https://elixir.bootlin.com/glibc/lat
Why UUID7 is better than UUID4 as clustered index in RDBMS
In the Introduction To Database Indexing Article, We discussed database indexes, Their type, representations, and use cases. In this article, we will experiment to check which performs better as a clustered index. UUID version 4 vs UUID version 7 or 6. Then we will discuss why that happened. What is UUID version 4?UUID, an acronym for Universally Unique Identifier, is a 128-bit identifier represen
Othello is Solved 論文解説 (私見) - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 今朝起きたら、とんでもない論文を見つけました。 Othello is Solved ゲームの オセロが"解かれた(弱解決)" というのです。飛び起きました。それで、16時まで二度寝してから読みました。 注意すべきは、この論文が査読を経て公開されているわけではないこと、つまり形式上特にチェックを受けたものではないことです。ただ、タイトルからして非常に衝撃的ですので、個人的に読んでみました。この記事では、私がこの論文(およびソースコード)を読んでわかったことを、なるべくわかりやすくまとめます。随時更新します。 余談ですが、このタイトルはどう
徐々に高度になるリングバッファの話 - Software Transactional Memo
リングバッファのイメージ図 1. リングバッファとは何か 機能的にはFirst In First Out (FIFO)とも呼ばれるキューの一種であるが、リング状にバッファを置いてそれの中でReadとWriteのインデックスがグルグルと回る構造をとる事によって容量に上限ができることと引き換えに高速な読み書き速度を得たものである。キューを単に実装するだけなら山ほど方法があって線形リストを使ってもいいしスタックを2つ使っても原理的には可能だ。その中でもリングバッファを用いた方法の利点はひとえに性能の高さでありメモリ確保などを行わないお陰でシステム系の様々な場所で使われている。 これの実装自体は情報系の大学生の演習レベルの難度であるが少し奥が深い。まずリングバッファのスタンダードなインタフェースと実装は以下のようなものである。 class RingBuffer { public: explicit
Algorithm Design with Haskellでアルゴリズムを学ぶ - 朝日ネット 技術者ブログ
はじめに 開発部のcbmkageです。 仕事でプログラムを書いていると、どうしたら期待通りに、かつ高速に動作するアルゴリズムが実装できるか、考えることがあります。 本記事では、アルゴリズムについて新たな視点を与えてくれる本「Algorithm Design with Haskell」を紹介します。 本記事はHaskell中級者向けです。Haskellの文法や、代表的なリスト操作関数を知っていることを前提としています。 はじめに Algorithm Design with Haskellとは 準備: 関数の同値関係 貪欲アルゴリズムのPART紹介 貪欲アルゴリズムとは 候補の生成と選択 貪欲アルゴリズムへの改善 まとめ 採用情報 Algorithm Design with Haskellとは Algorithm Design with Haskell 作者:Bird, Richard,Gib
試し割りによる素数列挙はエラトステネスの篩か？ - Qiita
背景 前回の記事 IchigoJamでエラトステネスの篩 - Qiita を受け、ツイート主さんから以下のページのURLが送られてきました。 エラトステネスの篩 [WildTree Wiki] 見ると、それぞれの奇数$T$について、$\sqrt{T}$以下の素数で割っていき、 全て割り切れなければ$T$は素数であると判定するアルゴリズムを使っているようです。 一方、エラトステネスの篩といえば、 確定した最小の素数の倍数を候補から外し、確定していない中で最小の候補を素数として確定させる、 という処理を繰り返すことで、効率よく素数のリストを求めることができるアルゴリズムのはずです。 今回送られたページにあるような、1個ずつ試し割りを行うアルゴリズムは、 果たしてエラトステネスの篩といえるのでしょうか？ そこで、試し割りと一般的なエラトステネスの篩の時間コストを比較してみることにしました。 今回
世界四連覇AIエンジニアがゼロから教えるゲーム木探索入門 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? はじめに 書籍化 本記事を元に ゲームで学ぶ探索アルゴリズム実践入門～木探索とメタヒューリスティクス という書籍を出版することになりました！ 本記事を読んで気になっていただけたらご購入をご検討いただけるとうれしいです！ この記事で得られる技術 ゲームルールに適した探索アルゴリズムを選択する ゲーム木探索をするのに適したクラス設計 主要なゲーム木探索アルゴリズムの実装 この記事の特徴 汎用アルゴリズムの実装例による他ゲームへの応用力と、実際に動作可能なサンプルコードによる具体的実装イメージの両視点でわかりやすくした（片方しか記載のない記事
リアルタイム共同編集のアルゴリズム (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（文書を編集する側です） そ
情報基礎特論: 制約プログラミング入門
CSP Cream Sugar Copris : 2011 6 6 2011 8 22 2012 6 24 2014 5 19 : CSP Cream Sugar Copris 1 2 3 Cream Java OpenOffice.org Calc 4 Sugar SAT Scala : CSP Cream Sugar Copris : CSP Cream Sugar Copris (CSP) (CSP; Constraint Satisfaction Problem) (X, D, C) X: (variable) D: x ∈ X (domain) ( : D(x) = {1, 2, 3}) D(x) C: X (constraint) X v x v(x) ∈ D(x) v (assignment) v C (satisfy) CSP (satisfiable) v (unsatisfia
クックパッドマートの配送ルートを自動生成している仕組み - クックパッド開発者ブログ
こんにちは、クックパッドマート流通基盤アプリケーション開発グループのオサ（@s_osa_）です。 生鮮食品の EC サービスであるクックパッドマートでは、「1品から送料無料」をはじめとするサービスの特徴を実現するために、商品の流通網を自分たちでつくっています。 このエントリでは、商品をユーザーに届けるための配送ルートを自動生成している仕組みについて紹介します。 解決したい問題 配送ルートとは クックパッドマートにはいくつかの流通方法がありますが、ここでは「ステーション便」と呼ばれるものについて解説します。他の流通方法などを含む全体像が気になる方は以下のエントリがオススメです。 クックパッド生鮮 EC お届けの裏側 2022 年版 - クックパッド開発者ブログ ステーション便では、ハブと呼ばれる流通拠点からユーザーが商品を受け取りに行く場所であるステーションへと商品を運びます。東京都、神奈川
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Dijkstra’s 70-Year Reign Ends: The Fastest Shortest Path Algorithm Revealed
Constraint Propagation and Backtracking-based Search
M-Coloring Problem - GeeksforGeeks