CWYAlpha

Just another WordPress.com site

Archive for 七月 2012

Thought this was cool: 数据结构重读 – 哈希表

leave a comment »

无论是折半查找、二叉排序树查找还是B树,性能都依赖于查找中的比较次数。

一种理想情况是不经过任何比较,一次直接定位索要查找的记录,即:若数据结构中存在关键字和K相等,则其必定在f(K)的存储位置上,我们称这个对应关系f为哈希函数

冲突(Collision):对不同的关键字,可能得到同一哈希地址,即存在key1!=key2,但f(key1)=f(key2)。此时称为冲突或碰撞。

由于在实际应用中,哈希函数都是压缩函数,所以冲突只能尽可能的减少,很难完全避免。

哈希表:根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的连续地址集合(区间)上,并以关键字在地址集合中的“像”作为记录在表中的位置,这种表称为哈希表,这一映像过程称为哈希造表或散列。所得的存储位置称为哈希地址或散列地址。

常见的哈希函数构造方法:

(1) 直接定址,如H(key) = a*key + b,如统计每个年龄的用户数。
(2) 数字分析,根据数据特点,取某一位或某几位叠加。
(3) 平方取中,取关键字平方后的中间几位(或平方)为哈希地址。
(4) 折叠法,将关键字纷呈几部分,然后每一部分的叠加和作为哈希地址。
(5) 除数余留法,取关键字被某个不大于哈希表长度的m的数p除后的余数,即算模 H(key) = key mod p。p的选择很重要,一般选质数或不包含小于20的质数因子的合数。
(6) 随机数法,利用伪随机特性,使用key作为种子,得到的随机数作为哈希地址。这个真有,比如Hadoop中某个Hash函数。

以上都是书上很陈旧的内容了,更为现代化的Hash函数请移步Wikipedia,List of Hash Functions

我个人认为几个比较给力的是:BKDR(用于英文单词)、MurmerHash(速度最快的,针对X86优化CPU运算,基本纯位操作),据说Goog开发了CityHash也是借鉴MurmerHash,不知道效果怎么样。

下面说说处理冲突的方法:

(1) 开放定址法,H = (H(key)+d) mode m,其中d是发现冲突后,每次的增量。若d=1,2….则称作线性探测再散列;若d=1, -1, 4, -4….则叫做二次探测再散列;d也可以是随机数,称为随机探测再散列。注意,二次探测再散列只能在m=4j+3时才能使用

(2) 再哈希法:H = RH(key)
(3) 链地址法:将所有关键字为同一词的记录存储再同一线性链表中,拉链,如下图所示。
(4) 建立公共溢出区,不管哈希地址是什么,一旦发生冲突,都填入溢出表。个人觉得这个也很靠谱。

下面用Java实现了一个简单的哈希表,Hash函数是平方取模,冲突处理是线性探测再散列,使用cap=0.75判断是否需要重哈希,以减少冲突。

代码如下:

import java.util.ArrayList;
import java.util.Arrays;

public class HashTable {

	public HashTable() {
		// default capbility
		cap = 10;
		// default cnt
		cnt = 0;
		// default size
		ht = new int[cap];
		Arrays.fill(ht, Integer.MAX_VALUE);
		// default load factor
		lf = 0.75;
	}

	private int FindPos(int key) {
		int pos = Hash(key);
		while (ht[pos] != Integer.MAX_VALUE && ht[pos] != key) {
			pos = (pos + 1) % cap; // 线性探测再散列
		}
		if (ht[pos] == key) {
			return -1;
		} else {
			return pos;
		}
	}

	private int Hash(int key) {
		// A very simple & bad hash function
		return (key * key) % cap;
	}

	private void ReHash() {
		// System.out.println("Rehash");
		// Simple * 2
		int[] ht_old = ht;
		cap *= 2;
		ht = new int[cap];
		Arrays.fill(ht, Integer.MAX_VALUE);
		// Rehash all old key
		for (int k : ht_old) {
			if (k != Integer.MAX_VALUE) {
				Insert(k);
			}
		}
	}

	public boolean Insert(int key) {
		int pos = FindPos(key);
		if (pos == -1) {
			// Already in hash table
			return false;
		} else {
			// Add to hash table
			ht[pos] = key;
			cnt++;
			// Check if need to rehash
			if ((double) cnt / cap > lf) {
				ReHash();
			}
			return true;
		}
	}

	public boolean Find(int key) {
		int pos = FindPos(key);
		if (pos == -1) {
			return true;
		} else {
			return false;
		}
	}

	/* Hash Table */
	private int[] ht = null;
	/* Load factor */
	private double lf;
	/* Capbility */
	private int cap;
	/* Cnt for actual elems */
	private int cnt;

	public static void main(String[] args) {
		HashTable ht = new HashTable();
		for (int i = 0; i < 100; i++) {
			ht.Insert(i);
		}
		System.out.println(ht.Find(99));
	}
}

 
from 四号程序员四号程序员: http://www.coder4.com/archives/3590

Advertisements

Written by cwyalpha

七月 31, 2012 at 4:58 下午

发表在 Uncategorized

Thought this was cool: 关于头文件和命名空间

leave a comment »

iostream

iostream 的意思是 输入输出流
直接点说就是in(输入) out(输出) stream(流)
取 in out 的首字母与 stream 合成

 

C++语言中

#include<iostream>是标准的C++头文件,任何符合标准的C++开发环境都有这个头文件。

  在旧的标准C++中,使用#include<iostream.h>

  但在新标准中,用#include<iostream>,而且在VS中编程的同时要注意要添加:

  using namespace std;

  using namespace std详解

  一 :

  <iostream>和<iostream.h>是不一样,前者没有后缀,实际上,在你的编译器include文件夹里面可以看到,二者是两个文件,打开文件就会发现,里面的代码是不一样的。

  后缀为.h的头文件c++标准已经明确提出不支持了,早些的实现将标准库功能定义在全局空间里,声明在带.h后缀的头文件里,c++标准为了和C区别开,也为了正确使用命名空间,规定头文件不使用后缀.h。

  因此,当使用<iostream.h>时,相当于在c中调用库函数,使用的是全局命名空间,也就是早期的c++实现;当使用<iostream>的时候,该头文件没有定义全局命名空间,必须使用namespace std;这样才能正确使用cout。

  二:

  所谓namespace,是指标识符的各种可见范围。

  C++标准程序库中的所有标识符都被定义于一个名为std的namespace中。

  由于namespace的概念,使用C++标准程序库的任何标识符时,可以有三种选择:

  1、直接指定标识符。例如std::ostream而不是ostream。完整语句如下:

  std::cout << std::hex << 3.4 << std::endl;

  2、使用using关键字。

  using std::cout;

  using std::endl;

  以上程序可以写成

  cout << std::hex << 3.4 << endl;

  3、最方便的就是使用using namespace std;

  例如:

  #include <iostream>

  #include <sstream>

  #include <string>

  using namespace std;

  这样命名空间std内定义的所有标识符都有效(曝光)。就好像它们被声明为全局变量一样。那么以上语句可以如下写:

  cout << hex << 3.4 << endl;

  因为标准库非常的庞大,所程序员在选择的类的名称或函数名时就很有可能和标准库中的某个名字相同。所以为了避免这种情况所造成的名字冲突,就把标准库中的一切都被放在名字空间std中。但这又会带来了一个新问题。无数原有的C++代码都依赖于使用了多年的伪标准库中的功能,他们都是在全局空间下的。

  所以就有了<iostream.h>和<iostream>等等这样的头文件,一个是为了兼容以前的C++代码,一个是为了支持新的标准。

  命名空间std封装的是标准程序库的名称,标准程序库为了和以前的头文件区别,一般不加”.h”

 

trackback:http://blog.csdn.net/shunshine988/article/details/4283990

本文链接

from 博客园_业精于勤,荒于嬉;行成于思,毁于随: http://www.cnblogs.com/hnrainll/archive/2012/07/31/2616615.html

Written by cwyalpha

七月 31, 2012 at 11:53 上午

发表在 Uncategorized

Thought this was cool: Real-time Compressive Tracking

leave a comment »

感谢香港理工大学的Kaihua Zhang,这是他即将在ECCV 2012上出现的paper:Real-time Compressive Tracking。 这里是他的介绍:

一种简单高效地基于压缩感知的跟踪算法。首先利用符合压缩感知RIP条件的随机感知矩对多尺度图像特征进行降维,然后在降维后的特征上采用简单的朴素贝叶斯分类器进行分类。该跟踪算法非常简单,但是实验结果很鲁棒,速度大概能到达40帧/秒。具体原理分析可参照相关文章。

链接

视频:

欢迎大家将自己的论文发到 Cvchina上和大家分享。。。。

Tags: ,

from 增强视觉 | 计算机视觉 增强现实: http://www.cvchina.info/2012/07/31/real-time-compressive-tracking/

Written by cwyalpha

七月 31, 2012 at 10:23 上午

发表在 Uncategorized

Thought this was cool: 用igraph包探索世界航空网络

leave a comment »

本文使用的数据仍然是上篇博文中用到的世界航班数据,不过本例不再仅限于中国国内航班。如果用社交网络的角度来观察数据,一个机场可以看作是一个人,而机场之间的来往航班可以看作是人与人之间的某种联系。整体世界的航线可以看作是一个社交网络。那么用R语言的igraph包来简单探索一下这个社交网络,看能不能得到什么发现。

# 仍然是上一篇博文的数据 
data.port <- read.csv('d:/airports.dat',F)
data.line <- read.csv('d:/routes.dat',F)
 
# 机场数据整理,除去重复的和没有编号的机场
airports <-data.port[data.port$V5!='',
c('V5','V4','V3')]
names(airports) <- c('name','country','city')
airports$city <- as.character(airports$city)
airports <- airports[!duplicated(airports$name),]
 
# 航线数据整理,只保留起飞和降落地点
goodlines <- (data.line[,'V3'] %in% airports$name) &
(data.line[,'V5'] %in% airports$name)
airlines <- data.line[goodlines,c('V3','V5')]
names(airlines) <- c('from','to')
 
# 加载igraph包,生成网络图对象
library(igraph)
g <- graph.data.frame(airlines, vertices=airports,directed=F)
# 删除没有航线的机场
g<- g - V(g)[degree(g)==0]
 
# 合并航线,将同一航线的频次放入weight属性
is.multiple(g)
E(g)$weight <- count.multiple(g)
g1 <- simplify(g, remove.multiple = TRUE, remove.loops = TRUE,
edge.attr.comb = 'mean')
summary(g1)
 
# 从上面观察整个机场群共有3218个机场,16822条航线,来判断这些机场整体是否连通?
is.connected(g1)
# 存在一些不能连通的机场,观察有哪些相互断开的机场群?
clusters(g1)$csize
V(g1)[clusters(g1)$membership==2]$country
# 发现有一些机场属于西南太平洋上的岛国,去掉这些处于边缘状态的机场
g2 <- g1 - V(g1)[clusters(g1)$membership!=1]
 
# 观察哪一对机场之间航班频次最多,原来是香港和曼谷,它们之间的航班达到28次,果然是有基情。
E(g2)[which.max(E(g2)$weight)]
V(g2)['BKK']$city
V(g2)['HKG']$city
 
# 哪个机场的直航城市最多,法兰克福位于首位,它与237个机场间有直飞航班。从下面的分布图来看,大部分机场的直航城市并不多,只有少数机场特别突出,我们还可以列出直航城市最多的十大机场。
V(g2)[which.max(degree(g2))]$city
plot(degree.distribution(g2), log="xy")
V(g2)$city[order(degree(g2),decreasing=T)][1:10]
 Google使用的PageRank值代表了一个网站的重要性。PageRank根据网页之间的超链接来确定一个页面的等级。那么机场的重要性也可以从航线的多寡来确定。 根据pagerank计算出机场前十强,分别是"Chicago" "Denver" "Los Angeles" "Houston"  "London" "Frankfurt" "Paris"  "Beijing" "Singapore" "Bangkok" 
V(g2)$city[order(page.rank(g2)$vector,decreasing=T)][1:10]
 
# 观察两个机场之间是否连通直航,这里判断的是武汉到开罗,结果是否
are.connected(g2,'WUH','CAI')
 
# 那么应当如何转机呢,这实际上是寻找网络中的最短连线wuhan->cairo,给出的结果是先从武汉到东京,再到莫斯科,最后到开罗。
V(g2)[get.shortest.paths(g2,'WUH','CAI')[[1]]]$city
 
# 还可以使用网络分析方法中的社群探测,发现网络中有三个主要的社群,观察社群特征,它们分别对应了美洲,欧洲与中东地区,亚太地区
commu <- fastgreedy.community(g2)
commu$membership
sizes(commu)
V(g2)[commu$membership==1]$country
V(g2)[commu$membership==2]$country
V(g2)[commu$membership==3]$country

from 数据科学与R语言: http://xccds1977.blogspot.com/2012/07/blog-post_31.html

Written by cwyalpha

七月 31, 2012 at 5:08 上午

发表在 Uncategorized

Thought this was cool: 像写函数式语言代码一样写C++

leave a comment »

忘记最早接触函数式编程语言是什么时候了,也忘记接触的第一门函数式语言是哪一门。断断续续接触过好几种函数式语言(当然都算不纯的,ruby/lisp不算纯吧),这些语言的思想在潜移默化中多多少少对我有所影响。

我是个C++程序员,我不知道我平时写的都是些什么代码。最让人印象深刻就是我会经常写遍历STL容器的代码,是经常,这样的遍历你可能也不陌生:

for (ListType::iterator it = con.begin(); it != con.end(); ++it) {
    something
}

或者针对std::map/set等的查找:

Table::iterator it = table.find(key);
if (it == table.end())
    do-something
do-something

多亏STL接口的一致性,这让我们写出了很多“一致性“代码。慢慢地我觉得恶心,不禁想起函数式编程语言中,对于这种需求一般都会提供类似的接口:

con.map(function (it) if (it->some-filed == some-value) return something end)
# 或者
con.each do |it| if it.some-filed == some-value then return something end end
# 或者
(con.map (lambda (it) (if ((= it.some-filed some-value)) (return something))))

(好吧,lisp我又忘了)总之,这种针对容器的遍历操作,都会成为一种内置接口,并且通过lambda来让用户直接编写处理代码,少去写循环的冗余。然后,我写了类似下面的一组宏(随手敲的不保证能运行):

#define IT_N __it

#define TRAVERSE_MAP(type, map, exps) \
    for (type::iterator IT_N = map.begin(); IT_N != map.end(); ++IT_N) { \
        exps; \
    }
#define I_KEY (IT_N->first)
#define I_VALUE (IT_N->second)

#define TRAVERSE_LIST(type, list, exps) \
    for (type::iterator IT_N = list.begin(); IT_N != list.end(); ++IT_N) { \
        exps; \
    }
#define L_VALUE (*IT_N)

#define FIDN_MAP_ITEM(type, map, key, fexps, texps) \
    do { \
        type::iterator IT_N = map.find(key); \
        if (IT_N == map.end()) { \
            fexps; \
        } else { \
            texps; \
        } \
    } while(0)

#define VAL_N __val
#define FIND_LIST_ITEM_IF(type, list, cmp, fexps, texps) \
    do { \
        struct Comp { \
            bool operator() (const type::value_type &VAL_N) const { \
                return cmp; \
            } \
        }; \
        type::iterator IT_N = std::find_if(list.begin(), list.end(), Comp()); \
        if (IT_N != list.end()) { \
            texps; \
        } else { \
            fexps; \
        } \
    } while(0)

#define NULL_EXP ;

当然,以上接口都还包含一些const版本,用于const容器的使用。使用的时候(截取的项目中的使用例子):

TRAVERSE_MAP(TimerTable, m_timers, 
        I_VALUE.obj->OnTimerCancel(I_KEY, I_VALUE.arg);
        TIMER_CANCEL(I_VALUE.id)); 

TRAVERSE_LIST(AreaList, areas,
        ids.push_back(L_VALUE->ID()));

FIND_MAP_ITEM(PropertyTable, m_properties, name,
        LogWarn("set a non-existed property %s", name.c_str()); return NIL_VALUE,
        if (val.Type() != I_VALUE.type()) {
            return NIL_VALUE; 
        } else {
            GValue old = I_VALUE;
            I_VALUE = val; 
            return old;
        });

多亏了C/C++宏对一切内容的可容纳性,可以让我往宏参数里塞进像if这种复合语句,甚至多条语句(例如最后一个例子)。这些宏我使用了一段时间,开始觉得挺爽,很多函数的实现里,我再也不用写那些重复的代码了。但是后来我发觉这些代码越来越恶心了。最大的弊端在于不可调试,我只能将断点下到更深的代码层;然后就是看起来特不直观,连作者自己都看得觉得不直观了,可想而知那些连函数式编程语言都不知道是什么的C++程序员看到这些代码会是什么心情(可以想象哥已经被诅咒了多少次)。

函数式语言让人写出更短的代码,这一点也对我有影响,例如我最近又写下了一些邪恶代码:

// split a string into several sub strings by a split character i.e:
// "a;b;c;" => "a", "b", "c"
// "a;b;c" => "a", "b", "c"
std::vector<std::string> SplitString(const std::string &str, char split) {
    std::vector<std::string> ret;
    size_t last = 0;
    for (size_t pos = str.find(split); pos != std::string::npos; last = pos + 1, pos = str.find(split, last)) {
        ret.push_back(str.substr(last, pos - last));
    }
    return last < str.length() ? ret.push_back(str.substr(last)) : 0, ret;
}

恶心的就是最后那条return语句,因为我需要处理”a;b;c”这种c后面没加分隔符的情况,但我并不愿意为了这个需求再写一个会占超过一行的if语句。因为,我太喜欢ruby里的if了:

do-something if exp

也就是ruby里允许这种只有一行if的代码将if放在其后并作为一条语句。我的不愿意其实是有理由的,在c/c++中有太多只有一行条件体的if语句,对这些语句参合进编程风格/可读性进来后,就不得不让你写出不安的代码,例如:

if (something) return something; // 某些编程风格里不允许这样做,因为它不方便调试

if (something) 
    return something; // 某些风格里又有大括号的统一要求

if (something) {
    return something; // 就算符合风格了,但这一条语句就得多个大括号
}

if (something) 
{
    return something; // 某些风格里这大括号就更奢侈了
}

这个return除了乍看上去有点纠结外,其实也不算什么大问题,但是那个问号表达式返回的0实在没有任何意义,而正是没有意义才会让它误导人。本来我是可以写成:

return last < str.length() && ret.push_back(str.substr(last)), ret;

这样利用条件表达式的短路运算,代码也清晰多了。但是,std::vector::push_back是一个没有返回值的函数,所以。

全文完。

原文地址:http://codemacro.com/2012/07/30/write-cpp-like-fp/

written byKevin Lynx posted athttp://codemacro.com


0

   

0

IT 牛人博客聚合网站(udpwork.com) 聚合
|
评论: 0
|
10000+ 本编程/Linux PDF/CHM 电子书下载

from IT牛人博客聚合网站: http://www.udpwork.com/item/7843.html

Written by cwyalpha

七月 31, 2012 at 5:08 上午

发表在 Uncategorized

Thought this was cool: 算法届的十位牛人

leave a comment »

·Don E. Knuth
伟大的智者——Don E.Knuth,中文名:高德纳(1938-)算法和程序设计技术的先驱者。Oh,God!一些国外网站这样评价他。一般说来,不知道此人的程序员是不可原谅的。其经典著作《计算机程序设计艺术》更是被誉为算法中“真正”的圣经,像KMPLR(K)这样令人不可思议的算法,在此书比比皆是。难怪连Bill Gates都说:“如果能做对书里所有的习题,就直接来微软上班吧!”
对于Don E.Knuth本人,一生中获得的奖项和荣誉不计其数,包括图灵奖,美国国家科学金奖,美国数学学会斯蒂尔将(AMS Steel Prize),以及发明先进技术荣获的极受尊重的京都奖(KyotoPrize)等等,写过19部书和160余篇论文,每一篇著作都能用影响深远来形容。Don E.Knuth也被公认是美国最聪明的人之一。当年他上大学的时候,常写些各种各样的编译器来挣外快,只要是他参加的编程比赛,总是第一名,同时也是世上少有的编程达到40年以上的程序员之一。他除了是技术与科学上的泰斗外,更是无可非议的写作高手,技术文章堪称一绝,文风细腻,讲解透彻,思路清晰而且没有学究气,估计这也是《计算机程序设计艺术》被称为圣经的原因之一。

·Edsger Wybe Dijkstra
谦逊的长者——Edsger Wybe Dijkstra1930年出生于荷兰阿姆斯特丹,2002年逝世于荷兰纽南。他在祖国荷兰获得数据和物理学学士,理论物理博士学位,2000年退休前一直是美国Texas大学的计算机科学和数学教授。以发现了图论中的最短路径算法(Dijkstra算法)而闻名于世,1972年因为ALGOL第二代编程语言而获得图灵奖。“Go To Statement Considered Harmful(EWD215)也是被广为传颂的经典之作。除了科学研究之外,他最喜欢做的事情就是教学,被人称作“一天教学24小时”的教授。
且不说Dijkstra算法对计算科学,网络科学发展的深远影响,单从他在1972年获得图灵奖时的演讲“The Humble Programmer”就不得不肃然起敬,在获得计算机科学中至高无上的奖项时,Edgs Wybe Dijkstra仍然称自己不过是一个谦逊普通的程序员,何等胸襟,举世之中几人可比。

·George Dantzig
运筹学大师——George Dantzig可谓是由父亲一手培养出的天才。George的父亲是俄国人,曾在法国师从著名的科学家Henri Poincar e。他曾经这样回忆自己的父亲:“在我还是个中学生时,他就让我做几千道几何题……解决这些问题的大脑训练是父亲给我的最好礼物。这些几何题,在发展我分析能力的过程中,起了最最重要的作用。”
在伯克利学习的时候,有一天George上课迟到,只看到黑板上写着两个问题,他只当是课堂作业,随即将问题抄下来并做出解答。六个月后,这门课的老师——著名的统计学家Jerzy Neyman——帮助他把答案整理了一下,发表为论文,George这才发现自己解决了统计学领域中一直悬而未决的两个难题。
George
后来在运筹学建树极高,获得了包括“冯诺伊曼理论奖”在内的诸多奖项。他在Linear programming and extensions一书中研究了线性编程模型,为计算机语言的发展做出了不可磨灭的贡献。天妒英才,他于2005513去世。

·James Cooley
推动时代前进的人——James Cooley(1926-)美国数学家,哥伦比亚大学的数学博士,以他所创造的快速傅立叶变换(FFT)而著名,不能不说是意义极其重大,FFT的数学意义不光在于使大家明白了傅立叶(Fourier)变换计算起来是多么容易,而且使得数字信号处理技术取得了突破性的进展,对于现在的网络通信,图形图像处理等等领域的发展与前进奠定了基
础。Fourier变化的意义在于将电能变为了工业的命脉,而FFT的意义更是在于他推动了整个社会信息化的进程。在IBM研究中心中主要从事数字信号处理的研究一直到1992年退休,同时他还是IEEE的数字信号处理委员会的成员。1980年获得ASSP’s Meritorious Service Award,1984年获得ASSP Society Award以及IEEE Centennial Medal

·John Backus
FORTRAN之父——John Backus早年在Hill School学习的时候因为讨厌学习,成绩一踏糊涂而不得不在暑假补课。1943年他在父亲的要求下到维吉尼亚大学学习化学,随后参军、照顾头部受伤的伤员、在医学学校学习治疗,可是最后又都放弃了。不过还好,战后Backus进入纽约哥伦比亚大学学习数学,并于1949年毕业。在毕业前夕,他跑到了麦迪逊大街的IBM计算机中心参观。事情凑巧,和导游聊天的时候Backus谈到自己正在找工作,在导游的鼓励下,他和中心一位主管的面谈,成为了一名IBM的程序员。
IBMBackus的才华得到了施展,发明了人类历史上第一个高级语言——FORTRAN。接着,又提出了规范描述编程语言语法的Backus-Naur Form(BNF)。这位当年的“差生”终于被整个计算机世界肯定——美国计算机协会于1977年授予John Backus图灵奖。

·Jon Bentley

实践探索先锋——Jon Bentley 1974年获得了斯坦福大学的学士学位,1976年获得北卡罗莱纳大学的硕士和博士学位。毕业后在卡耐基梅隆大学教授了6年计算机科学课程,1982年进入贝尔实验室。2001年退休后加入了现在的Avaya实验室,他还曾作为访问学者在西点军校和普林斯顿大学工作。他的研究领域包括编程技术、算法设计、软件工具和界面设计等等。
他写作过三本编程书籍,其中最著名的就是涵盖从算法理论到软件工程各种主题的Programming Pearls(编程珠玑),这其实是他发表过的文章的合集。在这些文章里,Jon从工程实现的角度出发,为程序员们提供了一个个艰难问题的解决方案,犹如一颗颗闪闪发亮的珍珠。Bentley的珍珠超出了可靠工程学的范畴,利用他的洞察力和创造力为那些恼人的问题提供了独特而巧妙的解决方案。

·Nicklaus Wirth
Pascal之父——Nicklaus Wirth,如果说有一个人因为一句话而得到了图灵奖,那么这个人应该就是Nicklaus Wirth,这句话就是他提出的著名公式“算法+数据结构=程序”。这个公式对计算机科学的影响程度足以类似物理学中爱因斯坦的“E=MC^2——一个公式展示出了程序的本质。
Nicklaus Wirth
1934年出生于瑞士,1963年在加州大学伯克利分校取得博士学位。取得博士学位后直接被以高门槛著称的斯坦福大学聘到刚成立的计算机科学系工作。在斯坦福大学成功的开发出Algol W以及PL360后,爱国心极强的Nicklaus Wirth1967年回到祖国瑞士,第二年在他的母校苏黎世工学院他创建与实现了Pascal语言——当时世界上最受欢迎的语言之一。后来他的学生Philipe Kahn毕业后和Anders Hejlsberg(Delphi之父)创办了Borland公司靠Turbo Pascal起家,很快成为了将Borland发展成为全球最大的开发工作厂商,这一切都不得不说要归工于PASCAL语言的魅力。PASCAL已经影响了整整几代的程序员,Nicklaus Wirth的思想还将会继续指引现在和以后的程序员前进的方向。

·Rebert Sedgewick
算法的讲解者——Robert Sedgewick是普林斯顿大学的计算机科学教授。他还是Adobe 
Systems
的一名主管,也曾作为访问学者在Xerox PARCIDAINRIA工作。他在斯坦福大学获得博士学位。他的著作包括Algorithm in CAlgorithm in C++Algorithm in Java等系列书籍,这些都再版多次。“没有人能够将算法和数据结构解释得比Robert Sedgewick更清楚易懂了!”很多读过他著作的程序员这样说。
目前Robert正在研究算法设计、数据结构、算法分析等方面的基础理论。他善于通过数学方法评估和预测算法性能,设法发现算法、数据结构的通用机制,例如使用逼近方法寻找更快速更高效的算法。另外,他还将算法和图形学结合起来,例如使用可视化方法评估算法效率,算法的图形化模拟,用于出版物的高质量算法表现方法等等。

·Tony Hoare
计算机领域的爵士——Tony Hoare1934年出生于英国,1959年博士毕业于俄罗斯莫斯科国立大学,获得语言机器翻译专业学士学位。1960年发布了使他闻名于世的快速排序算法(Quick Sort),这个算法也是当前世界上使用最广泛的算法之一。
Tony Hoare
在取得博士学位后,就职于Elliott Brothers,领导了Algol 60第一个商用编译器的设计与开发,由于其出色的成绩,最终成为该公司首席科学家。从1977年开始,Tony Hoare博士任职于牛津大学,投身于计算系统的精确性的研究、设计及开发。因其对Algol 60程序设计语言理论、互动式系统及APL的贡献,1980年被美国计算机协会授予“图灵奖”。
1999
年在牛津大学退学后,Tony Hoare博士被微软剑桥研究院聘请担任高级程序员,从事微软剑桥研究院研究生成果的工业化应用的工作,以及协助其它研究人员进行服务于软件产业及用户的长期基础研究项目。2000年因为其在计算机科学与教育上做出的贡献被封为爵士。

·Udi Manber
首席算法官——世界上还有如此奇怪的职位?但是对于Amazon乃至Google来说,这一点也不奇怪。Udi Manber,这位前Amazon的“首席算法官”,现在是Google负责工程事务的副总裁。他研究WWW的应用程序、搜索以及隐藏在这背后的算法设计。在此期间,他与其他人共同开发了AgrepGlimpseHarvestUnix上的搜索软件。1998年,Udi成为了Yahoo!的首席科学家。2002年,Amazon创造性地给了Udi“首席算法官”的职位,和UdiAmazon的“Search Inside the Book”搜索项目所做的工作相得益彰。
Udi
还因为他所著的Introduction to Algorithms——A Creative Approach而被大家称道。

 
转自:http://blog.sina.com.cn/s/blog_65d26f050100rwsa.html

本文链接

from 博客园_业精于勤,荒于嬉;行成于思,毁于随: http://www.cnblogs.com/hnrainll/archive/2012/07/30/2614914.html

Written by cwyalpha

七月 31, 2012 at 5:08 上午

发表在 Uncategorized

Thought this was cool: The Netflix Tech Blog: Chaos Monkey released into the wild

leave a comment »

Comments: “The Netflix Tech Blog: Chaos Monkey released into the wild”

URL: http://techblog.netflix.com/2012/07/chaos-monkey-released-into-wild.html

We have found that the best defense against major unexpected failures is to fail often. By frequently causing failures, we force our services to be built in a way that is more resilient. We are excited to make a long-awaited announcement today that will help others who embrace this approach.

Do you think your applications can handle a troop of mischievous monkeys loose in your infrastructure? Now you can find out.

What is Chaos Monkey?

Chaos Monkey is a service which runs in the Amazon Web Services (AWS) that seeks out Auto Scaling Groups (ASGs) and terminates instances (virtual machines) per group. The software design is flexible enough to work with other cloud providers or instance groupings and can be enhanced to add that support. The service has a configurable schedule that, by default, runs on non-holiday weekdays between 9am and 3pm. In most cases, we have designed our applications to continue working when an instance goes offline, but in those special cases that they don’t, we want to make sure there are people around to resolve and learn from any problems. With this in mind, Chaos Monkey only runs within a limited set of hours with the intent that engineers will be alert and able to respond.

Why Run Chaos Monkey?

Failures happen and they inevitably happen when least desired or expected. If your application can’t tolerate an instance failure would you rather find out by being paged at 3am or when you’re in the office and have had your morning coffee? Even if you are confident that your architecture can tolerate an instance failure, are you sure it will still be able to next week? How about next month? Software is complex and dynamic and that “simple fix” you put in place last week could have undesired consequences. Do your traffic load balancers correctly detect and route requests around instances that go offline? Can you reliably rebuild your instances? Perhaps an engineer “quick patched” an instance last week and forgot to commit the changes to your source repository?

There are many failure scenarios that Chaos Monkey helps us detect. Over the last year Chaos Monkey has terminated over 65,000 instances running in our production and testing environments. Most of the time nobody notices, but we continue to find surprises caused by Chaos Monkey which allows us to isolate and resolve them so they don’t happen again.

Auto Scaling Groups

The default instance groupings that Chaos uses for selection is Amazon’s Auto Scaling Group (ASG). Within an ASG, Chaos Monkey will select an instance at random and terminate it. The ASG should detect the instance termination and automatically bring up a new, identically configured, instance. If you are not using Auto Scaling Groups that should be the first step to making your application handle these isolated instance failure scenarios. Check out Asgard to make deploying and managing ASGs easy. There are many great features for ASGs beyond replacing terminated instances, like enabling the use of Amazon’s Elastic Load Balancers (ELBs) to distribute traffic to all instances in your application. Netflix has a best-practice where all instances should be run within an ASG and we have Janitor Monkey to remind us by terminating all instances not following this best-practice.

Configuration

Chaos Monkey allows for an Opt-In or an Opt-Out model. At Netflix, we use the Opt-Out model, so if an application owner does nothing, Chaos Monkey will be acting on their application. For your organization, you have the option to choose what is right for you. This allows you to “test the water” and try out Chaos Monkey on a specific application to see how it reacts. Not every application can trivially handle an instance going offline.  Sometimes it takes a human to manually recover instances, perhaps exercising backups to bring them back. Ideally, engineers work towards making that process easier and faster and eventually automatic. For those applications, there is the ability to Opt-Out of Chaos Monkey. There is also a tunable “probability” that Chaos Monkey uses to control the chance of a termination.  A probability of 1 (or 100%) will terminate one instance per day per ASG.  If instance recovery is difficult and you only want a termination weekly, you can reduce the probability to 0.2 or 20% (daily is 100%, it runs 5 work days per week, so weekly is 20%). Note that this is still a probability and only meaningful when sampled multiple times. With a 20% probability, Chaos Monkey would terminate one instance a week on average. In practice, it might be 2 days in a row followed by 2 weeks of no terminations, but given a large enough sample it will terminate weekly on average. For an environment as large as Netflix, the configuration can get a bit tricky to manage and for this we have developed a dashboard to help that we hope to open source soon. You can read more about how to configure Chaos Monkey on the documentation wiki.

REST

Currently, there is a simple REST interface that allows you to query Chaos Monkey termination events. We keep records of what was terminated and when, so if something disappears, you can see if Chaos Monkey was responsible. You could use this API to get notifications of terminations, but we encourage you to use a more general application monitoring solution like servo to discover what is happening to your applications at runtime.

Costs

The termination events are stored in an Amazon SimpleDB table by default. There could be associated costs with Amazon SimpleDB but the activity of Chaos Monkey should be small enough to fall within Amazon’s Free Usage Tier. Ultimately the costs associated with running Chaos Monkey are your responsibility.

More Monkey Business

We have a long line of simians waiting to be released.  The next likely candidate will be Janitor Monkey which helps keep your environment tidy and your costs down.  Stay tuned for more announcements.

If building tools to automate the operations and improve the reliability of the cloud sounds exciting, we’re always looking for new members to join the team.  Take a look at jobs.netflix.com for current openings or contact @atseitlin.

Chaos Monkey

Netflix Cloud Platform


from Hacker News 50: http://techblog.netflix.com/2012/07/chaos-monkey-released-into-wild.html?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+hacker-news-feed-50+%28Hacker+News+50%29

Written by cwyalpha

七月 30, 2012 at 4:39 下午

发表在 Uncategorized