巨大な集合に対して、定数メモリ&定数時間で近似値を計算できる、確率的データ構造の紹介スライドです。 本スライドは、株式会社エフ・コードの社内勉強会(2018/08/30)にて使用されたものです。
確率的データ構造を使って巨大な集合を定数メモリで近似しよう
巨大な集合に対して、定数メモリ&定数時間で近似値を計算できる、確率的データ構造の紹介スライドです。 本スライドは、株式会社エフ・コードの社内勉強会(2018/08/30)にて使用されたものです。
『みんなのデータ構造』発売および予約開始のお知らせ – 技術書出版と販売のラムダノート
ご来店ありがとうございます。 本日より、新刊『みんなのデータ構造』の発売を開始しました。紙書籍の発送は7月25日前後を予定しています。電子書籍は購入後すぐにお読みいただけます。 『みんなのデータ構造』は、Pat Morin氏による “Open Data Structures” を翻訳して書籍として出版するものです。Pat Morin氏による原文は、クリエイティブコモンズ継承ライセンス（CC BY）で公開されており、誰でも自由に教材として活用できるだけでなく、内容に手を入れて別のライセンスで再配布したり、販売したりできるようにされています。堀江氏、陣内氏、田中氏による翻訳と、ラムダノート株式会社による編集も、すべてCC BYで公開しており、同様に自由に利用していただくことが可能です。 書籍版『みんなのデータ構造』（紙書籍および電子書籍）につきましては、クリエイティブコモンズライセンスではなく
OpenDataStructures.jp
オープンソース版 Open Data Structures 日本語訳の PDF ファイルを以下で公開しています。最新のソースコードは GitHub のリポジトリ https://github.com/spinute にあり、適宜こちらの PDF ファイルに反映しています。 以下のものは C++ 版です（Java 版はこちら、疑似コード版はこちらにあります）。 目次 訳者まえがき 本書の読み方 訳者謝辞 なぜこの本を書いたのか 謝辞 第1章 イントロダクション 効率の必要性 インターフェース 数学的背景 計算モデル 正しさ、時間計算量、空間計算量 コードサンプル データ構造の一覧 ディスカッションと練習問題 第2章 配列を使ったリスト ArrayStack：配列を使った高速なスタック操作 FastArrayStack：最適化された ArrayStack ArrayQueue：配列を使ったキュ
2分探索のバグりにくい書き方 - くじらにっき++
問題設定 整数二分探索とは，以下の矢印の位置を求める問題である。 パターンA パターンB 解き方 前提として，範囲を閉区間で扱うと微妙にバグるので半開区間で扱う。while文の条件はどちらのパターンでも ub - lb > 1 である。 パターンA [lb, ub) として範囲を扱うのが正解。 mid = (lb + ub) / 2とする。矢印のところをチェックして(check(mid) ? lb : ub) = mid;と更新する。 失敗パターンとして，(lb,ub] として範囲を扱った場合を考える。 (lb, ub] の中にcheckがTrueになるものが無くなってしまった。 ダメってはっきりわかんだね。 パターンB (lb, ub] として範囲を扱うのが正解。 mid = (lb + ub) / 2とする。矢印のところをチェックして(check(mid) ? ub : lb) = m
ソートアルゴリズムを極める！ 〜 なぜソートを学ぶのか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 今回はソートについて記します。 0. はじめに データ構造とアルゴリズムを学ぶと一番最初に「線形探索」や「ソート」が出て来ます。これらのテーマは応用情報技術者試験などでも頻出のテーマであり、アルゴリズムの Hello World とも呼ぶべきものです。 特にソートは、 計算量の改善 ($O(n^2)$ から $O(n\log{n})$ へ) 分割統治法 ヒープ、バケットなどのデータ構造 乱択アルゴリズムの思想 といった様々なアルゴリズム技法を学ぶことができるため、大学の授業でも、アルゴリズム関連の入門書籍でも、何種類ものソートアルゴリズムが詳細に解説される傾向にあります。本記事でも、様々なソートアルゴリズムを一通り解説してみました。 しかしながら様々な種類のソートを勉強するのもよいが、「ソートの使い方」や
The Case for Learned Index Structures
The Google-brewed paper has thought-provoking ideas and is poised to be remembered for a long time. The paper’s key question is: can indexing data structures (e.g. B-Trees or HashMaps) be replaced with machine learning models (e.g. Neural Networks) ? (Figure 1). Indexes as predictive modelsThis simple question completely broke mine and others’ previous idea of what an index is: Before: indexes ==
オンラインアルゴリズムとストリームアルゴリズム - 共立出版
未知の未来に関る決断や予測は人間生活では必須であり、最善と信じて行った行動が後で大きな後悔を生むという事は日常茶飯事である。オンラインアルゴリズムの理論は、このような未知の未来に影響する情報処理を的確に行うための計算理論であり、時事刻々変化する巨大データに対して、将来どのような状況が起きても困らないように行動をプランする最善の手法の設計と数理的解析を探求するものである。本書はオンラインアルゴリズム理論の基礎理論である競合比解析に始まり、オンライン学習、確率的最適化、ストリームアルゴリズムなど、最先端の計算理論を用いた最新成果までを網羅し、実際に即した判りやすい例題を利用してオンラインアルゴリズムを幅広い見地から紹介する、世界でもはじめての本格的な教科書である。 第1章 はじめに 第2章 オンラインアルゴリズムの基本理論 第3章 いろいろなオンライン問題 第4章 オンライン学習モデル 第5章
アルゴリズムイントロダクション 第3版 総合版：世界標準MIT教科書
アルゴリズムイントロダクション 第3版 総合版：世界標準MIT教科書 T. コルメン, C. ライザーソン, R. リベスト, C. シュタイン(著), 浅野哲夫, 岩野和生, 梅尾博司, 山下雅史, 和田幸一(訳) 近代科学社 15,400円 (14,000円+税) 計算機科学の基礎分野で世界的に著名な4人の専門家がMITでの教育用に著した計算機アルゴリズム論の包括的テキスト．前版までで既にアルゴリズムとデータ構造に関する世界標準教科書としての地位を確立しているが，より良い教科書を目指して再び全面的な記述の見直しがなされている． 関連サイト本書の関連ページが用意されています。 アルゴリズムイントロダクション 第3版 総合版（近代科学社ウェブサイト）内容紹介世界標準 MIT 教科書!! 原著は，計算機科学の基礎分野で世界的に著名な4人の専門家がMITでの教育用に著した計算機アルゴリズム論の
Roaring Bitmaps
A better compressed bitset Roaring bitmaps are compressed bitmaps. They can be hundreds of times faster. Grab one of our research papers Roaring Bitmaps on GitHub Widely used Roaring is found in Google Procella: YouTube’s SQL Engine, Apache Lucene and derivative systems such as Solr and Elasticsearch, Apache Druid, Apache Spark, Apache Hive, Apache Tez, Apache Zeppelin, Apache Doris, Apache Carbon
Segment Tree - Algoogle
N := 区間の幅 解説 Segment Treeは主に区間に対するクエリを処理するために使われる. 完全二分木で実装されるので各クエリの計算量はO(log N)になる. 自由度が高く, 区間を扱う様々なものに利用される. コードはRMQとその区間足し込みバージョンの実装. この2つの書き方をなんとなくイメージできればある程度柔軟に実装できるようになるでしょう. 区間足し込みはその区間全体に一気に足された数というのを遅延評価することで実現できる. コード struct segtree { int N, dat[2*MAX]; segtree() {} segtree(int n) { N = 1; while(N < n) N *= 2; for(int i = 0; i < 2*N-1; i++) dat[i] = inf; } // update k th element void u
A general purpose counting filter: making every bit count | the morning paper
the morning paper a random walk through Computer Science research, by Adrian Colyer Made delightfully fast by strattic A general purpose counting filter: making every bit count Pandey et al., SIGMOD’17 It’s been a while since we looked at a full on algorithms and data structures paper, but this one was certainly worth waiting for. We’re in the world of Approximate Membership Query (AMQ) data struc
カラムナフォーマットのきほん 〜データウェアハウスを支える技術〜 - Retty Tech Blog
こんにちは、Retty.Inc ソフトウェアエンジニア兼データサイエンティストのchie（@chie8842）です。 好きなたべものは焼肉とみかんです。 現在Rettyでは、次世代分析基盤を構築しています。Rettyでは、サービス拡大に伴いログの急増や分析需要の拡大が見込まれるため、高いスループットとコストパフォーマンスを両立する、スケールするアーキテクチャ設計が求められています。 今回は、こうしたスケールするアーキテクチャ設計の実現のために理解しておくべきDWHのコア技術の一つである、カラムナフォーマットに焦点を当てて紹介します。 はじめに - カラムナフォーマットとは カラムナフォーマットとは、データベースの分析用途に利用されるファイルフォーマットの種類の一つです。大量のデータを扱う際に効率的に圧縮してストレージコストを下げたり、計算時に必要なデータだけを取り出して計算コストを小さくで
Amazonの推薦システムの20年
IEEE Internet Computingの2017年5・6月号に "Two Decades of Recommender Systems at Amazon.com" という記事が掲載された。 2003年に同誌に掲載されたレポート "Amazon.com Recommendations: Item-to-Item Collaborative Filtering" が Test of Time、つまり『時代が証明したで賞』を受賞したことをうけての特別記事らしい 1。 「この商品を買った人はこんな商品も買っています」という推薦で有名なAmazonが1998年にその土台となるアルゴリズムの特許を出願してから20年、彼らが 推薦アルゴリズムをどのような視点で改良してきたのか 今、どのような未来を想像するのか その一端を知ることができる記事だった。 アイテムベース協調フィルタリング 20年前も
空間インデックス(R-tree)入門 - たにしきんぐダム
R-treeとは空間データを効率良く検索するためのインデックス構造。R-tree について調べたのまとめておく。 目次 目次 参考資料 ナイーブな例 R-tree の概要 各ノードの要素数 参照処理 点検索 範囲検索 データの挿入・削除 挿入処理 ノードの分割 Exhaustive Algorithm Quadratic-Cost Algorithm Linear-Cost Algorithm 削除 木の再構築のアルゴリズム 更新処理 まとめ 参考資料 Guttman, Antonin. R-trees: a dynamic index structure for spatial searching. Vol. 14. No. 2. ACM, 1984. MySQL 5.7 Reference Manual - Creating Spatial Indexes PostGIS 2.3.3d
B TreeとB+ Treeの違い - Carpe Diem
概要 インデックスに対してMongoDBはB Treeを採用し、MySQLのInnoDBはB+ Treeを採用しています。 どうして採用しているアルゴリズムが違うのだろう？と思って調べてみました。 主な違い B+ TreeはほとんどB Treeと同じですが、以下の点が異なります。 リーフノードとリーフノードを結ぶポインタがある データはリーフノードのみに保持する 具体例 言葉だけだと分かりにくいので、Visualizeするツールを使って具体例を表示します。 [1, 2, 3, 4, 5, 6, 8, 10, 15, 18]という数列に対し、Order: 3で作ってみます。 Orderは１ノードから出る枝の数のことです。 B Tree B-Tree Visualization B+ Tree B+ Tree Visualization 先程のB Treeと違って、データはリーフノードに持つの
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Revisiting b+-trees
Decoding billions of integers per second through vectorization
Home
HugeDomains.com
An Atomic Hash Table ·