George's dev dream port
sunwinner · 共 106 篇文章
This blog stop updating, please go to http://codethoughts.info
本博客停止更新,新博文将发表于 http://codethoughts.info 欢迎订阅。 -------------------------------------------------------------------------------------------- This blog stop updating now, please subscribe http://codethoughts.info for the latest blog posts.
2015-04-04T11:43:48Z · 非技术 · 评论(0)
基础数据结构和算法十四:Directed Graphs
In directed graphs, edges are one-way: the pair of vertices that defines each edge is an ordered pair that specifies a one-way adjacency. Many applications (for example, graphs that represent the web, scheduling constraints, or telephone calls) are naturally expressed in terms of directed graphs. T…
2013-12-15T22:40:30Z · 编程语言 · 评论(0)
基础数据结构和算法十三:Undirected Graphs (2)
Design pattern for graph processing. Since we consider a large number of graph-processing algorithms, our initial design goal is to decouple our implementations from the graph representation. To do so, we develop, for each given task, a task-specific class so that clients can create objects to perf…
2013-12-13T22:51:29Z · 编程语言 · 评论(0)
基础数据结构和算法十三:Undirected Graphs
A graph is a set of vertices and a collection of edges that each connect a pair of vertices. Vertex names are not important to the definition, but we need a way to refer to vertices. By convention, we use the names 0 through V-1 for the vertices in a V-vertex graph. Glossary A substantial amount of…
2013-12-13T20:15:59Z · 编程语言 · 评论(0)
Ruby array slicing - weird behavior
If you play around array slicing in irb, it will behavior like below: irb(main):027:0> a = [1,2,3] => [1, 2, 3] irb(main):028:0> a[2,1] => [3] irb(main):029:0> a[4,1] => nil irb(main):030:0> a[3,1] => [] The weird behavior is that sometimes it return empty array, and sometimes it return nil instead…
2013-12-12T09:42:43Z · 编程语言 · 评论(0)
Ruby中Enumerable#inject用法示范
Enumerable#inject是Ruby核心库中的一个简洁而且强大的API,今天读到一段简洁的代码之后,对这个API产生了浓厚的兴趣,索性搜寻一下资料,总结一下它的用法。 代码如下: def text_at(*args) args.inject(@feed) { |s, r| s.send(:at, r)}.inner_text end 这段代码完成的功能是:取出XML文件中某子元素的文本内容,它是用nokogiri库来完成这个功能的。关于Nokogiri库API(at(), inner_text())的细节我们不谈,只是用这段代码来引起你对inject的兴趣,现在我们来看inject的…
2013-12-06T17:36:50Z · 编程语言 · 评论(0)
Trapped by String#split of Ruby
Today I was trapped by kind of wierd behavior of Ruby's String#split, here's an example: def parse_inline_styles(text) segments = text.split(%r{(</?.*?>)}).reject {|x| x.empty?} segments.size == 1 ? segments.first : segments end This code snippet parse text string by <b>, </b>, <i>,</i>, which is s…
2013-12-05T18:33:21Z · 编程语言 · 评论(0)
基础数据结构和算法十二:Hash table
Search algorithms that use hashing consist of two separate parts. The first part is to compute a hash function that transforms the search key into an array index. Ideally, different keys would map to different indices. This ideal is generally beyond our reach, so we have to face the possibility tha…
2013-12-02T22:06:01Z · 编程语言 · 评论(0)
基础数据结构和算法十一:Red-black binary search tree
The insertion algorithm for 2-3 trees just described is not difficult to understand; now, we will see that it is also not difficult to implement. We will consider a simple representation known as a red-black BST that leads to a natural implementation. Encoding 3-nodes. The basic idea behind red-bla…
2013-12-01T12:12:35Z · 编程语言 · 评论(0)
基础数据结构和算法十:2-3 search tree
Binary search tree works well for a wide variety of applications, but they have poor worst-case performance. Now we introduce a type of binary search tree where costs are guaranteed to be logarithmic, no matter what sequence of keys is used to construct them. Ideally, we would like to keep our bina…
2013-11-30T11:07:02Z · 编程语言 · 评论(0)
基础数据结构和算法九:Binary Search Tree
A binary search tree (BST) is a binary tree where each node has a Comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node’s left subtree and smaller than the keys in all nodes in that node’s right subtree. Rep…
2013-11-28T22:39:46Z · 编程语言 · 评论(0)
基础数据结构和算法八:Binary search
Binary search needs an ordered array so that it can use array indexing to dramatically reduce the number of compares required for each search, using the classic and venerable binary search algorithm. We maintain indices into the sorted key array that delimit the subar- ray that might contain the se…
2013-11-28T21:21:41Z · 编程语言 · 评论(0)
基础数据结构和算法七:Priority queue & Heap sort
Some important applications of priority queues include simulation systems, where the keys correspond to event times, to be processed in chronological order; job scheduling, where the keys correspond to priorities indicating which tasks are to be performed first; and numerical computations, where th…
2013-11-27T19:47:59Z · 编程语言 · 评论(0)
基础数据结构和算法六:Quick sort
Quick sort is probably used more widely than any other. It is popular because it is not difficult to implement, works well for a variety of different kinds of input data, and is substantially faster than any other sorting method in typical applications. The quicksort algorithm’s desirable features …
2013-11-21T19:33:14Z · 编程语言 · 评论(0)
基础数据结构和算法五:Merge sort
One of mergesort’s most attractive properties is that it guarantees to sort any array of N items in time proportional to N * log N. Its prime disadvantage is that it uses extra space proportional to N. Top-down mergesort It is one of the best-known examples of the utility of the divide-and-conquer …
2013-11-20T21:44:40Z · 编程语言 · 评论(0)