Software development final exam: Part 1
This is part 1 of my software development final exam. If you haven't read that introductory blog post, please go read it now. Algorithms and Data Structures Is O(2^n) equal to O(3^n)? Why? What is the expected run-time of quicksort? What is the worst-case run-time? What is the difference between a binary tree [EDIT: that should be binary search tree] and a B-tree? When and why does this difference
The Opposite of a Bloom Filter – Something Similar
A Bloom filter is a data structure that may report it contains an item that it does not (a false positive), but is guaranteed to report correctly if it contains the item (“no false negatives”). The opposite of a Bloom filter is a data structure that may report a false negative, but can never report a false positive. That is, it may claim that it has not seen an item when it has, but will never cla
Speed Hashing
06 Apr 2012 Speed Hashing Hashes are a bit like fingerprints for data. A given hash uniquely represents a file, or any arbitrary collection of data. At least in theory. This is a 128-bit MD5 hash you're looking at above, so it can represent at most 2128 unique items, or 340 trillion trillion trillion. In reality the usable space is substantially less; you can start seeing significant collisions on
Rediscovering the RSync Algorithm « Incubaid Research
Rediscovering the RSync Algorithm Posted: February 14, 2012 | Author: rslootma | Filed under: algorithms, OCaml, Programming, Uncategorized | Tags: algorithm, OCaml, optimization, Programming |Leave a comment » A:Ok, you’re synchronizing this over the web; and what do you use for the synchronization? B: Oh, we implemented the rsync algorithm. A: uhu. And what do you do with really big files? B
Fastest sort of fixed length 6 int array
Answering to another Stack Overflow question (this one) I stumbled upon an interesting sub-problem. What is the fastest way to sort an array of 6 integers? As the question is very low level: we can't assume libraries are available (and the call itself has its cost), only plain C to avoid emptying instruction pipeline (that has a very high cost) we should probably minimize branches, jumps, and ever
6.006: Introduction to Algorithms - Massachusetts Institute of Technology
Lecture 1 – Introduction & Document Distance (1 Feb 2011) notes | code | data | recitation notes | readings: 1, 3, D.1 Lecture 2 – Peak Finding (3 Feb 2011) notes | recitation notes | readings: 4.1, 4.3, D.1 Lecture 3 – Binary Search Trees (8 Feb 2011) notes | recitation notes | readings: 10.4, 12.1, 12.2, 12.3 Lecture 4 – AVL Trees (10 Feb 2011) notes | code | recitation notes | readings: 13.2, 1
Algorithms and Data Structures
This is a place to find information about some of the more fundamental algorithms used in computer science. This information is widely available on the net, but hopefully the way it's presented and discussed here will resonate with you. Most of these are things you wouldn't need to write yourself. Modern libraries and languages tend to have quality implementations for all of this. Nonetheless, I t
ハッシュライフ - Wikipedia
ハッシュライフはライフゲームないし類似したセル・オートマトンで、繰り返しパターンなどがある場合を効率的に表現したり、全盤面について1世代ずつ計算を繰り返すのではなく、影響範囲をうまく利用することで効率よく未来の状態を計算することが可能な手法である。「ハッシュ」の名の通り、ハッシュテーブルを利用した部分構造の共有が前提[1]だが、さらにメモ化を利用すれば、1世代ごとの計算の繰り返しに比べて、非常に高速に未来の世代を得ることも可能となる。初出は1980年代初期で、その頃ゼロックスパロアルト研究所の研究に参加していたビル・ゴスパーによる[2]。ゴスパーによる実装には、シンボリックスのLISPマシンと、FlavorsというLISPのオブジェクト指向拡張が用いられた。 ハッシュライフはライフゲームのバリエーションの多くで現れる多量の時間的・空間的な冗長性を活用する。例えば、ライフゲームではある程度の
A cool and practical alternative to traditional hash tables
A COOL AND PRACTICAL ALTERNATIVE TO TRADITIONAL HASH TABLES ULFAR ERLINGSSON, MARK MANASSE, FRANK MCSHERRY MICROSOFT RESEARCH – SILICON VALLEY MOUNTAIN VIEW, CALIFORNIA, USA ABSTRACT Recent advances in the theoretical literature have proposed interesting modifications to traditional hash tables. The authors of these papers propose hash tables which a) have a guaranteed constant time for a lookup b
Buckblog: Maze Generation: Algorithm Recap
The maze book for programmers! mazesforprogrammers.com Algorithms, circle mazes, hex grids, masking, weaving, braiding, 3D and 4D grids, spheres, and more! DRM-Free Ebook (Hello Minecrafters! Looking for random mazes you can build in Minecraft? Try this page I wrote. It’ll give you block-wise schematics for the maze, and will require less mental translation than the demos here.) Update (Sep 2015):
Efficient substring searching
There are many times when programmers need to search for a substring, for example when parsing text. This is commonly referred to as searching for a needle (substring) in a haystack (the string to search in). The most straightforward way to do this is by using search functions that your language provides: C: strchr()/memchr(), strstr()/memmem() C++: string::find() Ruby: String#index or regular exp
Bloom filter - Wikipedia
A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not – in other words, a query returns either "possibly in set" or "definitely not in set". Elements can be added to the set, but not removed (though this can be addresse
人材獲得作戦・４ 試験問題ほか - 人生を書き換える者すらいた。
さて試験問題です。 内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。 たとえば、S:スタート G:ゴール *:壁 $:解答の経路 としたとき、 ************************** *S* * * * * * * ************* * * * * ************ * * * * ************** *********** * * ** *********************** * * G * * * *********** * * * * ******* * * * * * ************************** という入力に対し、 ************************** *S* * $$$ * *$* *$$*$ ************
「最強最速アルゴリズマー養成講座」関連の最新 ニュース・レビュー・解説 記事 まとめ - ITmedia Keywords
最強最速アルゴリズマー養成講座： そのアルゴリズム、貪欲につき――貪欲法のススメ アルゴリズムの世界において、欲張りであることはときに有利に働くことがあります。今回は、貪欲法と呼ばれるアルゴリズムを紹介しながら、ハードな問題に挑戦してみましょう。このアルゴリズムが使えるかどうかの見極めができるようになれば、あなたの論理的思考力はかなりのレベルなのです。（2010/9/4） 最強最速アルゴリズマー養成講座： 病みつきになる「動的計画法」、その深淵に迫る 数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。（2010/5/15） 最強最速アルゴリズマー養成講座： アルゴリズマーの登
The Design of Software (CLOSED) - finding all paths in directed cyclic graph?
The Design of Software (CLOSED) A public forum for discussing the design of software, from the user interface to the code architecture. Now closed. The "Design of Software" discussion group has been merged with the main Joel on Software discussion group. The archives will remain online indefinitely. I don't care about the shortest anything. I would like to find all the paths in a directed graph th
1時間でわからせたコンシステントハッシュで仮想ノードが必要な理由 - 西尾泰和のはてなダイアリー
ConsistentHashing - コンシステント・ハッシュ法 とあるチャットで聞かれて図まで書いて解説したのでもったいないからエントリー化。ちなみにチャットが1時間弱だったのでこういうタイトルにした。 で、Bが消えるとBの責任範囲が全部Dに押し付けられてDがかわいそうでしょ。 Dの仕事が増えるでしょ。Cとか暇そうじゃん！サーバを複数用意しているメリットが薄れてる。みんなが同じくらい働くのが望ましい。 で、Bが1個の点で表現されているから「Bの手前」もDの1個だけで、そのせいで全部Dが引き受けるはめになった。つまり、仕事が細かく分割されてなくて1個の塊だから引き継ぐ人も1人だけで引き継いだ人涙目。あらかじめ仕事を100分割しとけばみんなで分担して肩代わりできて幸せだよね。 だからサーバが5個だけど点は5個じゃなくて500個打とう。それが仮想ノード。 実装はどうするの？という質問に対して
RJ のジャーナル - libketama - a consistent hashing algo for memcache clients | Last.fm
2007年 04月 11日 水曜日 02:36 We wrote ketama to replace how our memcached clients mapped keys to servers. Previously, clients mapped keys->servers like this: server = serverlist; This meant that whenever we added or removed servers from the pool, everything hashed to different servers, which effectively wiped the entire cache. We add (and sometimes remove) servers from the memcached pool often enough t
高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」
はじめに 大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するのは2003年に提案されたデータ構造、wavelet tree（以下「WT」と表記）です。WTは圧縮索引やSuccinct Data Structureなど、データをコンパクトに表現する際に重要なデータ構造です。WTは文字列T[0...n-1]が与えられた時、次の2つの操作を定数時間でサポートします。 rank(p, c)――T[0...p]中のcの出現回数を返す select(i, c)――(i+1)番目のcの位置を返す WTの作業領域量は、文字列をそのまま保存した時の約2倍程度です。 対象読者 C++の
Double-Array
ダブル配列（ Double-Array ）は， トライ（ Trie ）のデータ構造の一種であり， 小さい辞書で高速に検索できるという特長を持っています． 実際に，茶筌（ ChaSen ）や 和布蕪（ MeCab ）などの 形態素解析器で利用されているという実績があります． ダブル配列では，配列を使ってトライを表現します． 配列の各要素が BASE, CHECK という二つの整数を持つので，頭文字をとって配列 BC と呼ぶことにします． 以降の説明では，配列 BC の要素 x の BASE, CHECK を それぞれ BC[x].BASE, BC[x].CHECK と記述します． 通常，BASE, CHECK は個別の配列として紹介されますが， 特に分割して考える必要がないので，このような説明にしました． 基本的に，配列 BC の各要素は トライの節と一対一で対応します． そのため，対応する
ゲーマーでなくても仕組みぐらいは知っておきたいアルゴリズムx40
高校生の時、数学の先生がこう言いました。 ゲームなんて、開発者が作ったルールの上で遊ばれるだけだ。 と。 その時、ゲーマーな自分はこう思いました。 ゲーマーは、開発者が作ったルールの上で遊ばれたい。 と。 というわけで、普段何気なくプレイしているゲームには、どのようなルール（アルゴリズム）があるのか。それを知るために、いろいろなゲームのアルゴリズムなどを解析しているページへのリンク集を作りました。 ほとんどのゲームのアルゴリズムは正式に発表されていないので、ユーザーの手による逆解析だったり、大学の研究による真面目な考察だったりします。（リンク先には、一部アルゴリズムと呼べないものも含まれています） 各種ゲームのプログラム解析 ドラクエ、FF、ロマサガのプログラム解析 DQ調査報告書（リンク切れ） ドラクエの物理ダメージ計算式は本質的にどれも同じだが、細かい部分で微妙に違う RPG INST
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
