Advanced Data Structures (6.851)
6.851: Advanced Data Structures (Fall'17) Prof. Erik Demaine TAs: Adam Hesterberg, Jayson Lynch LAs: Andrew He, Stef Ren [Home] [Lectures] [Problem Sets] [Project] [Coauthor] [Accessibility] Data structures play a central role in modern computer science. You interact with data structures even more often than with algorithms (think Google, your mail server, and even your network routers). In additi
みんなのデータ構造
紙書籍をお届けします（PDFがついてきます） PDFのみ必要な場合は、こちらからPDF単体をご購入ください 紙書籍は通常、ご注文から2～3営業日で発送します 年末年始や大型連休など、1週間から10日程度、配送のお休みをいただく場合があります。詳しくはお知らせをご覧ください 配列、リスト、木、グラフ、それぞれの理論的な特性を知り、実装まで理解するためのガイドブック Pat Morin 著、堀江 慧・陣内 佑・田中 康隆 共訳 288ページ A5判 電子書籍の形式：PDF ISBN：978-4-908686-06-1 2018年7月20日 第1版第1刷 発行 正誤情報 データの格納方法を工夫するだけで、魔法みたいにアルゴリズムが導出できる。うまくデータを整頓するだけで、画期的に計算が速くなる。仕事で直面している問題がなかなか解決しないのは、問題に対する適切なデータ構造を知らないから、というだけ
An Introduction to Hashing in the Era of Machine Learning
In December 2017, researchers at Google and MIT published a provocative research paper about their efforts into “learned index structures”. The research is quite exciting, as the authors state in the abstract: “[…] we believe that the idea of replacing core components of a data management system through learned models has far reaching implications for future systems designs and that this work just
15 Great Articles About Decision Trees - DataScienceCentral.com
Home » Uncategorized15 Great Articles About Decision Trees Vincent GranvilleFebruary 21, 2018 at 1:30 pm This resource is part of a series on specific topics related to data science: regression, clustering, neural networks, deep learning, Hadoop, decision trees, ensembles, correlation, outliers, regression, Python, R, Tensorflow, SVM, data reduction, feature selection, experimental design, time se
簡潔データ構造 - 共立出版
2019年度大川出版賞受賞！ 簡潔データ構造とは、データをエントロピーの限界まで圧縮して保存しつつ、検索等の処理を行う際にはあたかも非圧縮のデータに対してアクセスしているように扱えるデータ構造である。データを圧縮することにより、これまでのデータ構造よりも多くのデータを扱えるようになる。扱うデータによっては 1/100 まで圧縮できる。2000年以降、多くの理論的・実用的データ構造が提案されており、ゲノム情報処理等では実際に使われている。 本書は、基本的な簡潔データ構造（ビットベクトル、文字列、木構造等）の理論を説明する。初期の簡潔データ構造は非常に難解なものが多く、実装しても性能の出ないことが容易に想像できたが、後に提案されたものは理論的性能を保ったまま簡単化されており、容易に実装可能であり実際の性能も良い。本書ではそのようなデータ構造を中心に説明しているため、簡潔データ構造を実問題に適用
プログラミングコンテストでのデータ構造
2. 内容 • Union-Find 木 • バケット法と平方分割 • セグメント木 • 共通点：自分で実装するデータ構造 • セグメント木が中心 – IOI でのセグメント木の出題が非常に多い
What's new in purely functional data structures since Okasaki?
Since Chris Okasaki's 1998 book "Purely functional data structures", I haven't seen too many new exciting purely functional data structures appear; I can name just a few: IntMap (also invented by Okasaki in 1998, but not present in that book) Finger trees (and their generalization over monoids) There are also some interesting ways of implementing already known datastructures, such as using "nested
私が書いた最速のハッシュテーブル – PART 1 | POSTD
結局、やり出したら止まりません。私は以前、” I Wrote a Fast Hashtable（私が書いた高速なハッシュテーブル） “という記事と、それに次いで” I Wrote a Faster Hashtable（私が書いたより高速なハッシュテーブル） “という記事をブログにアップしましたが、今回ついに、最速のハッシュテーブルを書き上げました。これが意味するところは、ルックアップがどのハッシュテーブルよりも速いということです。それに加えて、挿入や削除も（最速とまではいかないまでも）非常に速く行えます。 秘訣は、探索回数の上限を設定したロビンフッドハッシュ法を使用することです。ある要素が、その理想的な位置からX数以上、離れた位置にある場合、テーブルを拡張することで、全ての要素が、その大きなテーブル内において、理想的な位置に近づくようにします。結果的に、このやり方は非常にうまくいきました。
I've been writing ring buffers wrong all these years
So there I was, implementing a one element ring buffer. Which, I'm sure you'll agree, is a perfectly reasonable data structure. It was just surprisingly annoying to write, due to reasons we'll get to in a bit. After giving it a bit of thought, I realized I'd always been writing ring buffers "wrong", and there was a better way. Array + two indices There are two common ways of implementing a queue w
Comparison of Hash Table Libraries
Notes: CPU time is measured in nanosecond for each operation. Memory is measured by TCmalloc. It is the memory difference before and after the allocation of the hash table, instead of the peak memory. In this experiment, integers are inserted in order and there are no collisions in the hash table. All these libraries provide similar API. Discussions Speed and memory. The larger the hash table, the
圧縮配列ライブラリyunomiをリライトしました - 品川海苔は伊豆の磯餅
数年前に圧縮配列を作ってgithubで公開していました。 この度そのライブラリを一から書き直してリニューアルしました。 github.com 元々圧縮配列ライブラリであることをメインに作っていたのですが、今回のリニューアルで簡潔データ構造のライブラリとしても使えるようになっています。 圧縮配列とは 大量のデータを配列に格納しないといけないとき、あまりにデータが大きすぎてメモリに乗り切らないことはありませんか？圧縮配列は情報を圧縮状態でメモリに格納するためのものです。圧縮されているためそのまま格納するより省メモリですみます。当然通常の配列に比べて速度は落ちますが、ランダムアクセスリードが可能です。yunomiでは、Kimmo Fredriksson and Fedor Nikitinの論文に記載してあるFibonacciコーディングによる圧縮配列を実装しています。詳細を知りたい方は参考文献に
高速な辞書実装に使えるトライ木をD言語とPythonで書いてみた - Qiita
トライ木とは トライ(Trie)木というデータ構造をご存知でしょうか？ トライ木は高速な辞書の実装に使えるデータ構造です。LOUDSというデータ構造を使って実装すると，非常に少ないメモリで木を表現できるという利点があります。トライ木は例えばかな漢字変換(Google日本語入力など)において，国語辞典をメモリに保持するために用いられています。 トライ木はこんなカタチをしています。 (図はWikipediaより引用) 他の木と違うところは、木の"枝"にあたる部分にラベルが付いていることです。 これを辞書として使うにはどうすればいいでしょうか。 "in"を検索してみましょう。簡単です。i -> n とたどればいいだけです。「5」が検索結果として取り出せますね。 "inn"を検索してみましょう。今いる「5」の位置から下に動けばいいだけです。「9」が結果として取り出せます。 トライ木の特徴 高速に検
GitHub - khizmax/libcds: A C++ library of Concurrent Data Structures
The Concurrent Data Structures (CDS) library is a collection of concurrent containers that don't require external (manual) synchronization for shared access, and safe memory reclamation (SMR) algorithms like Hazard Pointer and user-space RCU that is used as an epoch-based SMR. CDS is mostly header-only template library. Only SMR core implementation is segregated to .so/.dll file. The library conta
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Programming Algorithms: Hash-Tables
Sean Law 🇨🇦 on Twitter: "I've been playing around a lot with sparse arrays and using them effectively for building local ML models. I was su… https://t.co/Y4rQ1Kiyot"
GitHub - ronomon/hash-table: Fast, reliable cuckoo hash table for Node.js.
GitHub - mariusae/ocaml-rtree: an R-tree implementation in OCaml
GitHub - nothings/single_file_libs: List of single-file C/C++ libraries.
Finger tree - Wikipedia
http://wtkw.net/tech-blog/?p=230