確率的データ構造の比較：カッコウフィルタ対ブルームフィルタ | POSTD
確率的データ構造は少ないメモリでデータをコンパクトに保存し、保存されたデータに関するクエリに対し、おおよその答えを提供してくれます。クエリに対し空間効率の良い方法で答えるように設計されており、それはつまり、正確さを犠牲にするということにもなります。しかし、これらは一般的に、問われているデータ構造の仕様にもよりますが、誤差率の保証と境界を提供してくれます。メモリ使用量が少ないため、確率的データ構造はストリーミングや低出力の設定に特に有用なのです。ですから、動画の視聴回数を数えたり、過去に投稿された一意となるツイートのリストを維持したりするなど、ビッグデータの環境下では非常に有用です。例えば、 HyperLogLog++ 構造 は、2.56KBのメモリで最大790億の一意のアイテムを数えることができるのですが、誤差率はわずか1.65パーセントです。 Fast Forward Labsのチームは
分散合意アルゴリズム Raft を理解する - Qiita
概要 Raft は安全な ステートマシンレプリケーション (SMR; State Machine Replication) を実装するための分散合意アルゴリズム。分散システムにおいて一貫性 (分散トランザクション) と可用性 (障害耐性) を実装するための基本的な部品として使用することができる。 分散システムにおける合意 (Consensus) とは、参加しているすべてのノードが最終的に同じ値を採用すること (≒ 同じ状態になること) を意味します。このため、合意アルゴリズムは一貫性のあるレプリケーションを実現するために利用されます。 TL;DR Raft は強い一貫性のレプリケーションや分散実行を行うことができる。 合意に達したデータが破壊されるシナリオが存在しない。 長期間の停止や大幅に遅延したノードが Raft クラスタに復帰しても問題ない。 ノード故障によるリーダー交代が発生しても
漢(オトコ)のコンピュータ道: InnoDBでCOUNT()を扱う際の注意事項あれこれ。
InnoDBを使うとき、MyISAMと比較して度々やり玉に挙げられるポイントとして「COUNT()が遅い」というものがある。確かにInnoDBにおいて行数を弾き出すのにはテーブルスキャンが必要なのだが、そもそもMyISAMのCOUNT()が速い（テーブルの行数を保持してる）のが特殊なのであって、InnoDBが遅いわけではないのである。とはいえ、高速なCOUNT()については需要が多く、この問題には多くの人取り組んでおられるようだ。しかしながら、COUNT()のチューニングについては未だ語られていない点があるように見受けられるので、今日はCOUNT()のチューニングについて解説しようと思う。 COUNT(*)、COUNT(col)、COUNT(1)の違い基本的なことではあるが、COUNT(*)とCOUNT(col)では意味が異なるため、異なる結果が返される場合がある。COUNT(*)はフェッ
12.6. B-Trees — CS3 Data Structures & Algorithms
12.6. B-Trees¶ 12.6.1. B-Trees¶ This module presents the B-tree. B-trees are usually attributed to R. Bayer and E. McCreight who described the B-tree in a 1972 paper. By 1979, B-trees had replaced virtually all large-file access methods other than hashing. B-trees, or some variant of B-trees, are the standard file organization for applications requiring insertion, deletion, and key range searches.
B-treeインデックス入門 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? B-treeがMySQLで使用されている背景から、B-treeインデックスの構造、そしてそれに基づいたインデックスの使用方法の入門編です。以下の流れに沿ってまとめていきます。 インデックスってなに？ B-treeってなんでインデックスに使われているの？ B-treeインデックスの構造 インデックスの使用方法 ※ 勉強をかねてまとめていることもあり、間違っている箇所がございましたら教えていただけると嬉しいです。 インデックスってなに？ 全体の内容の中から特定部分を探すために使用する、本の索引のような概念のことです。これを用いることで、検索
B-trees and database indexes — PlanetScale
PlanetScale Postgres is the fastest way to run Postgres in the cloud. Plans start at just $5 per month. Learn more By Ben Dicken | September 9, 2024 What is a B-tree?The B-tree plays a foundational role in many pieces of software, especially database management systems (DBMS). MySQL, Postgres, MongoDB, Dynamo, and many others rely on B-trees to perform efficient data lookups via indexes. By the ti
さまざまなレート制限アルゴリズムをアニメーションでわかりやすく視覚化するとこんな感じ
スパム防止などのためのレート制限を行うアルゴリズムは多数存在しています。さまざまなアルゴリズムの特徴をアニメーションでわかりやすくまとめたブログ記事をChatGPT関連のサービスsmudge.aiが開発ブログにて公開しました。 rate limiter – smudge.ai blog https://smudge.ai/blog/ratelimit-algorithms 配信のチャット欄にスパムが出現するという状況において、レート制限がない場合にはスパマーは短時間のうちに多数の投稿を行ってチャット欄を一人で埋め尽くしてしまいます。 左上の「Enable rate limiting」にチェックを入れるとレート制限を加えた場合の挙動が確認できます。レート制限が加わったことで、スパマーの投稿のほとんどをブロックしてチャット欄に与える影響を下げることができました。このとき、状況に応じて適切なアル
The life and times of an Abstract Syntax Tree
You’ve reached computer programming nirvana. Your journey has led you down many paths, including believing that God wrote the universe in LISP, but now the truth is clear in your mind: every problem can be solved by writing one more compiler. It’s true. Even our soon-to-be artificially intelligent overlords are nothing but compilers, just as the legends foretold. That smart contract you’ve been wr
)
Merge (version control) - Wikipedia
Example history graph of a version-controlled project, with merges as red arrows In version control, merging (also called integration) is a fundamental operation that reconciles changes made to a version-controlled collection of files. Most often, it is necessary when a file is modified on two independent branches and subsequently merged. The result is a single collection of files that contains bo
mergekit-evolve による 進化的モデルマージ｜npaka
以下の記事が面白かったので、簡単にまとめました。 ・Evolutionary Model Merging For All 1. 進化的モデルマージ「Sakana.ai」は約1か月前、「進化的モデルマージ」に関する論文を発表し、大きな話題を呼びました。 「進化的モデルマージ」を使用すると、マージで特定のコンピテンシーや資質をターゲットにすることができます。これがないと、モデルマージは手動の探索プロセスになります。数十回のマージを試し、それらを手動で評価し、マージパラメータが最終モデルの性能にどのように関連するか頭の中で考え出そうとすることになります。「進化的モデルマージ」を使用すると、どのような性質を持たせたいかを指定でき、最適化がそれを処理します。 「mergekit」では、この「進化的モデルマージ」を利用できます。 2. ハードウェア要件7Bモデル の場合は 24GB のVRAMで十分で
僕たちがグラフニューラルネットワークを学ぶ理由
グラフニューラルネットワーク - Forkwell Library #50 https://forkwell.connpass.com/event/315577/ での講演スライドです。 サポートサイト：https://github.com/joisino/gnnbook グラフニューラルネット…
Kubernetes: kubectl apply の動作 - Qiita
kubectl apply はオブジェクトが存在しなければ作成し、存在すれば差分を反映してくれる便利なコマンドです。しかし差分の反映は単純な上書きではないので注意が必要です。この記事では Kubernetes Meetup Tokyo #5 で発表した内容をベースに kubectl apply の動作を整理してみました。Kubernetes v1.9.0 で確認をしています。 kubectl apply とは kubectl にはオブジェクトを操作する様々なサブコマンドが用意されています。apply 以外の create, replace などのサブコマンドは、現在のオブジェクトの状態を意識して操作をする必要があります。例えば kubectl create では存在する名前のオブジェクトを再度作ろうとするとエラーになりますし、kubectl replace では存在しないオブジェクトを上書
Git の 3-way merge とは具体的にどのようなアルゴリズムですか？
「way」とは ここでの「way」とは、マージする際に "見て" いる場所のこと。3-way merge は 3 つの場所を見ている。 2-way merge：「マージの起点コミット」「マージさせたいコミット」を見てマージする 3-way merge：「マージの起点コミット」「マージさせたいコミット」「2 つのコミットの最近共通祖先となるコミット」を見てマージする アルゴリズムの概略 ここでは Git のデフォルト・マージ戦略である「recursive」にしたがった 3-way merge のアルゴリズムを書きます。簡単のために省略して書いています。 入力: コミットグラフ。マージの起点としたいコミット X。X にマージしたいコミット Y。 出力: マージできるかどうか。マージできるなら、マージ済みコミット Z を含む新しいコミットグラフ。マージできないなら、コンフリクト箇所。 手順 X
Winnyの金子さんのED法について | やねうら王 公式サイトやねうら王 公式サイト
Winnyの金子勇さんが考案された機械学習アルゴリズムED法を再現して実装した人がいていま話題になっている。 『Winny』の金子勇さんの失われたED法を求めて…いたら見つかりました https://qiita.com/kanekanekaneko/items/901ee2837401750dfdad いまから書くことは私の記憶頼りなので間違ってたらコメント欄で教えて欲しい。 1998年ごろだと思うのだが、私はWinnyの金子勇さんのホームページの熱心な読者だった。(ページも全部保存してたので私のHDDを漁れば出てくると思うが、すぐには出せない。) Winnyのβ版が発表されたのが2002年なのでそれよりはずいぶん前である。 当時、金子さんはNekoFightという3D格闘ゲームを公開されていた。そのゲームには、自動的に対戦から学習するAIが搭載されていた。 当時の金子さんのホームページの
『Winny』の金子勇さんの失われたED法を求めて - Qiita
結論から言うと、この記事を読んだ @pocokhc (ちぃがぅ)さんという方が金子勇さんが書いたED法のサンプルプログラムを見つけてくださいました。 ちぃがぅさんの記事はこちら 自分で解明したかったという気持ちも無いことは無いですが、バズった時点で誰かが実装してくれそうな気はしていました。新卒からIT業界に入って4年目が始まったところですが、業務以外で初めて業界にコントリビュートできた気がして嬉しいです！ 追記ついでに、謝罪します。初回公開時に記事タイトル含め本文中で何か所か「Winney」と書いてしまっていた箇所がありました。失礼いたしました。誤字修正してあります。指摘してくださった何人かの方に感謝申し上げます。 はじめに 今更ですが映画『winny』を見ました。 劇中で、金子勇さんのセリフにED法という聞いたことのないアルゴリズムが登場しました。 『このNekoFightにはAIを搭載
なぜUUIDはハイフンで8-4-4-4-12に区切られているか？ - Buri Memo:
ある特徴的な文字列がある。 11b484b6-cfeb-4730-8fba-467aee2d26ad 使ったことがあれば、恐らくすぐに UUID であると分かると思う。UUID は16進数がハイフンで分けられた特徴的なフォーマットをしている。その区切り方は、 8-4-4-4-12 となんだか不思議な感じだ。 そもそも、UUID は 128bit の数値であり、それを文字列で表現したものなのでハイフンが無くたって問題ない。にもかかわらずわざわざ覚えにくいケタで区切ることが多い。 その理由として、最初に思いつくのは人間が読みやすくするためだとは思うが、覚えやすく均等に区切ったり、左右対称の形にはできなかったのだろうか？ UUID の定義 生成した UUIDv1 を眺めてみる 元祖 UUID（Network Computer System の UUID） 形式の謎 RFC4122 で times
いろんなバンディットアルゴリズムを理解しよう - Qiita
今回は、何も知らないところからバンディットアルゴリズムを学びました。 シンプルなバンディットアルゴリズムから、各ユーザーごとに最適化するContextual Bandit、順序を最適化するCascading Banditまで解説します。 学んでいて疑問に思ったことを解消しつつ記載しています。 ソースコード https://github.com/birdwatcherYT/bandit 対象読者 バンディットアルゴリズムを理解して実装したい人 ユーザーごとにカスタマイズしたバンディットを理解して実装したい人（Contextual Bandit） 順序を最適化するバンディットを使いたい人（Cascading Bandit） バンディットアルゴリズム バンディットの問題設定を説明します。 スロットマシンN台がある スロットマシンの腕を引くと報酬がもらえる 累積報酬を最大化したい バンディットアル
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
CS 1332 Data Structures and Algorithms Visualizations
データベースでユニークキーにUUIDを使うメリットは何ですか？連番やタイムスタンプまたは複合などではいけないのでしょうか？どうも視認性が悪く使いにくく感じますし連番でも衝突しない気もします。
B+木入門：PHPで理解する データベースインデックスの仕組み/b-plus-tree-101
