OpenDataStructures.jp
オープンソース版 Open Data Structures 日本語訳の PDF ファイルを以下で公開しています。最新のソースコードは GitHub のリポジトリ https://github.com/spinute にあり、適宜こちらの PDF ファイルに反映しています。 以下のものは C++ 版です（Java 版はこちら、疑似コード版はこちらにあります）。 目次 訳者まえがき 本書の読み方 訳者謝辞 なぜこの本を書いたのか 謝辞 第1章 イントロダクション 効率の必要性 インターフェース 数学的背景 計算モデル 正しさ、時間計算量、空間計算量 コードサンプル データ構造の一覧 ディスカッションと練習問題 第2章 配列を使ったリスト ArrayStack：配列を使った高速なスタック操作 FastArrayStack：最適化された ArrayStack ArrayQueue：配列を使ったキュ
Writing a damn fast hash table with tiny memory footprints - Carpe diem (Felix's blog)
Hash table is probably the most commonly used data structure in software industry. Most implementations focus on its speed instead of memory usage, yet small memory footprint has significant impact on large in-memory tables and database hash indexes. In this post, I”ll provide a step by step guide for writing a modern hash table that optimize for both speed and memory efficiency. I’ll also give so
確率的カウントアルゴリズム Morris Counting の話 - Debug me
ちゃお。舞い降り......† ハイパフォーマンスPython 作者: Micha Gorelick,Ian Ozsvald,相川愛三出版社/メーカー: オライリージャパン発売日: 2015/11/20メディア: 大型本この商品を含むブログ (3件) を見る 11/20にオライリーのHigh Performance Pythonの日本語版が出るようです。 著者のMicha Gorelickさんの紹介文がエキセントリックなことで一部で話題沸騰中な本です。(未来から来たマッドサイエンティストらしい...†) 私は先に出た英語版を読んでMorris Countingという推定カウントアルゴリズムが面白いと思ったんですけど、検索してみたら日本語だとあまりヒットしなかったので、今回はそのお話をしたいと思います。トニーモリス (有名人) の話じゃないよ〜。 さてMorris Counting [Mor
moco(beta)'s backup: [翻訳] Using Finite State Transducers in Lucene
Lucene/Solr Advent Calendar 2014 22日めです。 第15回Solr勉強会で、ごく軽くLucene FST の紹介をしたのですが、自分もまだまだ勉強中です。ということで Lucene 開発者の Mike さんに、だめもとで「ブログのFST 関連のエントリを翻訳していいですか？」とメールを送ってみたところ、「いいよ！」と快諾してもらえたので、ここに掲載します。 —- 関連する話題ですが、 Golang で書かれた形態素解析器 kagome を作っている @ikawaha さんが、Lucene を絡めて猫にもわかる（かもしれない） FST の解説を書いてくださいました。ありがとうありがとう（；ω；）！アルゴリズムの説明から Double Array との比較まで至れり尽くせりなのであわせてどうぞ。 Luceneで使われてるFSTを実装してみた（正規表現マッチ：VM
![moco(beta)'s backup: [翻訳] Using Finite State Transducers in Lucene](https://cdn-ak-scissors.b.st-hatena.com/image/square/77d318a372491738cf7b65d7f6175d3c375a4701/height=288;version=1;width=512/http%3A%2F%2Fmedia.tumblr.com%2F572c54507b5a6157d76d225cfc7fa3bf%2Ftumblr_inline_ngwt2vmr2e1qmxdmr.png)
手元に置いておくと安心できる、情報系の人向けな日本語の本のリスト - EchizenBlog-Zwei
最近、人に本を薦める事が多くなった。とりあえずこの辺を読むといいですよ的なリストを作っておくと便利だと思ったので作ることにした。 以下、「事前知識のいらない入門本」「事前知識はいらないけど本格的な本」「事前知識がないと何言ってるかわからないけど有益な情報が満載な本」の3つにわけて列挙する。 事前知識のいらない入門本 数式少なめ、脳負荷の小さめな本をいくつか。何をやるにしてもデータ構造、アルゴリズム、数学はやっておくと幸せになれるよ。 情報検索と言語処理 データマイニングとか自然言語処理とかやりたい人にはとりあえずこれ。さすがに古い話が多くなってきたのでそろそろ新しい入門用情報検索本がでないかなあと思っている。 図解・ベイズ統計「超」入門 伝説のベイジアン先生がベイズの基礎を教えてくれる本。ベイズやりたい人はこれ。 珠玉のプログラミング データ構造とかアルゴリズムとかの考え方の基礎を教えてく
Quick Post: Should you ever use Linked-Lists? | Future Chips
This question has been bugging me for the last few days. Why would anyone use a linked-list instead of arrays? I argue that linked lists have become irrelevant in the context of a modern computer system. I have asked around a few colleagues and I include their counter arguments and my rebuttal for your reference. Please point out if I am missing something. Lists have several disadvantages that did
Cache-Oblivious データ構造入門 @DSIRNLP#5
最小カットを使って「燃やす埋める問題」を解く方法について、問題とソースコードつきで、まとめました。ニコニコ生放送「TopCoderでプログラムしてみた」2000回記念放送の資料です。
一体いつからRedisがSorted Setの実装にSkip Listしか使ってないと錯覚していた？ - 愛と勇気と缶ビール
デフォルトの設定 (zset-max-ziplist-entries, zset-max-ziplist-value) では 該当するSorted Setのエントリ数が128個以下 該当するSorted Setに含まれるmember (not score) のデータ長が全て64byte以下 という2つの条件が成立している場合、Sorted Setの表現にはSkip ListではなくZip Listというデータ構造が使われる。ZADD, ZCOUNT等の実装もどちらのデータ構造を使っているかのフラグで分岐している。 Zip Listはポインタを使わずデータとそのオフセットだけで表現された双方向リストであるため、空間効率はよいが全体のサイズが大きくなるとすぐ使えなくなる。 Redisにおいては、Sorted Setへのinsertに際して上記条件のどちらかが満たされなくなった場合にZip Li
Omnichannel Content Management Platform | DAM, PIM, CMS Systems | censhare
Products Omnichannel Content Platform Combines all your marketing processes, people and content together into a single, responsive, creative unit. Product Information Management Master product data with a single source of information. Digital Asset Management Centralize digital assets to focus on the customers. Content Management Create media neutral content for any customer experience. Modules Ad
Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell
Hi there! This webpage covers the space and time Big-O complexities of common algorithms used in Computer Science. When preparing for technical interviews in the past, I found myself spending hours crawling the internet putting together the best, average, and worst case complexities for search and sorting algorithms so that I wouldn't be stumped when asked about them. Over the last few years, I
XOR連結リスト - Wikipedia
XOR連結リスト（英: XOR linked list）は、プログラミングにおけるデータ構造の一種。ビット毎の排他的論理和 (XOR) の特徴を生かして、双方向連結リストに必要なメモリ量を削減する。なお、以下ではXOR演算を ⊕ と記述する。 概要[編集] 通常の双方向連結リストは、リスト上の前後のノードのアドレスを各ノードに格納する。従って、アドレス格納フィールドを2つ必要とする。 ... A B C D E ... –> next –> next –> next –> <– prev <– prev <– prev <– XOR連結リストでは、同じ情報を1つのアドレスフィールドに圧縮する。このとき、"prev" と "next" のアドレスについてビット毎のXOR演算を行った値をそのフィールドに格納する。 ... A B C D E ... <–> A⊕C <-> B⊕D <-> C⊕
RRR: A Succinct Rank/Select Index for Bit Vectors
This blog post will give an overview of a static bitsequence data structure known as RRR, which answers arbitrary length rank queries in $\mathcal{O}(1)$ time, and provides implicit compression. As my blog is informal, I give an introduction to this structure from a birds eye view. If you want, read my thesis for a version with better markup, and follow the citations for proofs by people smarter t
Wavelet Trees: an Introduction
Today I will talk about an elegant way of answering rank queries on sequences over larger alphabets – a structure called the Wavelet Tree. In my last post I introduced a data structure called RRR, which is used to quickly answer rank queries on binary sequences, and provide implicit compression. A Wavelet Tree organises a string into a hierarchy of bit vectors. A rank query has time complexity is
Skiplists20100604
App EngineのDatastoreで正確かつ高速に順位や平均等を求めることは困難です。Datastore上にSkip Listを実装することでそれらを計算する方法を紹介します。Read less
要素の挿入、削除、ランダムアクセスが全部高速なリストを作った - kaisehのブログ
スキップリスト（Skip List）は1990年に発表された比較的新しいアルゴリズムで、要素の挿入や削除、検索を平衡木と同等のパフォーマンスで実行可能なリスト構造です。 Skip Listは連結リストの多層構成になっています。路線に例えると、最下層のリンクは各駅停車のように、全要素を結んでいます。一方、上層のリンクは急行や特急のように、途中の要素をスキップするようになっています。この路線を特急→急行→…→各駅と乗り継ぐことで、目的の要素に高速に到達できる仕組みです。もっと詳しい解説はこちらやこちらにあります。 で、ここからが本題です。Skip Listの実装はいくつも出ているんですが、Sorted Listとしての実装ばかりで、要素を任意順序で格納できてランダムアクセス（indexを指定してのアクセス）可能なSkip Listが見つからなかったので、自分で作ってみました。 通常のSkip
What are the underlying data structures used for Redis?
I'm trying to answer two questions in a definitive list: What are the underlying data structures used for Redis? And what are the main advantages/disadvantages/use cases for each type? So, I've read the Redis lists are actually implemented with linked lists. But for other types, I'm not able to dig up any information. Also, if someone were to stumble upon this question and not have a high level su
Ryan Marcus · UPenn
Ryan Marcus, assistant professor at the University of Pennsylvania. Using machine learning to build the next generation of data systems. ____ __ ___ / __ \__ ______ _____ / |/ /___ _____________ _______ / /_/ / / / / __ `/ __ \ / /|_/ / __ `/ ___/ ___/ / / / ___/ / _, _/ /_/ / /_/ / / / / / / / / /_/ / / / /__/ /_/ (__ ) /_/ |_|\__, /\__,_/_/ /_/ /_/ /_/\__,_/_/ \___/\__,_/____/ /____/ ___ __ ___
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
asmyczek/java-zipper · GitHub - Zipper data structure for Java
アルゴリズムとデータ構造
skip list