共同編集を支える技術とライブラリの活用 - ICS MEDIA
『Google Docs』や『Figma』といったリアルタイムな共同編集ツールの恩恵を受けている人は数多くいるでしょう。『Visual Studio Live Share』のようなエンジニアに嬉しいツールも生まれ、今日ではオンライン上でも円滑なコミュニケーションが可能になっています。 これらのツールの基礎にあるのが「共同編集」のテクノロジーです。本記事ではこの技術に焦点を当て、その仕組みと主にフロントエンドでの実用例について紹介します。 記事の前半では、リアルタイムな共同編集に用いられる技術やアルゴリズムについて、発展の歴史とあわせて紹介します。解説用のコードにはJavaScriptおよびTypeScriptを使用しますが、フロントエンドエンジニアに限らず共同編集の仕組みについて気になる読者が知識を深めるきっかけとなるはずです。 さらに後半ではフロントエンドの開発者目線で、前半で紹介した技
整数を可逆スクランブルする - C Sharpens you up
2年前につぶやいた内容の詳しい説明。 32ビット整数をとりあえずスクランブルするすごく簡単な方法に気付いてしまった。なにか奇数をかけると、それにかければ元の数に戻るような奇数が必ずひとつあるから、それを力任せで見つけてしまえばいいんだ。ビット回転→奇数をかけるを3回繰り返すとほぼバラバラ。— ゆば大好き (@yuba) October 18, 2011 整数を、暗号ライブラリ使うほどじゃないんだけどスクランブルしたいことってあるんですよね。たとえば、IDを連番で振ってるんだけど連番だってことがユーザーにわかってしまうと具合が悪いとか。そういうときの簡単なスクランブル方法です。ただし、符号なし整数でしか使えないのでこの時点でJavaは対象外ごめんなさい。 まず32ビット整数版のC,C++,C#で動くコードです。 uint Scramble(uint v) { // 奇数その1の乗算 v *=
Bing検索の裏側―BitFunnelのアルゴリズム - Hatena Developer Blog
はてなアプリケーションエンジニアの id:takuya-a です。 この記事では、Microsoft の検索エンジン Bing で採用された BitFunnel アルゴリズムを紹介します。 昨年のエンジニアアドベントカレンダーでは、文字列検索のアルゴリズム全般について紹介しました（文字列アルゴリズムの学びかた - Hatena Developer Blog）。今年はそのなかでも、インデックス（索引）を使った全文検索アルゴリズムについてのお話になります。 この記事の前半は全文検索の入門にもなっていますので、検索技術になじみがない方にも楽しんでいただけるのではないでしょうか。 逆に、「そんなのもう知ってるよ！」という方は、本題である「BitFunnel アルゴリズムの詳細」から目を通していただければと思います。 この記事は、はてなエンジニア Advent Calendar 2017の21日目の
3-way mergeについて調べた - Qiita
今更過ぎるが3-way mergeについて勉強。 結論 2-wayだと片方に削除がある場合、もう片方が追加したとみなされる 適切にマージできなかった場合、削除した機能が残っている。という事態になってしまう 3-wayだと元のファイルがあるため、それぞれの差分がわかり、自動マージでも2-wayのような事態は発生しづらい サンプル データベースに管理者を登録するシステムがあったとする。 (コードはほんっとうに適当) マネージャから自分には管理者以外のユーザも利用できるように認証機能を外すよう依頼された。 同僚には名前とパスワードの重複を防ぐ事を依頼された。 今まで older.rb require 'database' data = Database.new puts "are you admin? [y/N]" unless gets.chomp == 'y' puts "canceled"
DAG (Directed acyclic graph) - 有向非巡回グラフ - なべ’s blog
先日、JJUG CCC 2015 Fallに参加して、灰色のサイトで有名なひしだまさん（ひしだま (@hishidama) | Twitter）の「GH-6 Java8 Stream APIとApache SparkとAsakusa Frameworkの類似点・相違点」を聞いた際に出てきた「DAG (Directed acyclic graph) - 有向非巡回グラフ」が面白そうだったので調べてみた。 DAGとは Wikiによると、 グラフ理論における閉路のない有向グラフの事。 有向グラフは頂点と有向辺（方向を示す矢印付きの辺）からなり、辺は頂点同士をつなぐが、ある頂点 v から出発し、辺をたどり、頂点 v に戻ってこないのが有向非巡回グラフである。 wikipedia:有向非巡回グラフ となっている。 DAGの例 Wikiの例はわかりづらいので、JJUG CCC 2015 Fallのひし
編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー
昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿入/削除/置換で一方を他方に変形するための最小手順回数を数えたものが編集距離です。 例えば 伊藤直哉と伊藤直也 … 編集距離 1 伊藤直と伊藤直也 … 編集距離 1 佐藤直哉と伊藤直也 … 編集距離 2 佐藤B作と伊藤直也 … 編集距離 3 という具合です。 編集距離はスペルミスを修正するプログラムや、近似文字列照合 (検索対象の文書から入力文字にある程度近い部分文字列を探し出す全文検索) などで利用されます。 編集距離算出は動的計画法 (Dynamic Programming, DP) で計算することができることが
Damerau-Levenshteinは並べ替え機能付き : mwSoft blog
先日、レーベンシュタイン距離のコードを見ていて思ったのだけど、この手法には1つもの足りない点がありました。 例えば以下の2つの文字を比べた場合です。 あした あたし 2つ目のポジションの「し」を削除し、3つ目のポジションに「た」を挿入するという2回のアクションで文字列を一致させられます。 これは、以下の文字列を比べた場合と同じコストです。 あした あたい 1つ目のパターンの方は、3つとも全て同じ文字が使われているというのに、文字列の近さは同じと判定されてしまうわけです。 レーベンシュタイン距離は「挿入」「削除」「置換」の3パターンしかサポートしていません。 これを解決するには「し」と「た」を「並べ替える」という処理が必要になります。 この処理を追加サポートしているのが、「Damerau-Levenshtein」（カタカナ表記ではなんと書けばいいのだろう）。並べ替え処理は、英語版Wikipe
#JJUG - Java で最速のハッシュアルゴリズムを求めて
【東京】【聴講者募集】JJUG ナイト・セミナー 「ビール片手にLT&納涼会」の発表資料です。 https://jjug.doorkeeper.jp/events/28182
トークンバケット - Wikipedia
トークンバケット（英: token bucket）とは、ネットワークへのデータ流入量を制御するアルゴリズムの一種であり、バースト性のあるデータ送信を許容する。いくつかの用途があるがトラフィックシェーピングの手法として使うことが多い。 なお、バケット (bucket) とは、バケツのことであり、転送すべきネットワークトラフィックを集積する抽象化されたコンテナである（実装は例えばバッファやキュー）。 トラフィックシェーピングでは、トークンバケットのほかにリーキーバケットも使われる。この2つは誤って混同されやすい。これらは性質も異なり、目的も異なる[1]。大きな違いは、リーキーバケットがデータ転送レートの上限を設定するのに対して、トークンバケットはデータ転送レートの平均に制限を課して、ある程度のバースト性を許容する。 トークンバケットは、バケット内のトークンの存在に基づいてトラフィックの転送をい
UUID と Perl について - daily dayflower
UUID がどういうものであるか，とか UUID の表現形については省略します。 UUID - Wikipedia が参考になるかと。 UUID の仕様として RFC 4122 を参照しました*1。なのでより細かいことについては原文を参照してください。策定されるまでにいろいろ経緯があるのですが，そのへんは http://www.rfcnews.jp/archives/2005/07/rfc_4122uuidurn.html に譲ります。 UUID の構造 UUID の内部構造をおおまかに表すと以下のようになります。 variant 2 bit (3 bit) version 4 bit time 60 bit clock_seq 14 bit (13 bit) node 48 bit 実際には variant フィールドは clock_seq フィールドのオクテットの中に埋め込まれています
Which hashing algorithm is best for uniqueness and speed? - Software Engineering Stack Exchange
Which hashing algorithm is best for uniqueness and speed? Example (good) uses include hash dictionaries. I know there are things like SHA-256 and such, but these algorithms are designed to be secure, which usually means they are slower than algorithms that are less unique. I want a hash algorithm designed to be fast, yet remain fairly unique to avoid collisions.
データ分散とインデックス最適化のためのハッシュ関数の利用 - Articles Advent Calendar 2011 Hacker
はじめに こんにちは、piarra です。みなさん、意識は高まっていますか？私は上々です。 という書き出しをやめたくてやめられなかったのが心残りです。 昨年までは、Casual Trackで寄稿させていただいていましたが、今年はYAPCで話したこともあり、Hacker Trackに初挑戦させていただきます。得意のMD5暗算法とその習得法について解説したいと思っていたところですが、より日常に役立つ方がよいかと思い、MD5やその他のハッシュ関数の活用法について少し触れてみたいと思います。 データサンプル DBMSを考慮せず、以下のようなデータサンプルがあったと考えてみましょう。 +----+-----------------------+ | id | url | +----+-----------------------+ | 1 | http://www.google.com | | 2
軽量ハッシュアルゴリズム - Qiita
今回はハッシュアルゴリズムについて少し触れてみたいと思います。 既存のハッシュアルゴリズムはどういうものがあるでしょうか？ SHA-1, MD5等が浮かんだ方も多いと思います。 「じゃあそれでいいじゃん」 ・・・ちょっと待ってください。 SHA-1, MD5というものは、暗号化のためのハッシュアルゴリズムです。 もし用途が単純なファイル比較等であれば、ここまで大げさなハッシュは冗長で高負荷低速であると言えます。 適切なアルゴリズムは状況によって適切に選びたいところです。 そこで今回は単純なファイル比較等に使用できる、簡単＆軽量なハッシュアルゴリズムの FNV-1 というアルゴリズムを紹介します。 詳細はこちらへどうぞ http://wowdev.jp/?p=873 ソースはこちらです。 # include <stdio.h> # include <stdint.h> /** * FNV C
algorithm - 最近点検索をkd-treeで : 404 Blog Not Found
2009年04月30日01:00 カテゴリMathLightweight Languages algorithm - 最近点検索をkd-treeで というわけで、kd-treeによる検索も実装してみました。 はてなブックマーク - ototoiのブックマーク データ数が少ない場合、この全検索が高速。ただデータが多くなってくるとkd-treeがいいと思う。点ならば配列をソートするだけで実現できる。 以下のデモでは、単にkd-treeによる検索だけではなく、kd-tree構築の速度と、総当たりの場合の速度の比較もできるようにしてあります。10,000点ぐらいだと、その差を顕著に感じることが出来るでしょう。100,000点ぐらいあると、感動的なほど差が出ます。それだけあってもkd-treeの方はほぼ1ms以内に検索が終わるのですから(ただしこの場合、デモの実行に合計10秒以上かかるので注意!)。
ConsistentHashing - コンシステント・ハッシュ法
ConsistentHashing - コンシステント・ハッシュ法 目次 この文書について コンシステント・ハッシュ法 実例 実装 用途 コンシステント・ハッシュ法 この文書について "Tom White's Blog: Consistent Hashing" の日本語訳です. http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html 推敲歓迎: 誤訳, タイポ, 訳語の不統一, そのほか... 原文のライセンス: http://creativecommons.org/licenses/by-nc-sa/2.0/ 私は今までに何度かコンシステント・ハッシュ法にとりくんだことがある。 このアイデアをあらわした論文 ( David Karger らによる Consistent Hashing and R
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
