・二分探索木 (binary search tree) ・AVL tree ・B-tree ・B+ tree について順を追いながら説明。 流れを細かく書いたので、わかりやすいと思います。
これでわかるB-treeアルゴリズム / B-tree algorithm
・二分探索木 (binary search tree) ・AVL tree ・B-tree ・B+ tree について順を追いながら説明。 流れを細かく書いたので、わかりやすいと思います。
回転をサボるAVL木を落とす - Qiita
この記事では$N$を二分探索木中の要素数(ノード数)として以後断りなく用います。 今回はAVL木をsetのような平衡二分探索木として扱いますが、配列型(平衡二分木)として使ってもほとんど同じことがいえます。 前提知識 二分探索木について (分かってると嬉しい) : AVL木の平衡方法 正しい平衡 ノードの平衡係数は(左の子の高さ) $-$ (右の子の高さです)。 説明によっては一重回転をやるケースと二重回転をやるケースとを完全に別のものとして区別していますが、二重回転は一重回転を2回やってるだけで、かつその2回目が一重回転をやるケースの一重回転と一致するので以下のように実装することができます。 ノード$x$の平衡係数が2の場合 $x$の左の子の平衡係数が-1なら左の子を左回転 $x$を右回転 ノード$x$の平衡係数が-2の場合(上の全く左右対称) $x$の右の子の平衡係数が1なら右の子を右
GDBM で学ぶ Extendible Hashing
最近仕事で GDBM を使う機会があり、GDBM で使われている extendible hashing に興味を持ったのでまとめてみました。 なお、今回対象にしている GDBM のバージョンは 1.12 です。 アジェンダ GDBM とは ハッシュテーブルの基礎 ハッシュ関数 衝突処理 リハッシュ Extendible Hashing GDBM による Extendible Hashing ハッシュ関数 ファイルヘッダのデータ構造 バケットのデータ構造 バケット要素のデータ構造 衝突処理 ディレクトリの拡張とバケットの分割 データベースファイルは要素数が多いと肥大化する おわりに 参考 GDBM とは http://www.gnu.org.ua/software/gdbm/ 曰く GNU dbm (or GDBM, for short) is a library of database f
ハッシュ探索について（個人用メモに近い） - Qiita
1.はじめに 友人と応用情報の勉強会を始めたのでそれ用のまとめです． 各個人が気になったところ，もう少し知りたいなと思ったところを勝手にまとめて共有する方式の勉強会です．（毎回記事にするかは怪しい） 記事としては既出もいいところでしょうが，今回の僕のテーマは探索アルゴリズム（ハッシュ探索）です． （綺麗にまとまっていませんが後日時間があれば追記したり整理します...） アルゴリズムについて まず僕がこれをテーマに選んだのは，今までハッシュは全単射じゃないと意味がない（完全に全単射は無理でしょうが，それに近いもの）と思っていたのですが，このハッシュ探索では，全単射が理想ではあるものの，そうでなくとも探索対象の集合を分割できるだけでも意味があるんだ，というもので賢いなと感動したからです． ハッシュはあくまでも道具であって，目的（解きたい問題）によっては使い方も変わるんだなと． 図にするとこんな
DBMの設計と実装 その1 ハッシュ関数 - 豪鬼メモ
個々のレコードがハッシュテーブル内のどのバケットに属するかはハッシュ関数で決める。入力値の種類によらずハッシュ値がうまいことばらけて衝突が起こりにくい関数が良い。今回は定番のMurmur hashを採用した。Rubyの文字列型のハッシュ関数もこれだ。 Murmur hashの値に対してバケット数で剰余を取れば十分なハッシュ関数として機能する。しかし、以前にそれで実装したソースを公開していたら、Murmur hashの作者から直に連絡があり、下位ビットだけ使うのは最善ではないと指摘された。32ビット以下のハッシュ関数が必要な場合、XORを使って上位ビットの折返しをした上で、剰余を取るべきだと。したがって、バケット数に応じたハッシュ関数の実装は以下のようになる。 uint64_t PrimaryHash(std::string_view data, uint64_t num_buckets)
赤黒木の本質 - Qiita
この記事はデータ構造とアルゴリズム Advent Calendar 2019 16日目の記事です。 15日目は@minaminaoさんによる「すごいTrie」です。 17日目は@takilogさんによる「Fréchet距離の計算アルゴリズム」です。 はじめに この記事では有名なデータ構造である赤黒木がなぜあのようなトリッキーな定義になっているのかその本質について解説します。 赤黒木の定義を見てトリッキーと思うかどうかは個人差あるかと思いますが、少なくとも僕が初めて赤黒木を学んだ時はなぜこのような定義になっているのか、そしてどうやって思いついたのか見当がつかずとても不思議に感じました。 しかし、その後赤黒木の成り立ちやその基になったデータ構造について知ると、トリッキーに見えた定義がとても自然であることを実感しました。 おそらく知っている人は当たり前に知っている内容だとは思いますが、知らない人
セグメント木をあきらめた人のための平方分割 - くじらにっき++
この記事はCompetitive Programming Advent Calendar 2016（その2）の12月15日の記事です。 www.adventar.org はじめに 基本事項 1点に対する変更クエリ・区間に対する質問クエリ Range Sum Query Range Minimum Query 区間に対する変更クエリ・1点に対する質問クエリ Range Add Query Range Update Query 区間に対する変更クエリ・区間に対する質問クエリ RSQ and RAQ RMQ and RUQ 応用例 Flipping Parentheses セグメントツリーにチャレンジしたくなったら 謝辞 はじめに 私はRMQのような典型的なセグメント木までは比較的容易に実装できるのですが，それよりも難しいクエリに対応したセグメント木を書くのは難しく感じています。とはいえ「区間に
splay tree をソラで書く！！！
(2023/02/05) 実はここに書いた方法はとにかく覚えにくいので、今度新しく書きます。考察不足でしたのでおわび申し上げます。 動機の例 自作ライブラリで Library Checker の問題[1]を解きたい link/cut tree を実装したい splay tree の面白い機能を思いついたときに実装したい 平衡二分探索木や動的木が JOI に出る(?)[2] [3] ネタバレ注意 PCK に出る(?)[4] ネタバレ注意 目標 平衡二分探索木の一種である (bottom-up の) splay tree の C++ 言語による実装例を示す splay tree を覚えやすい・一発で書きやすい方法で実装し、注意点をまとめる 注意点はできるだけ多くの点を挙げ、実装の方針が同じ splay tree が正しく動作しなかったときのチェックリストになるようにする この実装を用いて Li
完備辞書（簡潔ビットベクトル）の解説 - アスペ日記
以前、「簡潔データ構造 LOUDS の解説」というシリーズの記事を書いたことがあります。 LOUDS というのは木構造やtrieを簡潔に表すことができるデータ構造なのですが、この中で「簡潔ビットベクトル」というものについてはブラックボックスとして扱っていました。 また、中学生にもわかるウェーブレット行列を書いたときも、その中で出てきた「完備辞書」の実装には触れませんでした。 この「簡潔ビットベクトル」「完備辞書」は、同じものを指しています*1。 今回は、このデータ構造*2について書いてみます。 完備辞書でできること ビット列に対する定数時間の rank と selectです*3。 rank()は、「ビット列の先頭から位置 k までに、1 のビットがいくつあるか」*4。 select()は、「ビット列の先頭から見て、n 個目の 1 のビットの次の位置はどこか」*5。 それぞれ例を挙げます。
最大内積探索(MIPS)のライブラリを公開しました | カメリオ開発者ブログ
エンジニアの谷田です。 最大内積探索問題(Maximum Inner Product Search, 以下MIPS)ってご存知でしょうか？データベースに登録された多くのアイテムのベクトルのうち、クエリのベクトルとの内積を最大化するアイテムを探す問題です。行列分解を用いてユーザにアイテムをレコメンドするときなど、この探索が問題になってくることがあります。 MIPSを解く単純な方法は、与えられたクエリに対してデータベースのすべてのアイテムとの内積を計算することですが、これにはアイテム数に比例した時間がかかります。そのため、アイテムが何千万や何億といった数にのぼると、ベストなアイテムを返す処理を遅延なくリアルタイムで行うのは厳しくなってしまいます。 これを解決するために、局所性鋭敏型ハッシュ(Locality Sensitive Hashing, 以下LSH)という手法をもとにしたアルゴリズムが
セグメント木/遅延評価セグメント木の実装のコツ - 私のひらめき日記
はじめに セグメント木と遅延評価セグメント木を自分がどうやって空で実装しているのかをメモする。C言語での実装。 セグメント木が実装できれば、大体の場面で平衡二分探索木を実装する必要性がなくなり、競技プログラミング等で解ける問題の幅がぐっと広がる。 また、Binary Indexed Tree(BIT)の上位互換なので、とりあえずセグメント木さえきちんと実装できれば、BITとかをあまり気にしなくて良くなる。 Reference http://tsutaj.hatenablog.com/entry/2017/03/30/224339 https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/1 蟻本のセグメント木の解説 AOJ courceの問題中心に例題もこの記事の一番下の章に挙げている。 セグメント木の実装のコツ priority que
Perceptual Hashを使って画像の類似度を計算してみる - ユニファ開発者ブログ
最近、引越しをしたWebエンジニアの本間です。 引越しの作業は大変面倒でしたが、新しい街に来た時のワクワク感がやっぱりいいなーと感じております。 さて、弊社のサービスである「写真サービス るくみー」では、毎日たくさんの写真をアップロードしていただいているのですが、中には内容がほとんど同じ写真が入ってしまうことがあります。 これらの写真がそのまま販売されてしまうと、写真を選ぶ際に邪魔になったり、間違って複数枚購入してしまうことがあるため、可能な限り避けたい事象です。 「同じ内容」の写真を自動で判別する方法がないか調査していたところ「Perceptual Hash」という手法を見つけました。 Pythonでの画像処理の勉強も兼ねて、今回この手法を紹介してみようと思います。 Perceptual Hashとは ハッシュ値は、「あるデータをハッシュ関数に入れて得られる値」で「同じデータからは常に同
4-bit PQの解説
はじめに 4-bit Product Quantization (4-bit PQ)は、2021年現在最も高速な近似最近傍探索アルゴリズムの１つです。 この度、Fixstars社と共同で、faissライブラリにおける4-bit PQのARM上での高速実装を達成し、faiss本家にマージされました。 本記事では、4-bit PQについて解説します。 関連issue。マージされたPR。faiss 1.7.1以降で使えます。 Fixstars社の今泉さんによる、ARM実装の技術詳細。ARMに関する詳細はこちらをご覧ください。本記事では4-bit PQアルゴリズムそのものについて解説します。 4-bit PQは、PQという手法を近似し、SIMDレジスタによる恩恵を最大限に受けられるようにした方式です。以下では簡単のためVector Quantization (VQ)を対象とした、4-bit VQに
データ構造と メソッドのネーミング - codic ブログ
データ構造など技術的な背景をちゃんと知っていれば、データ操作に関する正しい英語を使えるねーて話です。用語のイメージもつかめるようにしていますので、shift / unshift とかイメージできない方もどうぞ。 1. push / pop = スタック push pop は、スタックの用語で、それぞれ pop はスタックから取り出す、push は挿入する事を意味します。JavaScript や Ruby の Array には、スタックとしてのコンセプトもあるので、push / popという用語が使われます。 対して、Javaの ArrayList (インターフェースは Collection） は、単なる集合を表すインターフェースなので、抽象化のために add / remove というネーミングが使われます。そういえば、Javaには、Stackというクラスも別途用意されていますね。Stack
データ指向アプリケーションデザインを読んでLSM-treeインデックスに基づくKVSを作る - 油そば
この記事はMicroAd Advent Calendar 2019の4日目の記事です。 qiita.com はじめに どういうKVSを作るか 手始めにログベースのKVS 書き込み, 読み取り, 削除 ログフォーマットの決定 実装 LSM-treeインデックスを持つKVSを実装する 書き込み MemTableからSSTableの生成 SSTableの反映 SSTableのマージとコンパクション バッファを使ったマージ&コンパクション ステップ1. SSTable毎にキーを読み出す ステップ2. バッファ内の最小のキーの最新の値を読み出す 再起動時の復元 アクターで組み立てる 書き込みのケース 読み取りのケース コード はじめに データ指向アプリケーションデザインは今年買って読んだ技術書の中で最も読み応えがあった本でした。 www.oreilly.co.jp 単に周回で読むだけでも学びが多い本
キャッシュ機構 TinyLFU のアーキテクチャと、それを支えるアルゴリズム - 好奇心に殺される。
Computer Science キャッシュ機構 TinyLFU のアーキテクチャと、それを支えるアルゴリズム TinyLFUの論文を読んだので概要と、それを支えるアルゴリズムを紹介します。 Overview TinyLFU はアクセス頻度を近似し、軽量でハイパフォーマンスに設計されたキャッシュアルゴリズムです。最近、Database Internals を読んでいて TinyLFU を知ったのですが、Database Internals では TinyLFU の詳細が書かれていなかったので、TinyLFUが提案されている論文を読んでみました。その内容をザックリ解説してみようと思います。 論文はこちらです。 TinyLFU: A Highly Efficient Cache Admission Policy いきなりTinyLFUの紹介を始めると混乱するので、ベースとなる技術やアルゴリズム
簡潔データ構造やBalancedParenthesesの紹介資料メモ
0_succ_bp.md 発表資料メモ: 簡潔データ構造について 主題 数千万オーダーの文字列集合(およびマップ)を如何にサイズ効率良く表現するか、の話 諸事情で集合をメモリ上に保持したいことがあるが、サイズは節約したい 実際にはサイズのみを追求するのではなく、諸々のトレードオフを加味しつつバランスを取る 今回はそれを実現するための方法の一つである 簡潔データ構造 について説明する: どういったデータ構造(のクラス)であるかの紹介 一言でいうなら「木構造を情報理論的な下界に近いサイズで表現するためのデータ構造」 性能特性の提示 簡潔データ構造の一つであるBalancedParenthesesについては、ある程度掘り下げて説明する 静的構築前提 亜種や類似手法の紹介(余裕があれば) ポインタの重さを知って貰う 注意 筆者はこの分野に特に精通している訳ではなく、用語や細部はいろいろと怪しいので
billion-scaleの近似最近傍探索
1 billion-scaleの近似最近傍探索 松井勇佑 国立情報学研究所 2018/7/19 2 関連する資料 直積量子化を用いた近似最近傍探索に関するサーベイ http://yusukematsui.me/project/survey_pq/survey_pq_jp.html サーベイ論文： Y. Matsui, Y. Uchida, H. Jégou, and S. Satoh “A Survey of Product Quantization”, ITE Journal, 2018, [link] 関連するスライド・本： ショートコードによる 大規模近似最近傍探索 講義資料，大阪大学，2016 [link] 【招待ショートサーベイ】 直積量子化を用いた 近似最近傍探索 PRMU, 2016 [link] コンピュータビジョン―広がる要素技術と応用― 第6章：近似最近傍探索 共立出版
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
「階層型データベース」調べても基本概念以外ほとんど情報が出てこないです。製品名、解説サイト、使用している企業/システム、経験談等具体的な情報を教えてもらえませんか？ - Quora
転置インデックスのポスティングリスト圧縮アルゴリズムをRustで実装してみる | by mocobeta | Medium