Bloom Filters
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. 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 goin
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
上に示した2つの図は、対数スケールの上にプロットした2つの確率分布である[注 1]。どちらの図でも、赤で示した部分の面積が最初の桁が1である確率に比例しており、青で示した部分の面積が最初の桁が8である確率に比例している。 左側の分布では、赤と青の領域の面積比はおおよそそれぞれの幅の比に等しくなっている。幅の比は普遍的で、ベンフォードの法則によって厳密に与えられる。したがって、こうした確率分布に従う数値はおおむねベンフォードの法則に従う。 一方、右の分布では、赤と青の領域の面積比はその幅の比から大きく外れている。右の図でも幅の比は左側の分布と同じになっている。赤と青の領域の面積比は、その幅よりもむしろ高さの比に依存して決定されている。幅と異なり高さはベンフォードの法則に普遍的な関係を満たさない。代わりにその数値の分布の形によって完全に決定される。したがって、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] 法にも技術にも詳しくない一般の人がそう思うのは自然なことでしょう。オンライン投票ができれば、少なくとも若年層の投票率にはいい影響がありそうです。しかし「現代的で民主的な選挙」の要件をしっかり満たしてオンライン投票を実現するのは、実は技術的にも容易ではありません。 「現代的で民主的な選挙」の要件とは、どういうものでしょうか。現在の技術でオンライン投票を実施すると、その要件はどのように毀損するのでしょうか。私たちはその要件を、本当に理解しているでしょうか。 本記事は、「現代的で民主的な選挙」の要件を振り返り、そこから導かれる「オンライン投票のなにが『難しい』のか」をできるだけ明確にする試みです。そして、議論をその先へ進めるための前
Scope Graphs | A Theory of Name Resolution
Names are crucial for organizing and understanding programs. Yet names and name binding get a second class treatment in programming language definition. We have a fairly standardized approach based on context-free grammars to provide tool independent descriptions of the syntax of programming languages. There is no analog for describing the name binding rules of programming languages. It is hard to
"Incremental, zero-config Code Nav using stack graphs" by Douglas Creager
Exploring a large or unfamiliar codebase can be tricky. Code Navigation features like “jump to definition” and “find all references” let you discover how different pieces of code relate to each other. To power these features, we need to extract lists of symbols from the code, and describe the language-specific rules for how those symbols relate to each other. It’s difficult to add Code Nav to a l
クックパッドマートの配送ルートを自動生成している仕組み - クックパッド開発者ブログ
こんにちは、クックパッドマート流通基盤アプリケーション開発グループのオサ（@s_osa_）です。 生鮮食品の EC サービスであるクックパッドマートでは、「1品から送料無料」をはじめとするサービスの特徴を実現するために、商品の流通網を自分たちでつくっています。 このエントリでは、商品をユーザーに届けるための配送ルートを自動生成している仕組みについて紹介します。 解決したい問題 配送ルートとは クックパッドマートにはいくつかの流通方法がありますが、ここでは「ステーション便」と呼ばれるものについて解説します。他の流通方法などを含む全体像が気になる方は以下のエントリがオススメです。 クックパッド生鮮 EC お届けの裏側 2022 年版 - クックパッド開発者ブログ ステーション便では、ハブと呼ばれる流通拠点からユーザーが商品を受け取りに行く場所であるステーションへと商品を運びます。東京都、神奈川
How to recognize the compression algorithms with your eyes - ZenHAX
online casino malaysia online casino singapore[phpBB Debug] PHP Warning: in file [ROOT]/phpbb/session.php on line 1065: Cannot modify header information - headers already sent by (output started at [ROOT]/vendor/autoload.php:3) [phpBB Debug] PHP Warning: in file [ROOT]/phpbb/session.php on line 1065: Cannot modify header information - headers already sent by (output started at [ROOT]/vendor/autolo
高速な文字列探索：Daachorseの技術解説 - LegalOn Technologies Engineering Blog
こんにちは。LegalForce Researchで研究員をしている神田 (@kampersanda) です。 LegalForce Researchでは現在、高速なパターンマッチングマシン Daachorse（ダークホース）を開発・運用しています。文字列処理の基礎である複数パターン検索を提供するRust製ライブラリです。以下のレポジトリで公開されています。 github.com 本記事はDaachorseの技術仕様を解説します。具体的には、 複数パターン検索に関係する基礎技術（トライ木・Aho–Corasick法・ダブル配列） Daachorseの実装の工夫と性能 を解説します。 以下のような方を読者として想定します。 文字列処理アルゴリズムやデータ構造に興味のある方 自然言語処理の要素技術に興味のある方 Rustライブラリに興味がある方 Daachorseについて 複数パターン検索の基
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Adjacency list optimizations by lettertwo · Pull Request #9444 · parcel-bundler/parcel
What do I think about Community Notes?
https://www.diva-portal.org/smash/get/diva2:1302887/FULLTEXT01.pdf
GitHub - uuid6/uuid6-ietf-draft: Next Generation UUID Formats
