Kenyth Zeng's Library tagged algorithm → View Popular

Filter:
All
Annotated

15 Sep 09

B-tree - Wikipedia, the free encyclopedia

en.wikipedia.org/B-tree - Preview

wikipedia B-tree data-structure algorithm

a B-tree is a tree data structure that keeps data sorted and allows searches, insertions, deletions, and sequential access in logarithmic amortized time.
The B-tree is a generalization of a binary search tree in that more than two paths diverge from a single node^[1]
19 more annotations...
- the B-tree is optimized for systems that read and write large blocks of data.
- In order to maintain the pre-defined range, internal nodes may be joined or split.
- Each split node has the required minimum number of keys.
- A B-tree is kept balanced by requiring that all leaf nodes are at the same depth.
- B-trees have substantial advantages over alternative implementations when node access times far exceed access times within nodes.
- practical B-trees using secondary storage want a large number of child nodes to improve performance.
- In the narrow sense, a B-tree stores keys in its internal nodes but need not store those keys in the records at the leaves.
- B⁺-tree and the B^*-tree. In the B⁺-tree
- Rudolf Bayer and Ed McCreight invented the B-tree while working at Boeing in 1971^[3]
- Usually, sorting and searching algorithms have been characterized by the number of comparison operations that must be performed using order notation.
- The time to read a record on a disk drive can dominate the time needed to compare keys once the record is available.
- Inserting a record before the first record in the file requires shifting all of the records down one.
- A B-tree of order m (the maximum number of children for each node) is a tree which satisfies the following properties:
  
  Every node has at most m children.
  Every node (except root and leaves) has at least ^m⁄₂ children.
  The root has at least two children if it is not a leaf node.
  All leaves appear in the same level, and carry information.
  A non-leaf node with k children contains k–1 keys.
- This relationship between U and L implies that two half-full nodes can be joined to make a legal node, and one full node can be split into two legal nodes
- A B-tree of depth n+1 can hold about U times as many items as a B-tree of depth n,
- Insert the separation value in the node's parent
- If the splitting goes all the way up to the root, it creates a new root with a single separator value and two children
- the most efficient way to construct the initial B-tree is not to insert every element in the initial collection successively, but instead to construct the initial set of leaf nodes directly from the input, then build the internal nodes from these.
- The B-tree is also used in filesystems to allow quick random access to an arbitrary block in a particular file.

11 Sep 09

Deterministic algorithm - Wikipedia, the free encyclopedia

en.wikipedia.org/...Deterministic_algorithm - Preview

computer math wikipedia algorithm

In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. Given a particular input, it will always produce the same output, and the underlying machine will always pass through the same sequence of states.
One simple model for deterministic algorithms is the mathematical function

04 Sep 09

Algorithm Education in Python

www.ece.uci.edu/...python.html - Preview

algorithm python article introduction education

Unfortunately, the use of traditional programming languages forces students to deal with details of data structures and supporting routines, rather than algorithm design. Python represents an algorithm-oriented language that has been sorely needed in education.
. One reason is that these languages require declaration of global variables, local variables, and parameters before they can be used. Another reason, more importantly, is that many data structures such as lists, linked data structures, and specialized arrays must be designed and implemented to support the algorithm
3 more annotations...
- Python provides the fundamental data structures such as lists, tuples, and dictionaries
- extensible to arbitrary data types
- We start with sorting algorithms and heapsort with priority queues to highlight memory management issues. Then, we use them to build binary trees and implement the Huffman compression algorithm. Finally, we show how Python can be used effectively for graph algorithms.

17 Aug 09

Encoding - Protocol Buffers - Google Code

code.google.com/...encoding.html - Preview

encoding algorithm format protobuf doc

The binary version of a message just uses the field's number as the key – the name and declared type for each field can only be determined on the decoding end by referencing the message type's definition (i.e. the .proto file).

27 Jul 09

Binary tree - Wikipedia, the free encyclopedia

en.wikipedia.org/Binary_tree - Preview

wikipedia algorithm data-structure

- The number of nodes $n$ in a perfect binary tree can be found using this formula: $n = 2 h + 1 - 1$ where $h$ is the height of the tree.
- The number of nodes $n$ in a complete binary tree is minimum: $n = 2 h$ and maximum: $n = 2 h + 1 - 1$ where $h$ is the height of the tree.
- The number of nodes $n$ in a perfect binary tree can also be found using this formula: $n = 2 L - 1$ where $L$ is the number of leaf nodes in the tree.
- The number of leaf nodes $n$ in a perfect binary tree can be found using this formula: $n = 2 h$ where $h$ is the height of the tree.
- The number of NULL links in a Complete Binary Tree of n-node is (n+1).
- The number of leaf node in a Complete Binary Tree of n-node is $U p p e r B o u n d (n / 2)$ .
- For any non-empty binary tree with n₀ leaf nodes and n₂ nodes of degree 2, n₀ = n₂ + 1.^[1]
In depth-first order, we always attempt to visit the node farthest from the root that we can, but with the caveat that it must be a child of a node we have already visited.

24 Jul 09

Quicksort - Wikipedia, the free encyclopedia

en.wikipedia.org/Quicksort - Preview

algorithm wikipedia sorting toread

QuickSort.java

www.cs.princeton.edu/...QuickSort.java.html - Preview

algorithm sorting code sample java

09 Jul 09

Unqualified Reservations: Wolfram Alpha and hubristic user interfaces

unqualified-reservations.blogspot.com/...-alpha-and-hubristic-user.html - Preview

Wolfram-Alpha search UI review analysis algorithm

29 May 09

谷歌浏览器里牛逼的中文分词

initiative.yo2.cn/640309 - Preview

search algorithm chrome opensource Chinese starred 分词

今天突然发现谷歌浏览器（chrome/chromium）居然实现了中文词语之间的跳转
深入研究了一下这个有趣的功能，发现是IBM的ICU库提供的，每个Chrome安装文件夹下面都有一个icudt38.dll，这里面包含了一份中文词语表。

28 May 09

bzip2 - Wikipedia, the free encyclopedia

en.wikipedia.org/Bzip2 - Preview

algorithm compression bzip2 magic

.magic:16 = 'BZ' signature/magic number

27 May 09

Public-key cryptography - Wikipedia, the free encyclopedia

en.wikipedia.org/...Public-key_cryptography - Preview

wikipedia algorithm encryption

do not require a secure initial exchange of one or more secret keys as is required when using in symmetric key algorithms.
7 more annotations...
- can also be used to create digital signatures.
- Transport Layer Security (TLS) (successor to SSL), PGP and GPG.
- The distinguishing technique used in public key-private key cryptography is use of asymmetric key algorithms because the key used to encrypt a message is not the same as the key used to decrypt it.
- the discovery of such algorithms which revolutionized the practice of cryptography beginning in the middle 1970s.

Memcache Hash算法值得探索的内容 - 西湖边的穷秀才-文初 - BlogJava

www.blogjava.net/...221906.html - Preview

memcached algorithm distributed

存储数据如何均匀分散。如何把数据尽可能的散开存储，这样对于Memcache的可扩展性才会有充分利用

技术文摘: 字符串hash算法比较

blog.iyi.cn/...post_2.html - Preview

algorithm comparison performance

链表查找的时间效率为O(N)，二分法为log2N，B+ Tree为log2N，但Hash链表查找的时间效率为O(1)。

17 May 09

Solidot | 开源方案打破世界数据排序记录

developers.solidot.org/article.pl - Preview

news Hadoop distributed algorithm

30 Apr 09

MapReduce - Wikipedia, the free encyclopedia

en.wikipedia.org/MapReduce - Preview

distributed algorithm wikipedia scalability Google

The framework is inspired by map and reduce functions commonly used in functional programming,^[2]
Map takes one pair of data with a type on a data domain, and returns a list of pairs in a different domain:

Map(k1,v1) -> list(k2,v2)
7 more annotations...
- ct to data stru
- defined with respect to data structured in (key, value) pairs.
- the MapReduce framework collects all pairs with the same key from all lists and groups them together, thus creating one group for each one of the different generated keys.
- The Reduce function is then applied in parallel to each group, which in turn produces a collection of values in the same domain:
  
  Reduce(k2, list (v2)) -> list(v2)
- This behavior is different from the functional programming map and reduce combination, which accepts a list of arbitrary values and returns one single value that combines all the values returned by map.
- count the appearances of each different word in a set of documents
- each document is split in words, and each word is counted initially with a "1" value by the Map function, using the word as the result key. The framework puts together all the pairs with the same key and feeds them to the same call to Reduce, thus this function just needs to sum all of its input values to find the total appearances of that word.