Collaborative Text Editing with Eg-walker: Better, Faster, Smaller
Collaborative text editing algorithms allow several users to concurrently modify a text file, and automatically merge concurrent edits into a consistent state. Existing algorithms fall in two categories: Operational Transformation (OT) algorithms are slow to merge files that have diverged substantially due to offline editing; CRDTs are slow to load and consume a lot of memory. We introduce Eg-walk
「秘密計算を用いたデータ利活用実践のためのガイドライン」中間報告文書を公開
NTTコミュニケーションズ株式会社 国立研究開発法人産業技術総合研究所 株式会社野村総合研究所 NRIセキュアテクノロジーズ株式会社 GMOサイバーセキュリティ byイエラエ株式会社 NTTコミュニケーションズ株式会社(以下 NTT Com)、国立研究開発法人産業技術総合研究所(以下産総研)、株式会社野村総合研究所(以下NRI)、NRIセキュアテクノロジーズ株式会社(以下NRIセキュア)、GMOサイバーセキュリティ byイエラエ株式会社(以下GMOサイバーセキュリティ byイエラエ)、は、さまざまなデータの安全な流通・利活用に貢献できる秘密計算の普及促進に向けて、秘密計算を扱うプロジェクトの立ち上げや、セキュアなデータ管理の実現における指針を示す「秘密計算を用いたデータ利活用実践のためのガイドライン」(以下 本ガイドライン)の中間報告文書を2025年3月26日に公開します。 1.背景 秘密
Hacking the JavaScript Lottery
January 2016 boasted a Powerball jackpot of 1.5 billion dollars. This generated a lot of interest in the lottery and the Los Angeles Times released a simulator where you start with 100 dollars and play until that is gone. I had seen previous work for predicting Java’s Math.random() and thought it would be a fun project to replicate for the browser. The first step is to find the algorithm used in t
How Unix Spell Ran in 64kB RAM
How do you fit a 250kB dictionary in 64kB of RAM and still perform fast lookups? For reference, even with modern compression techniques like gzip -9, you can't compress this file below 85kB. In the 1970s, Douglas McIlroy faced this exact challenge while implementing the spell checker for Unix at AT&T. The constraints of the PDP-11 computer meant the entire dictionary needed to fit in just 64kB of
JavaScriptによるはじめてのアルゴリズム入門 | 技術評論社
概要 「アルゴリズム入門」シリーズのJavaScript対応版です。アルゴリズムは、プログラムを効率的かつ正確に実行するための重要な要素です。プログラミング技術を上達させるためには、系統的に異なるさまざまな視点でのアルゴリズム学習が効果的です。本書ではJavaScriptを用いて基本的なアルゴリズムの概念と実装方法を学び、プログラムの流れを制御するための方法を理解していきます。学習には、Webベースの開発環境“p5.jsWebエディタ”を使います。Webブラウザから掲載プログラムを入力して、すぐに動作を確認することができます。 目次 第1章 ウォーミング・アップ 1-0 アルゴリズムとは 1-1 漸化式 1-2 写像 1-3 順位付け 1-4 ランダムな順列 1-5 モンテカルロ法 1-6 ユークリッドの互除法 1-7 エラトステネスのふるい 第2章 数値計算 2-0 数値計算とは 2-1
Bloom Filters
2024-02-19 Everyone has a set of tools they use to solve problems. Growing this set helps you to solve ever more difficult problems. In this post, I'm going to teach you about a tool you may not have heard of before. It's a niche tool that won't apply to many problems, but when it does you'll find it invaluable. It's called a "bloom filter." Before you continue! This post assumes you know what a h
Hashing
This page makes heavy use of JavaScript to visualise the concepts discussed. Viewing it without JavaScript will be a strange experience, as the text talks about the visualisations. I strongly recommend either enabling JavaScript, or not wasting your time. As a programmer, you use hash functions every day. They're used in databases to optimise queries, they're used in data structures to make things
Load is not what you should balance: Introducing Prequal
We present Prequal (Probing to Reduce Queuing and Latency), a load balancer for distributed multi-tenant systems. Prequal aims to minimize real-time request latency in the presence of heterogeneous server capacities and non-uniform, time-varying antagonist load. It actively probes server load to leverage the power-of-d-choices paradigm, extending it with asynchronous and reusable probes. Cutting a
Hash-flooding DoS と SipHash - あどけない話
以前、僕が実装している web サーバ Mighty が、Haskell で書いているにも関わらず、セグメンテーションフォールトを起こしていた。調べたところ hashable ライブラリがリンクする C の DJBX33X が、SipHash に変わったことが原因だった。このときから SipHash が気になっていたし、以前社内で説明した "Efficient Denial of Service Attacks" との関係も知りたかったので、少し調べてみた。この記事は、その覚え書き。 Hash-flooding DoS の歴史 1998 年に Alexander Peslyak 氏が Phrack Magazine で、Hash-flooding DoS を受けたことを報告している。ハッシュは、N 個の要素を挿入するのに通常 O(N) かかるが、ハッシュ値がすべて衝突する最悪の場合では O
ベンフォードの法則 - ｛ 適用と制限 ｝Wikipedia
対数スケールのグラフ、この数直線上にランダムに点を取ると、その地点が表す数値の最初の桁が1になる確率がおおよそ30 パーセントである。 ベンフォードの法則（ベンフォードのほうそく、Benford's law）とは、自然界に出てくる多くの（全てのではない）数値の最初の桁の分布が、一様ではなく、ある特定の分布になっている、という法則である。 この法則によれば、最初の桁が1である確率はほぼ3分の1にも達し、大きな数値ほど最初の桁に現れる確率は小さくなり、9になると最初の桁に現れる確率は20分の1よりも小さくなる。数理的には、数値が対数的に分布しているときは常に最初の桁の数値がこのような分布で出現する。以下に示したような理由により、自然界での測定結果はしばしば対数的に分布する。別の言い方でいえば、対数的な測定結果があらゆる場所に存在する。 この直感に反するような結果は、電気料金の請求書、住所の番地
テキストエディタで使われがちなデータ構造 Piece Table の概要と実装 - A Memorandum
テキストエディタのデータ構造 Gap method Piece Table method Piece Table の構造 Piece Table の実装 Piece Table のメソッド まとめ テキストエディタのデータ構造 テキストエディタで採用されているデータ構造にはいろいろあります。 こちらの論文 Data Structures for Text Sequences では各種データ構造について比較検討されています。 多くは、Gap method や Piece table method をベースにしたものが多いのではないでしょうか(図で言う最下部の中心の丸印に当たります)。最近では Rope なども有名ですね。 Gap method Gap method では、現在のカーソル位置で、テキストバッファを2つに分割し Gap を間に挟み、カーソル位置に対する編集(テキスト追加/削除)を
Object Tracking State of the Art 2022
Learn about the current SOTA like ByteTrack, DeepSORT, StrongSORT and OC-SORT First, an introduction will be made to the key metrics used in literature to compare different trackers; after this introduction, a discussion on the SOTA algorithms of object tracking will be conducted. Object detection tries to answer the question: “ What objects are in this image and where are they? Object Tracking an
共同編集を支える技術とライブラリの活用 - ICS MEDIA
『Google Docs』や『Figma』といったリアルタイムな共同編集ツールの恩恵を受けている人は数多くいるでしょう。『Visual Studio Live Share』のようなエンジニアに嬉しいツールも生まれ、今日ではオンライン上でも円滑なコミュニケーションが可能になっています。 これらのツールの基礎にあるのが「共同編集」のテクノロジーです。本記事ではこの技術に焦点を当て、その仕組みと主にフロントエンドでの実用例について紹介します。 記事の前半では、リアルタイムな共同編集に用いられる技術やアルゴリズムについて、発展の歴史とあわせて紹介します。解説用のコードにはJavaScriptおよびTypeScriptを使用しますが、フロントエンドエンジニアに限らず共同編集の仕組みについて気になる読者が知識を深めるきっかけとなるはずです。 さらに後半ではフロントエンドの開発者目線で、前半で紹介した技
リアルタイム共同編集のアルゴリズム (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（文書を編集する側です） そ
60 LeetCode questions to prepare for coding interview
I recently received a job offer from one of FAANG. Here are some problems to help me pass the coding interview. Categories are LinkedListStackHeap, PriorityQueueHashMapGraph, BFS, DFSTree, BT, BSTSortDynamic ProgrammingBinary searchRecursionSliding windowGreedy + BacktrackingIf you can solve them quickly, you would have a high chance to pass coding interview. Problems are either Easy or Medium. I
オンライン投票はなぜ『難しい』のか
日本で公職選挙が近づいてくると、「202X 年にもなって投票所に行く必要があるなんて」とか「オンライン投票もいまだにできないなんて」みたいな声をよく聞きます。 [1] 法にも技術にも詳しくない一般の人がそう思うのは自然なことでしょう。オンライン投票ができれば、少なくとも若年層の投票率にはいい影響があるかもしれません。しかし「現代的で民主的な選挙」の要件をしっかり満たしてオンライン投票を実現するのは、実は技術的にも容易ではありません。 「現代的で民主的な選挙」の要件とは、どういうものでしょうか。現在の技術でオンライン投票を実施すると、その要件はどのように毀損するのでしょうか。私たちはその要件を、本当に理解しているでしょうか。 本記事は、「現代的で民主的な選挙」の要件を振り返り、そこから導かれる「オンライン投票のなにが『難しい』のか」をできるだけ明確にする試みです。そして、議論をその先へ進める
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - microsoft/bf-tree: Bf-Tree is a modern read-write-optimized concurrent larger-than-memory range index in Rust from MS Research.
Robust-first computing: Demon Horde Sort (full version)
Adjacency list optimizations by lettertwo · Pull Request #9444 · parcel-bundler/parcel
What do I think about Community Notes?